主题：2005 noip考题 1道
mdjqdh
[专家分：140] 发布于 2005-10-15 17:33:00
看程序写结果的
program m;
var n:longint;
function g(k:longint):longint;
begin
if k<=1 then g:=k
else g:=(2002*g(k-1)+2003*(k-2)) mod 2005
end;
begin
read(n);
writeln(g(n));
end.
输入 2005
输出:?
这个怎么算 ? 我感觉用笔好象根本算不出来
回复列表 （共16个回复）
沙发
FancyMouse [专家分：13680] 发布于 2005-10-15 18:10:00
g(x) = (-1)^(n-1)(2^n - 1) mod 2005
用数学归纳法可以证明
剩下来的工作就是求2^2005 mod 2005了。求出来是32，因此答案31
板凳
mdjqdh [专家分：140] 发布于 2005-10-15 18:22:00
汗 偶像...
能否问下具体证明过程
我们还没学归纳法
3 楼
FancyMouse [专家分：13680] 发布于 2005-10-15 18:28:00
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)式正确
4 楼
mdjqdh [专家分：140] 发布于 2005-10-15 18:48:00
思路是怎么来得? 以便我以后能会这个类型的
5 楼
天水 [专家分：320] 发布于 2005-10-15 20:01:00
我在机器上运行时为什么很久不出结果？？？？
6 楼
天水 [专家分：320] 发布于 2005-10-15 20:03:00
请问 楼主您哪个省的？
好像noip今天才举行的吧？这么快就提问了？
7 楼
FancyMouse [专家分：13680] 发布于 2005-10-15 20:42:00
机器运行肯定出不了结果。你认为你的计算机调用2^2005次函数要多少时间内完成？
用这个检查答案吧：
int g(int x)
{
int d[10000];
d[0] = 0;d[1] = 1;
for(int i=2;i<=x;i++)
d[i] = 2002*d[i-1] + 2003*d[i-2];
return d[i];
}
8 楼
FancyMouse [专家分：13680] 发布于 2005-10-15 21:04:00
不好意思我用C的，要用pascal的话翻译一下再运行
9 楼
DullSky [专家分：50] 发布于 2005-10-15 22:17:00
原来是：
var n:integer;
function g(k:integer):integer;
begin
if k<=1 then
g:=k
else
g:=(g(k-1)*2002+g(k-2)*2003) mod 2005;
end;
begin
readln(n);
write(g(n));
end.
输入2005
输出：？
运行不了！！！
var a,b,c,n:integer;
begin
a:=0;
b:=1;
for n:=2 to 2005 do begin
c:=(2002*a+2003*b) mod 2005;
writeln('g(',n,')=',c);
a:=b;
b:=c;
end;
end.
改成递推后的
执行结果1994
10 楼
FancyMouse [专家分：13680] 发布于 2005-10-15 22:24:00
你写错了。答案肯定31。
应该c:=(2003*a+2002*b) mod 2005;
我来回复
您所在位置：