递推法 - 大数阶乘问题

递推法：

      要求问题规模为N的解，当N=1时，解或为已知，或能非常方便的得到解。当得到问题规模为i-1的解后，由问题的递推性质，能从已经求得的规模为1，2，...，i-1的一系列解，构造出问题规模为i的解。这样，程序可从i=0或i=1出发，重复的，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

 

题目：

      编写程序，对给定的n（n<=100），计算并输出k的阶乘k!（k=1，2，...，n）的全部有效数字。

思路：

      要求的整数超出了范围，用数组来存储。a[0]存储长整数的位数m，例如5! = 120存为{3，0，2，1}。计算k!可采用对已经求得的（k-1）!连续累加k-1次后求出。

 

程序代码：

 

#include <stdio.h>
#include <malloc.h>

#define MAXN 1000

// 已知a中的(k - 1)!，求出k!
void pnext(int a[], int k) {
	
	int *b, m = a[0], i, j, r, carry;
	b = (int *)malloc(sizeof(int) * (m + 1));
	for(i = 1; i <= m; i++) b[i] = a[i];
	for(j = 1; j < k; j++) { // 控制累加k-1次
		for(carry = 0, i = 1; i <= m; i++) {
			// 这里的a[0]保存的是(k-1)!的位数，m则是k!的位数，所以m变化后会大于a[0]
			r = (i <= a[0] ? a[i] + b[i] : a[i]) + carry;
			a[i] = r % 10; carry = r / 10;
		}
		if(carry) a[++m] = carry;
	}
	free(b);
	a[0] = m;
}

void write(int *a, int k) {
	int i;
	printf("%4d!=", k);
	for(i = a[0]; i > 0; i--) printf("%d", a[i]);
	printf("\n\n");
}

void main() {
	int a[MAXN], n, k;
	printf("Enter the number n:");
	scanf("%d", &n);
	a[0] = 1;
	a[1] = 1;
	write(a, 1);
	// 这里就是从1开始的递推过程
	for(k = 2; k <= n; k++) {
		pnext(a, k);
		write(a, k);
		getchar();
	}
}