首页 > ACM题库 > HDU-杭电 > HDU 4099-Revenge of Fibonacci-字典树-[解题报告]HOJ
2015
04-16

HDU 4099-Revenge of Fibonacci-字典树-[解题报告]HOJ

Revenge of Fibonacci

问题描述 :

The well-known Fibonacci sequence is defined as following:

  Here we regard n as the index of the Fibonacci number F(n).
  This sequence has been studied since the publication of Fibonacci’s book Liber Abaci. So far, many properties of this sequence have been introduced.
  You had been interested in this sequence, while after reading lots of papers about it. You think there’s no need to research in it anymore because of the lack of its unrevealed properties. Yesterday, you decided to study some other sequences like Lucas sequence instead.
  Fibonacci came into your dream last night. “Stupid human beings. Lots of important properties of Fibonacci sequence have not been studied by anyone, for example, from the Fibonacci number 347746739…”
  You woke up and couldn’t remember the whole number except the first few digits Fibonacci told you. You decided to write a program to find this number out in order to continue your research on Fibonacci sequence.

输入:

  There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases (T<=50000).
  For each test case, there is a single line containing one non-empty string made up of at most 40 digits. And there won’t be any unnecessary leading zeroes.

输出:

  There are multiple test cases. The first line of input contains a single integer T denoting the number of test cases (T<=50000).
  For each test case, there is a single line containing one non-empty string made up of at most 40 digits. And there won’t be any unnecessary leading zeroes.

样例输入:

15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

样例输出:

Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374

题目:Revenge of Fibonacci

 

题意:给出斐波那契数列的前k位,k不超过40,找出最小的正整数n,满足F(n)的前k位与给定数的前k位相同,斐波那契数列的项数不超过100000。

 

解析:本题可以分为两步:

第一步就是预处理出100000项斐波那契数列的前40位,插入到字典树中。

第二步就是查询匹配求最小的n。

对于第一步,我们可以把斐波那契数列精确到50多位,然后只存40位即可,这样就防止进位的误差。在斐波那契数列加法过程中,我们只把它的前50多

位进行相加,不然存不下。

 

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N=10;

int f1[65],f2[65],f3[65];

class Trie
{
    public:
       int v;
       int flag;
       Trie *next[N];
       Trie()
       {
           v=-1;
           memset(next,NULL,sizeof(next));
       }
};

Trie *root;

void Insert(char *S,int ans)
{
    int len=strlen(S);
    Trie *p=root;
    for(int i=0;i<len;i++)
    {
        int id=S[i]-'0';
        if(p->next[id]==NULL)
            p->next[id]=new Trie();
        p=p->next[id];
        if(p->v<0) p->v=ans;
    }
}

int Find(char *S)
{
    Trie *p=root;
    int count;
    int len=strlen(S);
    for(int i=0;i<len;i++)
    {
        int id=S[i]-'0';
        p=p->next[id];
        if(p==NULL) return -1;
        else  count=p->v;
    }
    return count;
}

void Init()
{
    int h;
    char str[65]="1";
    memset(f1,0,sizeof(f1));
    memset(f2,0,sizeof(f2));
    memset(f3,0,sizeof(f3));
    f1[0]=1;f2[0]=1;
    Insert(str,0);
    for(int i=2;i<100000;i++)
    {
        memset(str,0,sizeof(str));
        int r=0;
        for(int j=0;j<60;j++)
        {
            f3[j]=f1[j]+f2[j]+r;
            r=f3[j]/10;
            f3[j]%=10;
        }
        for(int j=59;j>=0;j--)
        if(f3[j])
        {
            h=j;
            break;
        }
        int k=0;
        for(int j=h;j>=0;j--)
        {
            str[k++]=f3[j]+'0';
            if(k>=40) break;
        }
        Insert(str,i);
        if(h>55)
        {
            for(int j=1;j<59;j++)
                f3[j-1]=f3[j];
            for(int j=1;j<59;j++)
                f2[j-1]=f2[j];
        }
        for(int j=0;j<60;j++)
            f1[j]=f2[j];
        for(int j=0;j<60;j++)
            f2[j]=f3[j];
    }
}

int main()
{
    root=new Trie();
    Init();
    char str[105];
    int t,i,j,k=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",str);
        printf("Case #%d: ",k++);
        int tmp=Find(str);
        printf("%d\n",tmp);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9390039


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。