杭州交通信息网中国的历史地图册:帮帮忙 今年的noip
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 17:42:32
var
n:longint;
function g(k:longint):longint;
begin
if k<=1 then g:=k
else
g:=(2002*g(k-1)+2003*g(k-2)) mod 2005;
end;
begin
read(n);
writeln(g(n));
end.
当n=2005时输出多少
noip2005 提高 pascal第4题。
要具体的算法 要具体的算法
怎样用二分法作呀
n:longint;
function g(k:longint):longint;
begin
if k<=1 then g:=k
else
g:=(2002*g(k-1)+2003*g(k-2)) mod 2005;
end;
begin
read(n);
writeln(g(n));
end.
当n=2005时输出多少
noip2005 提高 pascal第4题。
要具体的算法 要具体的算法
怎样用二分法作呀
g(x) = (-1)^(n-1)(2^n - 1) mod 2005
用数学归纳法可以证明
剩下来的工作就是求2^2005 mod 2005了。求出来是32，因此答案31
g(x) = (-1)^(n-1)(2^n - 1) mod 2005 (1)
当x=0，1的时候显然正确。
现在由定义，g(x) = (2002g(x-1) + 2003g(x-2)) % 2005
=(-3g(x-1) - 2g(x-2)) % 2005
=(-3*(-1)^(x-2)(2^(x-1)-1) - 2*(-1)^(x-3)(2^(x-2)-1)) % 2005
=(-1)^(x-3)(3*2^(x-1) - 3 - 2*2^(x-2) + 2) % 2005
=(-1)^(x-1)(2^x - 1) % 2005
即当g(x-2),g(x-1)成立时g(x)也成立
因此推出(1)式正确
回二楼:
机器运行肯定出不了结果。你认为你的计算机调用2^2005次函数要多少时间内完成？
其实这道题有人借用很好的电脑算过,半个小时之内是没有答案显示的。