首页 > 代码库 > 【Fibonacci】BestCoder #28B Fibonacci

【Fibonacci】BestCoder #28B Fibonacci

2024-11-25 08:34:02   203人阅读

Fibonacci

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 795    Accepted Submission(s): 213

Problem Description
Following is the recursive definition of Fibonacci sequence:
Fi=???01Fi−1+Fi−2i = 0i = 1i > 1
Fi=
　　0, 　　　　　 i = 0
　　1, 　　　　　 i = 1
　　Fi−1+Fi−2, 　i > 1
Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.(一开始没理解题意，其实我觉得这题意也不大好=。 =，题解说是Fib乘积，但和为什么不行呢，路过的可以帮忙解答一下)
 
Input
There is a number T shows there are T test cases below. ( T < 100000 )
For each test case , the first line contains a integers n , which means the number need to be checked.
0≤n≤1,000,000,000
 
Output
For each case output "Yes" or "No".
 
Sample Input
3417233
 
Sample Output
YesNoYes
 
Note：
1、Fibonacci序列在1~1000000000范围内只有43个数。
2、判断一个数是几个数乘积的递归算法（掌握）；
 
代码（看过题解）：
技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using namespace std; 6 const int maxn = 100; 7 int f[maxn], tmp[maxn], j, k; 8 void Fibonacci() 9 {10     f[0] = 0; f[1] = 1;11     k = 2;12     while(f[k-1] + f[k-2] <= 1000000000)13     {14         f[k] = f[k-1] + f[k-2];15         k++;16     }17 }18 bool Judge(int x, int step)//注意这里没有step的话会tle。。。19 {20     if(x == 1) return true;21     for(int i = step; i < j; i++)22     {23         if(x%tmp[i] == 0)24         {25             if(Judge(x/tmp[i], i))26                 return true;27         }28     }29     return false;30 }31 int main()32 {33     Fibonacci();34     int T;35     scanf("%d", &T);36     for(int i = 0; i < T; i++)37     {38         int n;39         scanf("%d", &n);40         if(!n) printf("Yes\n");41         else42         {43             j = 0;44             for(int i = 3; i < k; i++)45             {46                 if(n%f[i] == 0)47                     tmp[j++] = f[i];48             }49             if(Judge(n, 0)) printf("Yes\n");50             else printf("No\n");51         }52     }53     return 0;54 }
View Code

 

【Fibonacci】BestCoder #28B Fibonacci


联系
我们