首页 > 代码库 > poj水题-1001 一个简单的大数乘幂算法实现

poj水题-1001 一个简单的大数乘幂算法实现

  说到底就是一个大数乘幂运算,小数点后零。明白大数乘幂算法直接搞。

  这里就有几个问题:

  1.幂位数小可以用二进制容器表示(取模更好,但我是为了练习STL)

  2.n位大数用string表示,外加一个int型表示小数点位置

  3.字符串×字符串用小学竖式乘法算法就行,注意补零。位数多时两个string两个string地加。

  代码长,但理解容易,大数乘法,加法函数很多都能重用。

  1 #include <iostream>  2 #include <vector>  3 #include <string>  4 #include <strstream>  5   6   7 using namespace std;  8   9 string Str_Char_Muti(const string & str,const char c) 10 { 11     int Len = str.length(); 12     int mutitemp=0,addtemp=0; 13     int i; 14     string aim =str; 15     for(i = 0;i<Len;++i) 16     { 17         mutitemp = (c -0)*(str[i]-0)+addtemp; 18         aim[i] =(char) (mutitemp%10 +0); 19         addtemp = mutitemp /10; 20     } 21     if(addtemp != 0) 22         aim = aim +(char) (addtemp+0); 23     return aim; 24 } 25 string Str_Add(const string &str_1,const string &str_2) 26 { 27     if("0" ==str_1) 28         return str_2; 29     if("0"==str_2) 30         return str_1; 31     int Llen,Slen; 32     string copy_1 = str_1; 33     string copy_2 = str_2; 34     if(str_2.length()>str_1.length()) 35     { 36         Slen = str_1.length(); 37         Llen = str_2.length(); 38         for(int i=0;i<Llen-Slen;++i) 39         { 40             copy_1 +=0; 41         } 42     } 43     else  44     { 45  46         Slen = str_2.length(); 47         Llen = str_1.length(); 48         for(int i=0;i<Llen-Slen;++i) 49         { 50             copy_2 +=0; 51         } 52     } 53  54     int addtemp=0,jin =0; 55     string aim (Llen ,0); 56     int i; 57     for(i=0 ; i<Llen ; ++i) 58         { 59             addtemp =( (copy_1[i] -0)+(copy_2[i]-0) )+jin; 60             jin = addtemp /10; 61             aim[i] =(char)( addtemp % 10 + 0 ); 62         } 63     if(jin != 0) 64     aim += (char) ( jin+0 ); 65  66     return aim; 67  68 } 69 string Str_Muti(const string &str_1,const string& str_2) 70 { 71     string aim = "0"; 72     string temp = "0"; 73     if(str_1=="1") 74         return str_2; 75     if(str_2=="1") 76         return str_1; 77     int Len_1 = str_1.length(); 78     int Len_2 = str_2.length(); 79     aim = "0"; 80     for(int i=0;i<Len_2;++i) 81     { 82         temp = Str_Char_Muti(str_1,str_2[i]); 83         for(int j=0;j<i;++j) 84         { 85                 temp = 0+ temp; 86         } 87  88         aim = Str_Add(aim,temp); 89     } 90     return aim; 91 } 92 string delete_0(const string &str ,int pos ) 93 { 94     string aim; 95     int i=0; 96     if(pos<str.length()) 97     { 98         while(str[i] == 0&&i<=pos) 99             i++;100         if(i<pos)101         {102             string head(str,i,pos-i);103             string rear(str,pos,str.length()-pos);104             string r ="";105             for(int j=0;j<rear.length();++j)106                 if(0!= rear[j]) 107                 {108                     r = rear;109                     break;110                 }111             aim = head +.+r;112 113         }114         else 115         {116             string a(str,pos,str.length()-1);117             aim = a;118         }119     }120     else 121     {122         aim = str;123         int a = pos-str.length() ;124         while(a--)   125         {126             aim = aim +0;            127         }128         aim = aim + .;129     }130     return aim;131 }132 int main ()133 {134 135     int n;136     int pos;137     string s;138     string str_a;139     string one ="1";140     while(cin>>s>>n)141     {142         pos = 0;143         str_a = "";144         string sum ="1"; 145         for(int i= 0;i<6;++i)146             {147                 if(.==s[i])148                     pos = 5-i;149                 else str_a = s[i] +str_a;150             }151 152         vector <string> di;153         pos = pos *n;154         while(n!=0)155         {156             if(n%2==1)157             {158                 di.push_back(str_a);159             }160             else 161             {162                 di.push_back(one);163             }164             str_a = Str_Muti(str_a,str_a);165             n = n/2;166         }167 168         for(int i=0;i<di.size();++i)169         {170             sum = Str_Muti(sum,di[i]);171         }172 173             str_a = delete_0(sum,pos);174 175         for(int i=str_a.length()-1;i>-1;--i)176         {177             cout<<str_a[i];178         }179             cout<<endl;180     }181     return 0;182 }