首页 > > 程序设计 > C/C++ >

#北大poj#1001Exponentiation求幂

2018-06-18 04:09:37来源：未知阅读 ()

附上原题地址：http://poj.org/problem?id=1001

首先分析题目，列出了我认为几个比较重要的点：

columns 1～6, columns 8～9；
全输入完后，全输出；
巨大的精确计算；
小数时首末尾零去掉；

接下来逐个击破；

输入两个整数，算乘积

　　因为是很大的数，所以已经超出了int，或是long long double所能计算的范围，于是想到了用数组的方法去处理。

　　将乘数保存到数组里，然后用列竖式的思想，进行个位的计算和进位。模拟如下：

　　　　　　　　 a[0] a[1] a[2] a[3] a[4]

　　 X 　　　 b[0] b[1] b[2] b[3] b[4]

　 ----------------------------------------------------------------------------

　　　　　　　　 [0][4] [1][4] [2][4] [3][4] [4][4]

　　　　　　　　 [0][3] [1][3] [2][3] [3][3] [4][3]

　　　　　　　　 [0][2] [1][2] [2][2] [3][2] [4][2]

　　　　 [0][1] [1][1] [2][1] [3][1] [4][1]　　

　　　　 [0][0] [1][0] [2][0] [3][0] [4][0]

　 ----------------------------------------------------------------------------

c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8]

　　然后，在写这一步代码前我先列了一个实例来明确每一步的目的：

　　　　　　　　　　 9 9

　　　　　　　X 　　 9 9 //建成两个乘数数组，数组长度即为数的位数

　　　　　　　　　---------------------

　　　　　　　　　 81 81

　　　　　　　　　---------------------

　　　　　　　　 81 162 81 //进位前各位的相乘与加和

　　　　　　　　---------------------

　　　　　　　　 81 170 1

　　　　　　　　　---------------------

　　　　　　　　 98 0 1 //进位完毕

　　　　下面是实现了“输入两个整数，算乘积”的代码：

 1 #include <stdio.h>
 2 int main() {
 3     int la,lb,l,i,j;
 4     char aa[50],bb[50];
 5     scanf("%s %s",aa,bb);
 6     la = strlen(aa);
 7     lb = strlen(bb);
 8     l=la+lb-1;
 9     int a[la],b[lb],ab[l],c[l];
10     for(i=0;i<la;i++){
11         a[i]=(int)aa[i]-48;
12     }
13     for(i=0;i<lb;i++){
14         b[i]=(int)bb[i]-48;
15     }//两个乘数数组搞定
16     for(i=l-1;i>=0;i--){
17         ab[i]=0;
18         for(j=la-1;j>i-lb;j--){
19             if(i-j>=0&&j>=0){
20             ab[i]=ab[i]+a[j]*b[i-j];
21             }
22         }
23     }
24     for(i=0;i<l;i++){
25         c[i]=ab[i];
26     }//ab进位前搞定
27     printf("\n");
28     for(i=l-1;i>=1;i--){
29         c[i]=ab[i]%10;
30         ab[i-1]=ab[i-1]+(ab[i]-c[i])/10;
31     }
32     c[0]=ab[0];
33     for(i=0;i<l;i++){
34         printf("%d",c[i]);
35     }  
36     return 0;
37 }

输入多个乘数后，分行输出结果

　　　　这里用到了一个语句：while(scanf("%s%d",s,&n)==2)或者也可写作while(scanf(%s%d",s,&n)!=EOF)

　　　　作用就是输入数据输入完成以后则跳出循环。

　　　　下面是实现了“输入多个乘数后，分行输出结果”的代码：

 1 #include <stdio.h>
 2 int main() {
 3     int x[100],y[100],z[100],i=0,j;
 4     while(scanf("%d %d",&x[i],&y[i])==2){
 5         z[i]=x[i]*y[i];
 6         i++;
 7     }
 8     for(j=0;j<i;j++){
 9         printf("%d\n",z[j]);
10     }
11     return 0;
12 }