Question

pascal高精度算法求n！（带讲解，初学者。满意追加）

Answer 1

阶乘的计算

问题描述

输入一个整数n(1<=n<=1000),输入n!的精确值.

分析:当n比较大时,n!是一个很大的数,Pascal的实数和整数类型均不能存储,所有考虑用高精度计算.

这个问题的情况比较特殊，我们可以把n!看成(n-1)!*n,这样参与乘法的两个数一个是高精度数(n-1)!，另一个是常规的整数n.

下面我们看,如何得到n!的精确值,
如:12！=12*11！=12*39916800,以些为例说明计算过程：
(1)a数组存放的是上一次阶乘的结果39916800(这里是11!)，所以此时a数组的存放情况为：

下标k 1 2 3 4 5 6 7 8 9 10...
数组a 0 0 8 6 1 9 9 3 0 0 ...

(2)在进行计算时将a中的各个元素分别同乘数(这里是12)相乘，结果存放在当前位，上面的a数组同12相乘，得到的中间结果为：

下标k 1 2 3 4 5 6 7 8 9 10...
数组a 0 0 96 72 12 108 108 36 0 0 ...

(3)每次乘积运算之后将处理进位,如上例中a[3]将向a[4]进位9，进位后a[3]=6，a[4]=81，同时a[4]在向a[5]进位8，进位后a[4]=1，a[5]=20,a[5]向a[6]进位2,进位后a[5]=0,a[6]=110,a[6]向a[7]进位11,进位后a[6]=0,a[7]=119,a[7]向a[8]进位11,进位后,a[7]=9,a[8]=47,a[8]向a[9]进位4,进位后[8]=7,a[9]=4,a[9]不必向a[10]进位了,到些进位处理完成.通过进位处理后,a数组中存储的数据如下:

下标k 1 2 3 4 5 6 7 8 9 10...
数组a 0 0 6 1 0 0 9 7 4 0 ...

此时a数组中存储的数就是12!=479001600,这与我们手工计算的结果是一样的.
参考程序如下:(同学们可以构造不同的程序)

var n,i,j,k,x,q:word;
a:array[1..3000] of word;{1000!不会超过3000位,a数组保存高精度计算结果}
begin
write('n=');readln(n);
for i:=1 to 3000 do a[i]:=0;{a数组初始化}
k:=1;{数组a的第一个下标}
a[1]:=1;{a[1]取初值}
for i:=2 to n do {分别取2,3,...,n,与数组a相乘}
begin
for j:=1 to k do a[j]:=a[j]*i;{i与数组a相乘}
q:=0;{以下程序段作进位处理}
for j:=1 to k do
begin
x:=a[j]+q;
a[j]:=x mod 10;
q:=x div 10;
end;
while (q>0) do{对最后一位再做进位处理}
begin
k:=k+1;
a[k]:=q mod 10;
q:=q div 10;
end;
end;
for i:=k downto 1 do{输出n!的精确值}
write(a[i]);
writeln;
writeln('k=',k);{统计n!有多少位}
end.