首页 > 代码库 > 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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。