首页 > 代码库 > hdu 1021 斐波那契2，找规律
hdu 1021 斐波那契2，找规律
背景：暴力必定超数据结构范围，因为斐波那契类型数列，成指数形式爆炸增长。故写了数据发现取余30不影响结果。
学习：1.数论类题可以写出几组数据找规律，猜结论。
我的代码：
#include<stdio.h>
int str[1000009] = { 7, 11 };
int main()
{
int n;
for (int i = 2; i <=1000000; i++){
str[i] = (str[i - 1] + str[i - 2])% 30;
}
while (scanf("%d", &n) != EOF){
if (str[n ] % 3 == 0) printf("yes\n");
else printf("no\n");
}
return 0;
}
也有人根据同余的性质写出递推式{a1≡b1(mod3)，得a1+b1（mod3）}：
str[i] = str[i - 1] %3+ str[i - 2]%3;
oms解法:
找规律，一次找出f[0]~f[n]的对三取余的数：
1，2，0，2，2，1，0，1，1，2，0，2，2，1，0，1，1，2，0，2，2，1，0，1.........不断循环
我们的目的是找到取余之后的0与n的关系，除了第一个，0和0之间都是有三个数，所以容易得到只要n%4==2，那么f[n]=0.
hdu 1021 斐波那契2，找规律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。