UC知道pascal语言编程 斐波拉契的
来源：百度知道 编辑：UC知道 时间：2024/06/21 10:51:57
Description
王者们的名字在石碑上被激活，或许其中就有你，为了知道自己是否是将来的王者，我们需要在自己脑子里找出上天赋予我们的天然密码来预知它。这个密码就是左右脑记忆量的和。
初始时，我们左脑记忆量为0，右脑记忆量为1，为了得出密码，我们需要将两个记忆量相加，然后替换为左脑的新记忆量或右脑新的记忆量，而这其中的最大值更接近密码的真实值。当替换了N次后，我们就可以得出最后的密码了。
由于最终的密码可能过大，所以我们只需要取其对于2009的余数即可。
Input
一行，一个数字，N.
对于50%的数据满足 1 <= N <= 1000
对于100%的数据满足 1 <= N <= 1000000
Output
一行，最终密码对于2009的余数。
Sample Input
5
Sample Output
8
我的程序
var
a:array[0..1000000] of longint;
b,n:longint;
begin
readln(n);
a[0]:=0;
a[1]:=1;
for b:=2 to n+1 do
a[b]:=((a[b-1] mod 2009)+(a[b-2] mod 2009)) mod 2009;
writeln(a[b],' ');
end.
怎么过不了1000000那个点？？？
请高手帮我优化一下 谢谢
王者们的名字在石碑上被激活，或许其中就有你，为了知道自己是否是将来的王者，我们需要在自己脑子里找出上天赋予我们的天然密码来预知它。这个密码就是左右脑记忆量的和。
初始时，我们左脑记忆量为0，右脑记忆量为1，为了得出密码，我们需要将两个记忆量相加，然后替换为左脑的新记忆量或右脑新的记忆量，而这其中的最大值更接近密码的真实值。当替换了N次后，我们就可以得出最后的密码了。
由于最终的密码可能过大，所以我们只需要取其对于2009的余数即可。
Input
一行，一个数字，N.
对于50%的数据满足 1 <= N <= 1000
对于100%的数据满足 1 <= N <= 1000000
Output
一行，最终密码对于2009的余数。
Sample Input
5
Sample Output
8
我的程序
var
a:array[0..1000000] of longint;
b,n:longint;
begin
readln(n);
a[0]:=0;
a[1]:=1;
for b:=2 to n+1 do
a[b]:=((a[b-1] mod 2009)+(a[b-2] mod 2009)) mod 2009;
writeln(a[b],' ');
end.
怎么过不了1000000那个点？？？
请高手帮我优化一下 谢谢
你原先过不去是因为：
输入的n是1000000
最后输出的b是n+1
而你的数组只开到了1000000
所以相当于你输出了a[1000001]
数组下标越界了！！！
楼上说得对，不需要把1~n全部存下来
只要用三个变量
滚动地运算就可以了！
没必要开1000000的数组 因为你最后考虑的值仅是N
并且N只和N-1 和N-2 有关
所以你只要定义三个变量
BEGIN
READLN(N);
A:=0;
B:=1;
FOR I:=1 TO N DO
BEGIN
C:=(A+B) MOD 2009;
A:=B;
B:=C;
END;
最后 writeln（c）
就成了？
我猜的
楼上说的是对的。
不过你的程序过不了1000000，是数组问题，数组要开到1000001.
你可以用矩阵快速幂，不过你可能不会