首页 > 代码库 > BestCoder10 1001 Revenge of Fibonacci(hdu 5018) 解题报告
BestCoder10 1001 Revenge of Fibonacci(hdu 5018) 解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5018
题目意思:给出在 new Fibonacci 中最先的两个数 A 和 B(也就是f[1] = A, f[2] = B),通过这条式子f[n] = f[n-1] + f[n-2],问 C 是否在这条 new Fibonacci sequence 内。(1 <= A, B, C <= 1 000 000 000)
首先,要想到 C 有可能是 A 或者 B,这种情况也是属于在这个序列范围内的。
还有一个地方,不要固定死数组的长度,因为不确定到底需要多大的空间存下来,而且,确实比较浪费空间,当前需要求出一个新的数,其实就是需要前面的两个数而已,再前面的根本就没什么用。
于是我这里就用到滚动数组的技巧,只开了长度为 4,不断迭代来判断在 1000 000 000 的范围内,能否得到 C 这个数。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 1e9; 8 __int64 A, B, C; 9 __int64 f[4];10 11 int main()12 {13 int T, i;14 while (scanf("%d", &T) != EOF)15 {16 while (T--)17 {18 scanf("%I64d%I64d%I64d", &A, &B, &C);19 f[0] = 0;20 f[1] = A;21 f[2] = B;22 if (C == A || C == B)23 printf("Yes\n");24 else25 {26 bool flag = 0;27 for (i = 3; ; i++)28 {29 f[0] = f[1];30 f[1] = f[2];31 f[2] = f[0] + f[1];32 if (f[2] == C)33 {34 flag = 1;35 break;36 }37 if (f[2] >= INF)38 break;39 }40 printf("%s\n", flag ? "Yes" : "No");41 }42 }43 }44 return 0;45 }
BestCoder10 1001 Revenge of Fibonacci(hdu 5018) 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。