POJ 1001 Exponentiation 字符串乘法+快速求幂

我就是我 2023-06-13 09:41 85阅读 0赞

**考虑一下下面的样例应该可以AC：**

底数整数的情况
    去掉最后后导零
    没有小数部分时候不输出小数点

**思路**  
**先不考虑小数点  
将数存入字符串a,b中  
答案存入ret  
ret的长度是a的长度和b的长度之和  
a\[i\]和b\[j\]相乘的位置放在ret的i+j和i+j+1的位置  
注意进位**

#include <iostream>
    #include <string>
    using namespace std;
    
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    string cheng(string a,string b){ 
        string ret(a.size()+b.size(),'0');
        for( int i=a.size()-1;i>=0; i-- ){ 
            for( int j=b.size()-1;j>=0;j-- ){ 
                int temp = (a[i]-'0')*(b[j]-'0') + ret[i+j+1]-'0';
                ret[i+j+1] = temp%10+'0' ;
                ret[i+j] += temp/10;
            }
        }
        return ret;
    }
    
    string quickPow( string a,int n ){ 
        string ret = "1";
        while( n>0 ){ 
            if( n&1 ){ 
                ret = cheng(ret,a);
            }
            n >>= 1;
            a = cheng(a,a);
        }
        return ret;
    
    }
    
    int main()
    { 
        string s="0.4321";
        int a=20;
        while( cin >> s >>a ){ 
            int pos = s.find('.');
    
            string qian = s.substr(0,pos);
            string hou = s.substr( pos+1 );
            if(pos==-1){ 
                hou = "";
            }
            string ret = quickPow(qian+hou,a);
            int i = 0;
            int houSize = hou.size()*a;
            qian = ret.substr(0,ret.size()-houSize);
            hou = ret.substr(ret.size()-houSize);
            while( i < qian.size() && qian[i] == '0' ){ 
                i ++;
            }
            qian = qian.substr(i);
            i = hou.size()-1;
            while(i>=0 && hou[i]=='0'){ 
                i--;
            }
            hou = hou.substr(0,i+1);
            if(hou.size()==0){ 
                cout<< qian << endl;
            }else{ 
                cout<< qian <<"."<< hou <<endl;
            }
    
        }
        return 0;
    }

![在这里插入图片描述][20191115195653298.png]

[20191115195653298.png]: https://img-blog.csdnimg.cn/20191115195653298.png