Exponentiation(poj能通过,joj不能)

来源:互联网 时间:1970-01-01

#include <stdio.h>#include <stdlib.h>#include <string.h>using namespace std;const int baseLength = 6;const int MAX = 200;char a[baseLength]={0}; //base///不要思维定势地以为b也要用字符数组来保存///Don't think b as array,a integer type is enoughint b = 0; //indexint c[MAX] = {0}; //bit informationint d[MAX] = {0}; //same as cint e[MAX] = {0}; //resultint pos = -1; //track the position of pointint pos_not_zero_right = 0; //the first postion that is not zero from rightint pos_not_zero_left = 0;bool isZero = true;void display(){ pos_not_zero_right = MAX-1; pos_not_zero_left = 0; if (pos >=0) { for (int i=MAX-1; i>=MAX-pos-1; i--) { if (e[i] != 0) { pos_not_zero_right = i; break; } ///如果到了小数点的位置,数字还是零,那么就把小数点的下标赋值给有界限pos_not_zero_right if (i == MAX-pos-1 && e[i] == 0) { pos_not_zero_right = MAX-pos-1; } } } else { pos_not_zero_right = MAX-1; } for (int i=0; i<MAX; i++) { if (e[i] != 0 || i == MAX-pos) { pos_not_zero_left = i; break; } } for (int i=pos_not_zero_left; i<=pos_not_zero_right; i++) { if (i == MAX-pos) { printf("."); } printf("%d", e[i]); } printf("/n");}void Exp(int index){ if (index == 1) { for (int i=0; i<MAX; i++) { e[i] = c[i]; } return; } else if (index == 0) { e[MAX-1] = 1; return; } else //index >= 2 { ///注意index是与1比较还是与0比较:当index=2时,是两个数相乘一次 ///Be careful about the value of index while (index-- != 1) { for (int i=MAX-1; i>=(MAX)/2; i--) { for (int j=MAX-1; j>=(MAX)/2; j--) { e[ j-(MAX-1-i) ] += c[i]*d[j]; if (e[ j-(MAX-1-i) ] >= 10) { ///要时刻清楚c,d,e都是干什么的,就不会把数组名搞错; ///c,d存的是数,连个一样的数,e存的是数的n次方 ///Be clear about what the function of c,d,e,or it's ///easy to get wrong,c,d store number,two completely ///identical array,and e is used to store temp and ///ultimate results; e[ j-(MAX-1-i)-1 ] += e[ j-(MAX-1-i) ] / 10; e[ j-(MAX-1-i) ] = e[ j-(MAX-1-i) ] % 10; } } } for (int i=0; i<MAX; i++) { c[i] = e[i]; ///每乘一次都要把e清零,e相当于累加寄存器,如果不清零,则会重复的加 e[i] = 0;//There is a need to clear the array e for storing results; } } for (int i=0; i<MAX; i++) { e[i] = c[i]; } }}int main(){ while (scanf("%s%d", a, &b) == 2) { //检查输入的书是否是零,要检查各种形式; //check if the input data is zero, in several ways; isZero = true; for (unsigned int p=0; p<strlen(a); p++) { //如果有数字不是零或浮点,则这个书不是零; if (!(a[p] == '0' || a[p] == '.')) { isZero = false; break; } } if (isZero && b != 0) { printf("0/n"); continue; } if (isZero && b == 0) { continue; } int i, j; for (i=0, j=MAX-1; i<baseLength; i++) { if (a[baseLength-i-1] != '.') { //store the data in array c,in the way of integer, //one bit to one bit,right align c[j--] = a[baseLength-i-1]-'0'; } else { pos = i;//pos是从左边数的下标 } } //copy c to d for (int k=0; k<MAX; k++) { d[k] = c[k]; } Exp(b); pos = pos * b; display(); b = 0; pos = -1; for (int k=0; k<MAX; k++) { a[k] = 0; c[k] = 0; d[k] = 0; e[k] = 0; } } return 0;}
要注意的问题:(1)gcc下使用const int var = ...会产生variably modified 'users' at file scope的错误(http://hi.baidu.com/brady_home/blog/item/d37ab2af5826f6ca7dd92a2
a.html);
 (2)gcc不识别bool类型,所以用int代替即可;(http://tech.16c.cn/linux/accidence/20091029/11713.html)
 (3)要注意对边界的确定。边界有左有右,要把它们和小数点位置综合起来考虑;因为数组中是不保存小数点的所以在确定有边界时要格外注意当前下标和小数点位置的大小
 关系。可能小数点前一位仍然是零。
 (4)做题之前要理解乘法是如何转换成加法的,数组对应位置要想好;
 (5)学会以“ (scanf("%s%d", a, &b) == 2)”控制输入;


相关阅读:
Top