浅析100的阶乘算法

烽火ㄨ飞狐

注：对于搞过或者正在搞信息学竞赛的朋友，这篇文章无非讲了一点高精度的皮毛，无须浪费时间阅读.
前不久看到有兄弟问关于100阶乘的算法。
这个问题不简单。 初学编程的人可能会立即想到一个算法——不就是一个循环的事儿么！

其实从数学的角度来看，这个算法是完全正确的,但是现实世界比数学世界要复杂的多。这样的算法无疑会导致数据溢出。（说到底“溢出”是“黑客”们吃饭的本钱，关于溢出的话题这里不做过多讨论，不懂得可以自己去google，简单说就是100的阶乘这个结果太大了，以至于C语言内置的任何一中变量都盛不下）

根据我一个印度朋友的实验，用MatLab可以不考虑溢出而顺利的得出结果。C语言是以简洁著称的，标准库里没有提供处理大数的方案。不过这也不是什么缺点，刚好给了我们一个自己动手来探索在其他语言内部大数乘法实现方法的机会。

废话说道这里。

问题的核心在于，C并没还有给我们提供一个储存大数的方法，更毋提数学运算了。所以首先我们需要一个储存大数的方法。这里采用一个最简单的解决方案：数组。
我们用一个整数数组来代表一个大数，数组中的每一个元素储存大数中的一位数。数组下标从小到大分别表示大数的低位到高位。举个例子：个位数由下标为0的元素来表示。

有了储存的方法，下面我们考虑一下怎样来让两个储存在数组里的大数相乘。
其实现在我们更接近原始的数学运算。由于数组的运用，我们重新“获得”了数位的概念。拿出纸和笔，回想一下用竖式演算的过程。这里以456*123为例：

  4 5 6
X 1 2 3
-----------
1 3 6 8
9 1 2
4 5 6
-----------
5 6 0 8 8

呵呵，没算错吧？
不难看出，这个笔算的过程可以总结成这样：
用第二个大数的每一位和第一个大数的每一位相乘，把每一次乘完得到的结果按照相应位数累加起来，就得到了结果。
这里有几个关键的细节，我们不妨给每一个数位都标上对应的数组下标：

  4 5 6
X 1 2 3
-----------
1 3 6 8
9 1 2
4 5 6
-----------
5 6 0 8 8

4 3 2 1 0 <===数组下标

经过观察，可以发现，当第一个大数下标为x的数字和第二个大数下标为y的数字相乘的时候，所得结果的最低位的下标是x+y。例如6的下标是0，2的下标是1，2*6的时候得到的最低位数字是2，而它的下标恰为0 + 1 = 1。
在竖式里面，每当两个数字相乘的时候，如果结果大于9，那么就自动近位。但实际编程的时候，由于我们用一个整型变量存储一位数，所以当某次结果大于9的时候，我们不立即进位，而是简单的把这个两位数（或者是更多位数，只要整型变量能存的下）存在这个“数位”里。到特定的时候再处理。

有了相乘的方法，剩下的阶乘只要用一开始那个最简单的循环搞定就行了。

算法说到这应该已经没什么好说的了。在下面的代码里，我定义了用来表示大数的结构Super,里面记录的大数的长度和内容，然后就有一套处理这个结构的函数（输入，输出，初始化，相乘）。具体请看注释。

#include<stdio.h>
#include<string.h>
#define SUPER_LEN 10***00 //最多位数

typedef struct super Super; //储存大数的结构
struct super
{
  int num[SUPER_LEN]; //大数
  int len; //大数长度
};

void trans(char*s, Super *n); //输入函数，把一个字符串转换成大数结构
void output(Super *n); //输出函数，把一个大数输出到标准输出
Super super_mul(Super *a,Super *b); //两个大数相乘，返回结果
void super_empty(Super *); //初始化大数结构

int main (void)
{
  int i;
  char s[SUPER_LEN];
  Super a,b,c;
  
  a.len=1;
  a.num[0]=1;

  for(i=2;i<=100;i++) { //循环计算阶乘
    sprintf(s,\"%d\",i); //把整数转换成字符串
    trans(s,&b); //把字符串转换成大数结构
    a = super_mul(&a,&b); //累乘到a里
  }  
  output(&a); //输出结果
  printf(\"\\n\");

  return 0;
}

void trans(char *s,Super *n)
{
  int i;
  n->len = strlen(s);
  for (i = 0;i < n->len; i++) {
    n->num = s[n->len-i-1] - &#39;0&#39;;
  }
}
void output(Super *n)
{
  int i;
  for(i=n->len-1;i>=0;i--)
    printf(\"%d\",n->num);
}


Super super_mul (Super *a,Super *b)
{
  Super r, *c = &r,*t;
  int i,j,p,left;

  if (a->len < b->len) { //a代表较长的大数
    t=a;
    a=b;
    b=t;
  }
  super_empty(c); //c指向用于返回的结果，在这里初始化
  c->len = a->len; //c的初始长度
  for(i=0; i < b->len;i++) { //较短大数的每一位
    for (j=0; j< a->len; j++) { //乘以较长大数的每一位
      c->num[i+j] += b->num * a->num[j]; //前面解释过，数组下标和数字所在数位的关系
    }
    for(p=i; p < i+j; p++) { //现在开始进位
      left = c->num[p] / 10;
      c->num[p] %= 10;
      c->num[p+1] += left;
    }
    c->len = i+j; //更新结果的长度
    if(c->num[p]) c->len++; //如果最后一位大于10，再进位

  }
  return r;
}

void super_empty(Super *a)
{
  int i;
  for(i=0; i< SUPER_LEN; i++)
    a->num = 0;
  a->len = 0;
}

其实这样的算法在时间和空间上都十分浪，不过还好它解决了溢出的问题。安全第一嘛。

很久没有coding了，文章中如果有误，欢迎各位牛人指正。