模拟记忆化
原题链接：7972.【递归】斐波那契数列
2024-11-30 19:46:45
发布于：江苏
7阅读
0回复
0点赞
先列举斐波那契数列找规律。
i=1——1
i=2——1
i=3——2
i=4——3
i=5——5
i=6——8
把这些数组按奇偶性分开。
i=1——1 i=2——1
i=3——2 i=4——3
i=5——5 i=6——8
把n=1和n=2特判之后，可以发现规律。
i=1——l=1
i=2——r=1
i=3——l=l+r=1+1=2
i=4——r=r+l=1+2=3
i=5——l=l+r=2+3=5
......
所以当i为奇数时，改变l；i为偶数时，改变r。
同样的，当n为奇数时，输出l；n为偶数时，输出r。
得到模拟代码
#include <cstdio>
#define xc(l,r) for (int i=l; i<=r; i++)
long long n,l,r;
int main()
{
scanf("%d",&n);
l=r=1;
xc(3,n)
{
if (i%2==1) l+=r;//奇数改变l
else r+=l;//偶数改变r
}
printf("%d",n%2==1?l:r);//奇数输出l，偶数输出r
return 0;
}
这里空空如也
有帮助，赞一个