主题:[讨论]1!+2!++50!如何只用高精度加法,请教各位大牛
interegg
[专家分:80] 发布于 2007-08-03 21:25:00
1!+2!++50!如何只用高精度加法,请教各位大牛,帮帮小弟,谢谢咯[em2]
回复列表 (共11个回复)
沙发
Matodied [专家分:7560] 发布于 2007-08-03 21:36:00
只用高精度加法?
那么50!只能用实型才可以装的下!
我可没学过用高精度计算实型数的,而且是用科学计数法表示的!
板凳
interegg [专家分:80] 发布于 2007-08-03 21:54:00
对于此题的解法是这样的:
用高精度乘法与加法(也可以全部用加法来实现)
小弟在括号里的话就听不明白了,请帮忙解释下,如何才能办到
3 楼
Matodied [专家分:7560] 发布于 2007-08-03 22:00:00
可以用高精度乘法加上加法。
用乘法加上加法:
(1)1! + 2! + 3! + ... + 50!
=(1) + (1 * 2) + (1 * 2 * 3) + ... + (1 * 2 * 3 * ... * 50)
其中每一个括号就可以用高精度乘法实现了。
至于全用加法的方法我还不知道,可能是乘法可以转换成加法,但是这样的话式子就太烦琐了。
4 楼
interegg [专家分:80] 发布于 2007-08-03 22:04:00
是不是把乘法可以看成是几个相同的数相加,再利用递归解决?
5 楼
Matodied [专家分:7560] 发布于 2007-08-03 22:15:00
对!
比如(1 * 2 * 3)只要进行以下计算:
(1 * 2) = 1 + 1 = 2
(2 * 3) = 2 + 2 + 2 = 6
6 楼
interegg [专家分:80] 发布于 2007-08-03 22:27:00
如果这样编出来的程序效率怎么样?会不会有太多重复的步骤出现?怎么样进行优化?
如
4!算好后 算5!就不用重新把前面的算一次了,这样的问题怎么来解决?
7 楼
Matodied [专家分:7560] 发布于 2007-08-04 14:33:00
n!算好后再算(n + 1)!的公式(只用加法):
(n + 1)! = n! + n! + n! + ... + n!
(__________ _________)
\/
n + 1 个 n!
下面是一个根据n!求(n + 1)! 的函数(只用高精度加法):
TYPE arr = ARRAY[1..1023] OF INTEGER;
FUNCTION gjdadd(a, b: STRING): STRING;
VAR
x, y, z: arr; r, s: STRING;
la, lb, l, i, k: INTEGER;
BEGIN
la := LENGTH(a); lb := LENGTH(b);
IF la > lb THEN l := la ELSE l := lb;
FOR i:=1 TO l + 1 DO z[i] := 0;
FOR i:=1 TO la DO VAL(COPY(a, la + 1 - i, 1), x[i], k);
FOR i:=1 TO lb DO VAL(COPY(b, lb + 1 - i, 1), y[i], k);
FOR i:=1 TO l DO BEGIN
z[i] := z[i] + x[i] + y[i];
IF z[i] >= 10 THEN BEGIN z[i] := z[i] - 10; z[i + 1] := z[i + 1] + 1; END;
END;
IF z[l + 1] <> 0 THEN l := l + 1;
r := '';
FOR i:=l DOWNTO 1 DO BEGIN
STR(z[i], s); r := r + s;
END;
gjdadd := r;
END;
FUNCTION nextmult(result: STRING; n: INTEGER): STRING;
VAR
i: INTEGER; m: STRING;
BEGIN
m := result;
FOR i:=2 TO n + 1 DO BEGIN
m := gjdadd(m, result);
END;
nextmult := m;
END;
其中result是n!。
比如:nextmult('120', 5) = 720(6!)
这样你的问题就好做了。
程序:
VAR
i: INTEGER; l, t: STRING;
BEGIN
l := '1';
FOR i:=2 TO 50 DO BEGIN
t := nextmult(l, i - 1);
l := gjdadd(l, t);
END;
WRITELN(l);
END.
(其中gjdadd就是求高精度加法的函数)
结果:
775559376643691140112121508234651605531629860008493056000000000000
8 楼
interegg [专家分:80] 发布于 2007-08-05 07:43:00
谢谢,那么只用高精度加法与合用高精度乘法与加法,哪个效率高?
9 楼
Matodied [专家分:7560] 发布于 2007-08-05 13:16:00
差不多,看你自己吧。
10 楼
abcwuhang [专家分:1840] 发布于 2007-08-05 22:10:00
var n:byte;
i,z,zo:longint;
ji,c:array[1..20000]of 0..9;
procedure times(ii:byte);
var j,t,tt:longint;
begin
t:=0;
if ii<=i then
begin
for j:=1 to z do
begin
tt:=t;
t:=(ji[j]*ii+t) div 10;
ji[j]:=(ji[j]*ii+tt) mod 10;
end;
if t>0 then
begin
inc(z);
ji[z]:=t;
end;
times(ii+1);
end
else
begin
zo:=z;
for j:=1 to z do
begin
tt:=t;
t:=(c[j]+ji[j]+t) div 10;
c[j]:=(c[j]+ji[j]+tt) mod 10;
end;
if t>0 then
begin
inc(zo);
c[zo]:=t;
end;
fillchar(ji,sizeof(ji),0);
ji[1]:=1;
z:=1;
end;
end;
begin
fillchar(ji,sizeof(ji),0);
ji[1]:=1;
fillchar(c,sizeof(c),0);
z:=1;
zo:=0;
n:=50;{求1!+...+n!,这里设定n=50}
for i:=1 to n do
times(1);
for i:=zo downto 1 do
write(c[i]);
writeln;
end.
我来回复