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.