hdu 5167 Fibonacci（DFS，剪枝，斐波那契）

最新推荐文章于 2019-03-18 20:48:45 发布

acm_cxq

最新推荐文章于 2019-03-18 20:48:45 发布

阅读量712

点赞数

分类专栏：搜索文章标签： ACM HDU dfs

本文链接：https://blog.csdn.net/acm_cxq/article/details/51932448

版权

搜索专栏收录该内容

27 篇文章

订阅专栏

本文探讨了如何解决HDU 5167 Fibonacci问题，通过使用深度优先搜索（DFS）并结合剪枝策略来避免超时错误。在枚举过程中，从最大数开始向下进行，同时对特殊情况0、1、2进行特判，以防止无限循环。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Fibonacci

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

Problem Description

Following is the recursive definition of Fibonacci sequence:

F i = ⎧ ⎩ ⎨ 01 F i - 1 + F i - 2 i = 0 i = 1 i > 1

Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.

Input

There is a number

T shows there are

T test cases below. (

T≤100,000 )
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

Sample Output

  
  
   
   Yes
No
Yes

题意：问n是否能由多个斐波那契数相乘而来

思路：直接爆搜会TLE，所以这里有个剪枝技巧，我们从大小大枚举，这一次搜索选择了i,那么我们下次只需要枚举3~i即可，相等于从序列最大的数开始向下枚举。

注意0,1,2不能算进去，0,和1要特判，不然会死循环。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
#define N 100000
long long f[N];
int flag,cnt;
long long n;
void init()
{
    f[0]=0;
    f[1]=1;
    cnt=2;
    for(; f[cnt-1]<=1000000000; cnt++)
        f[cnt]=f[cnt-1]+f[cnt-2];
}
void dfs(long long k,int num)
{
    if(k==1){
        flag=1;
        return;
    }
    for(int i=num;i>=3;i--)
        {
            if(f[i]>k) continue;
            if(k%f[i]==0)
            dfs(k/f[i],i);
            if(flag) return;
        }
}
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        if(!n||n==1) printf("Yes\n");
        else
        {
            flag=0;
            dfs(n,cnt-1);
            if(flag) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}