|
context
阶乘
【题目】数学上定义:
n!=1×2×3×...×(n-1)×n (N>0)
0!=1
若用integer型数据表示阶乘,最多可到7!,用Longint类型也只能到12!
要求输入正整数n,求 n! 的精确表示
【算法分析】用数组存放结果，模拟人工计算过程，逐位去乘，注意进位情况的处理。
【参考程序１】
const
max=1000;
var
n,i,j,jinwei,weishu:integer;
result:array[1..max] of integer;
{result 数组放结果}
begin
writeln('input n:');readln(n);
{输入n}
fillchar(result,sizeof(result),0);
result[1]:=1;
{从1开始乘起}
jinwei:=0;
{jinwei:进位}
weishu:=1;
{weishu:结果的位数}
for i:=2 to n do begin
{从2开始,一直乘到n}
jinwei:=0;
{进位预置为0}
for j:=1 to weishu do begin
{×i,用result数组逐位去乘}
result[j]:=result[j]*i+jinwei; {加上上一次的进位}
jinwei:=result[j] div 10; {逢10进位,生成新的进位}
result[j]:=result[j] mod 10;
{result数组只放10以内的数字}
end;
while jinwei<>0 do begin
{一轮算完后,有新的进位时}
weishu:=weishu+1;
{位数加1}
result[weishu]:=jinwei mod 10;
{循环处理进位,直到为0}
jinwei:=jinwei div 10; {因为进位可能不只一位数}
end;
if weishu>max then begin writeln('error!');halt;end;{超过预定位数,出错}
end;
write(n,'!=');
for i:=weishu downto 1 do write(result[i]);readln; {输出}
end.
【参考程序２】
var
a:array[1..10000] of integer;
b,c,d,t,x:integer;
begin
write ('input number:');
readln (x);
if (x<0) then
begin writeln ('error!'); readln; halt; end;
for t:=1
to 10000 do a[t]:=0;
d:=1; a[1]:=1;
for c:=1 to x do
{一直乘到x}
begin
t:=1; b:=0;
{t:第几位数
b:进位 d:总位数}
repeat
a[t]:=a[t]*c+b; {数组每位均乘上c,同时加上进位}
b:=a[t] div 10; {分离出进位}
if a[t]>=10 then if (t=d) then d:=d+1;
{假如最后一位乘时有}
{进位,则总位数加1}
a[t]:=a[t] mod 10;
inc (t);
{数组下一位}
until (t>d);
{直到乘完数组的每一位数字}
end;
write (x,'!=');
for t:=d downto 1 do write (a[t]);
{输出}
end.
【题目】求ｍ×ｎ的值。（ｍ与ｎ的位数均不超过２５５位）
【算法分析】由于ｍ与ｎ的位数太大，所以必须用高精度运算。与高精度阶乘不同之处在于,如何处理部分积相加的问题.两数相乘的高精度运算，其实即是用计算机来模拟手工进行两数相乘。
试看
n=811,m=98 的情况:
811
用m的每一位(从低位到高位)去乘n的每一位,
× 98
------
6488
7299
<------------注意这里如何处理相加.同理,m的百位,千位.....
-------
乘n后的结果如何相加,也要处理好.
79478
【参考答案】
123456789*123456789=15241578750190521
1111111*111=123333321
9999999*99=989999901
987654321*987654321=975461057789971041
99999999999999999999*99999999999999999999=9999999999999999999800000000000000000001
【参考程序】
const max=10000;
var
i,j,jinwei,weishu:integer;
n,m:string;n_length,m_length:integer;
result:array[1..max] of integer;
begin
writeln('input n:');readln(n);
{m,n均用字符串输入}
writeln('input m:');readln(m);
fillchar(result,sizeof(result),0);
n_length:=length(n);
{n_length:被乘数n的位数}
m_length:=length(m);
{m_length:乘数m的位数}
for i:=1 to m_length
do begin
{用m的每个数字去乘n}
jinwei:=0;
{预置进位为0}
for j:=1 to n_length do begin
{因n也是大数,故要一位一位地去乘}
result[j+i-1]:=(ord(n[n_length+1-j])-48)
*(ord(m[m_length+1-i])-48)+jinwei+result[j+i-1];
{相乘的结果放数组result,其下标j+i-1同时反应了应该加在哪个位上}
{注意要把字符串的数字转换成数值才能相乘}
jinwei:=result[j+i-1] div 10;
{处理进位}
result[j+i-1]:=result[j+i-1] mod 10;
end;
weishu:=n_length+i-1;
{乘完一轮后,已有的位数}
while jinwei<>0 do begin
{处理乘完一轮后,产生的进位}
weishu:=weishu+1;
result[weishu]:=(jinwei+result[weishu]);
jinwei:=(result[weishu]) div 10;
result[weishu]:=(result[weishu]) mod 10;
end;
if weishu>max then begin writeln('error!');halt;end;{超过预定位数,出错}
end;
write(n,'*',m,'=');
{输出}
for i:=weishu downto 1 do write(result[i]);readln;
end.
|