UC知道高精度应用（兔子繁殖）求解释
来源：百度知道 编辑：UC知道 时间：2024/09/25 12:25:14
高精度应用（兔子繁殖）求解释
高精度有一道题是：
Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？
已知：N<=93。
程序如下：
var
n,len,i,k:integer;
f1,f2,f:array[1..210] of integer;
begin
fillchar(f1,sizeof(f1),0);
fillchar(f2,sizeof(f2),0);
readln(n);
f1[1]:=1;
F2[1]:=1;
len:=1;
for k:=3 to n do
begin
fillchar(f,sizeof(f),0);
（for i:=1 to len do
begin
f[i+1]:=(f1+f2+f) div 10;
f:=(f1+f2+f) mod 10;
end;）这一部分是什么意思？
if f[len+1]>0 then len:=len+1;
f1:=f2;
f2:=f;
end;
writeln(len);
for i:=len downto 1 do write(f);
end.
高精度有一道题是：
Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？
已知：N<=93。
程序如下：
var
n,len,i,k:integer;
f1,f2,f:array[1..210] of integer;
begin
fillchar(f1,sizeof(f1),0);
fillchar(f2,sizeof(f2),0);
readln(n);
f1[1]:=1;
F2[1]:=1;
len:=1;
for k:=3 to n do
begin
fillchar(f,sizeof(f),0);
（for i:=1 to len do
begin
f[i+1]:=(f1+f2+f) div 10;
f:=(f1+f2+f) mod 10;
end;）这一部分是什么意思？
if f[len+1]>0 then len:=len+1;
f1:=f2;
f2:=f;
end;
writeln(len);
for i:=len downto 1 do write(f);
end.
这个程序的时间复杂度太高了，可读性也差，我写个容易理解，并且时间复杂度非常低的程序给你吧。
你看，他这里面有一个i循环，每一次都要进行一次数组的移位，如果数据刁钻的话，这个程序必卡无疑。
program rabbit_Hewr;
type
high=array[0..1000]of byte;
var
a:array[0..2]of high; //这里表示FIB里面的三个数，我用的是动态储存。
i,tmp,n:longint; //tmp记录现在应该是a[tmp]更新。
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function add(a,b:high):high;//高精度加法。
var
i,s,g:longint;
ans:high;
begin
fillchar(ans,sizeof(ans),0);
ans[0]:=max(a[0],b[0])+2;
g:=0;
for i:=1 to ans[0] do begin
s:=a[i]+b[i]+g;
ans[i]:=s mod 10;
g:=s div 10;
end;
while (ans[0]>1) and (ans[ans[0]]=0) do dec(ans[0]);
add:=ans;
end;
begin
readln(n);
fillchar(a,sizeof(a),0);
a[1][0]:=1;
a[1][1]:=1;
a[2][0]:=1;
a[2][1]:=1;
tmp:=2;
if n<=2 then writeln(1) e