poj 1001 Exponentiation ?模拟大数
链接:
http://poj.org/problem?id=1001
题意:
题意很简单,给你2个数(前面的是小数,后面是不超过25的整数),求得前一个数的幂(后一个数作指数部分)。
思路:
要求小数的幂,用一般的double,float完全满足不了解的需求。而且看到案例就知道肯定用大数解决。
大数解决最简单的看来是用JAVA直接可以求,不过我还没有学习JAVA,只能悲催的用字符串来解决。
由于第2个数(指数项)并不大,完全可以以相乘来解决乘方。
又由于小数点可以自行推算,所以可以把小数做整数来求,最后再插入小数点。
所以,我们总结起来要解决的问题,无非下面几点:
1.如何做整数乘法,并记录大数?
大数乘法,本来需要俩个乘数都化为字符串形式,逐位相乘,再进位记录。但这一题乘数只有5位酱紫,可以用整数记录。
那么只需要一个用数组记录结果,另一个用整数记录。
2.如何找到小数点位置?
小数就为原来查找到小数距最后一位的距离乘上指数就是最后小数点距最后一位的距离。
3.如何做最后输出(舍去前导0和后导0)
寻找到有用的开始下标数,和结束下标数。
ac代码:
#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <string> #include <algorithm> using namespace std; #define ll long long #define PI acos(-1.0) const int INF=99999999; const int MAXN=3000; const int mod=100; int result[130]; //记录结果数组 int multiplier; //作乘数 void multiply() { int temp[130]; //过程数组 memset(temp,sizeof(temp)); for(int i = 0; i < 130; i++) { int t = result[i] * multiplier; int carry = (t + temp[i]) / 10; //需要进位的数 temp[i] = (t + temp[i]) % 10; //不需要进位的数 //进位处理 int g = 1; while(carry) { int t = temp[i+g] + carry; carry = t / 10; temp[i+g] = t % 10; g++; } } //传回数组数值 for(int i = 0; i < 130; i++) result[i] = temp[i]; } void output(int point) { int began=0,aim=129; for(int i = 0; i < 130 ;i++) { began = i; if(i == point) break; if(result[i] != 0) break; } for(int i = 129; i >= 0; i--) { aim = i; if(result[i] != 0) break; if(i == point-1) break; } for(int i = aim; i >= began; i--) { if(i == point-1) cout << '.'; cout << result[i]; } cout << endl; } int main() { char a[15]; int n; while(~scanf("%s%d",a,&n)) { memset(result,sizeof(result)); //初始化 int point; //记录小数点位置 int index=4; //记录下标 multiplier = 0; //处理乘数的值,点的位置,结果数组的初始值 for(int i=0;i<6;i++) { if(a[i] == '.') point = i; else { multiplier = multiplier*10+(a[i]-'0'); result[index--] = a[i]-'0'; } } //处理最终点的位置 point = 5 - point; point = point * n; //连乘 for(int i = 1; i < n; i++) multiply(); //for(int i=0;i<= 50;i++) //cout << result [i]; //cout << endl; output(point); } return 0; }
发现以上代码在HDU1063并过不了。
现在重新编写了一份代码,已AC:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> using namespace std; const int N = 130; int result[N]; char real[N]; char s[10]; int main() { int n; while(~scanf("%s",s)) { memset(result,sizeof(result)); scanf("%d",&n); int temp[N]; int len = strlen(s); int point_id = -1; //小数点后面数字的数量 int k = 0; int a = 0,b = 1; for(int i = len-1; i >= 0; i--) { if(s[i] != '.') { result[k++] = s[i]-'0'; a += (s[i]-'0')*b; b *= 10; } else point_id = k; } if(point_id != -1) point_id = point_id*n; printf("%d\n",point_id); n--; while(n--) { memset(temp,sizeof(temp)); int add = 0; for(int i = 0; i < N; i++) { int x = a*result[i]; printf("%d x\n",x); int g = 0; while(x) { int f = temp[i+g]+x; x = f/10; temp[i+g] = f%10; g++; } } for(int i = 0; i < N; i++) result[i] = temp[i]; } k = 0; int flag = 0; for(int i = 0; i < N; i++) { if(i == point_id) { real[k++] = '.'; point_id = -1; flag = 1; } if(result[i] == 0 && point_id != -1 && !flag) continue; real[k++] = result[i]+'0'; flag = 1; } real[k] = '\0'; puts(real); flag = 0; for(int i = k-1; i >= 0; i--) { if(i == 0 && real[i] == '.') continue; if(real[i] != '0') { printf("%c",real[i]); if(flag == 0) flag = 1; } else if(flag == 1 && real[i] == '0') printf("%c",real[i]); } puts(""); } return 0; }