华师一附中OI组

标题: 求3的N次方 [打印本页]
作者: diggersun    时间: 2014-11-1 14:09
标题: 求3的N次方
标准程序：
  1. #include <iostream>
  2. using namespace std;
  3. int a[100]; //定义了a[0]***a[9]共10个元素
  4. int i,j,k;
  5. int x;
  6. int main()
  7. {
  8.     a[0]=1;  //乘法默认的初值是1
  9.     for (k=0; k<=99; k++)  //做 100次连乘  
  10.     {
  11.         for (i=0; i<=99; i++) a[i]=a[i]*3;  //每位数字都乘法   
  12.         for (i=0; i<=98; i++)  //进位  标程
  13.         {
  14.             x=a[i];
  15.             a[i]=x%10;
  16.             a[i+1]=a[i+1]+x/10;
  17.         }
  18.     }
  19.     j=99;
  20.     while ((a[j]==0) && (j>0)) j--;
  21.     for (i=j; i>=0; i--) cout<<a[i];
  22. }
复制代码
作者: clivia    时间: 2014-11-1 14:11
我什么都不说了。（语言意味上）
作者: diggersun    时间: 2014-11-1 14:15
有人说，老师，初值设为3，减少一次乘法，
Mr Sun：可行，意义不大。
有人说，老师，我每次乘以27，减少大约2/'3乘法，
Mr Sun：可行，代码会变复杂，可以考虑。
有人说，老师，每次乘法里面又有100次此小乘法和100次进位，其实大多数情况下，前面都是0，可以考虑优化
Mr Sun： U R Very Clever！！！我们增加一个变量，记录有效位数，在此位数之后的都有效,前面的都是0.
shaonian: 其实我一般不用这样的方法，因为*****
Mr Sun： 学习和解决问题是不一样的！！

作者: diggersun    时间: 2014-11-1 14:20
改进后的程序
  1. #include <iostream>
  2. using namespace std;
  3. int a[100]; //定义了a[0]***a[9]共10个元素
  4. int i,j,k;
  5. int l;
  6. int x;
  7. int main()
  8. {
  9.     a[0]=1;
  10.     l=0;  //乘法默认的初值是1
  11.     for (k=0; k<=99; k++)  //做 100次连乘
  12.     {
  13.         for (i=0; i<=l; i++) a[i]=a[i]*3;  //每位数字都乘法
  14.         for (i=0; i<=l-1; i++)  //进位  标程
  15.         {
  16.             x=a[i];
  17.             a[i]=x%10;
  18.             a[i+1]=a[i+1]+x/10;
  19.         }
  20.         if (a[l]>=10)
  21.         {
  22.             x=a[l];
  23.             a[l]=x%10;
  24.             a[l+1]=a[l+1]+x/10;
  25.             l++;
  26.         }
  27.     }
  28.     for (i=l; i>=0; i--) cout<<a[i];
  29.     return 0;
  30. }
复制代码
作者: diggersun    时间: 2014-11-1 14:29
更好的做法当然是快速幂，但是这个太难，以后再讲。
现在我们修改这个程序做100！
作者: hr567    时间: 2014-11-1 22:39
本帖最后由 hr567 于 2014-11-1 22:50 编辑

改两句话就够了……
  1. #include <iostream>
  2. using namespace std;
  3. int a[100];
  4. int i,j,k;
  5. int l;
  6. int x;
  7. int main()
  8. {
  9.     a[0]=1;
  10.     l=0;
  11.     for (k=1; k<=100; k++)
  12.     {
  13.         for (i=0; i<=l; i++) a[i]=a[i]*k;
  14.         for (i=0; i<=l-1; i++)
  15.         {
  16.             x=a[i];
  17.             a[i]=x%10;
  18.             a[i+1]=a[i+1]+x/10;
  19.         }
  20.         while (a[l]>=10)
  21.         {
  22.             x=a[l];
  23.             a[l]=x%10;
  24.             a[l+1]=a[l+1]+x/10;
  25.             l++;
  26.         }
  27.     }
  28.     for (i=l; i>=0; i--) cout<<a[i];
  29.     return 0;
  30. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2