说到底就是一个大数乘幂运算,小数点后零。明白大数乘幂算法直接搞。
这里就有几个问题:
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 }
poj水题-1001 一个简单的大数乘幂算法实现,布布扣,bubuko.com
原文:http://www.cnblogs.com/fuyi/p/3901197.html