阶乘：1x2x3x4.....N，仿照2的N次方的手法，只不过这次从前往后计算，得到的数从左往后，依次为个位十位百位...等等。
例如：021，表示120
#include <iostream> using namespace std; #define max 100 /*保存结果的数组长度*/ int f[max]; int main() { int n=10; /*n表示n!，自由修改*/ f[0] = 1; for(int i = 2;i <= n;i++) { int c = 0;/*进位值*/ for(int j = 0;j < max;j++)/*整个数组乘一遍*/ { int s = f[j] * i + c; f[j] = s % 10; c = s / 10; } } for(int k = max - 1;k >= 0;k--) /*扫描清除右边的0*/ if(f[k]) break; for(i = k;i >= 0;i--) /*从右往左打印结果*/ cout<<f[i]; return 0; }
这个算法的一个缺点是，每次都要把数组乘一遍，有什么办法能优化它呢？
一、首先对阶乘结果的位数进行优化，采用的思路是：
int f(int n) { double a=0.0; while(n) { a+=log10(n); n--; } return (int)a+1; }
得到位数的好处是，不用事先定义一个大数组，而是需要多少位就分配多大的数组（堆分配），这是解决空间的问题。
接着，再想着时间的问题，假如定义100个元素的数组，每次代码都要从数组的首位一直到末位乘以一个数，假如算到5！=120的时候，数组存储的情况是：
0 2 1 0 0 0 0 0 0....
现在又要这个数组每位再乘以6，则右边是一连串的0，还有必要再依次乘一遍吗？设想了几种可能，均告失败。记录一下错误的尝试：
这种思路是，初始化时先把数组全部置为某个字符，比如'C’，而在循环相乘的判定中，如果没有进位，且下一个数组元素是标志‘C'，就停止循环，但是忽略了这个标志’C'也需要参与运算，于是失败！
现在设想，如果把已经得到结果的最末位数做一个监视哨flag，每次循环乘数只要乘到这个监视哨就结束，就可以解决这个问题！如图所示：
flag作为监视哨，必定指向每次运算之后的结果的最末位。假如现在j又要乘以6，从第一位0开始，一直移位到监视哨。即：j<=flag。
第二种情况，假如在监视位出现进位了，依然还要继续乘下去，于是，得到另一个条件：f>0，只要有进位也要继续往下乘。
第三种情况：假如现在结果已经是0 2 7，（720），再乘以7之后，得到：
0 4 0 5，由于flag现在还指向第三位，所以要把位置提到末位，也就是说，每次循环完成之后，还要提升监视哨的位置.
到此，问题算是解决了！
这个模型相当于，如何在数组的循环运算中截断到某个位置！（主要判定监视哨的位置和中止的条件）
/*算法改进，效率提升很多！*/ #include <iostream> using namespace std; #define max 30000 int a[max]; int main() { int n,x; cin>>n; a[0]=1; for(int i=2,flag=0;i<=n;i++)/*监视哨初始指向数组首位*/ { for(int f=0,j=0;j<=flag || f>0;j++)/*j未到监视哨，或者有进位*/ { x=a[j]*i+f; f=x/10;/*进位*/ a[j]=x%10; } while(a[j]==0)/*提升监视哨的位置,j有两种可能的位置*/ j--; flag=j; } while(flag>=0) /*输出结果*/ { cout<<a[flag]; flag--; } return 0; }
