XMU1428 求遞歸的次數 帥額

1428.Hofstadter G-sequence Time Limit: 1000 MS         Memory Limit: 65536 K  Total Submissions: 228 (66 users)         Accepted: 42 (39 users)  [ My Solution ] Description Hofstadter G-sequence是一個有趣的數列, 但由於在此篇幅有限, 我們就不做具體的介紹了。以下的代碼, 所求的函數G(n)即為Hofstadter G-sequence數列: int G(int n) {     if(n <= 1) return 1;     return n - G(G(n - 1)); } 當然, 這道題目的要求並不是要你求出函數G(n)的值, 而是給定你一個正整數x, 你需要求解, 使用上面這個函數計算出G(x)的值需要調用函數G(n)多少次呢？ Input 輸入只有一行, 一個正整數x (1 <= x <= 1,000,000)。 Output 由於答案可能會很大, 所以你只需輸出答案對1,000,000,007取模後的結果即可。 Sample Input 3 Sample Output 5 Source  詳細看代碼   [cpp]   #include <stdio.h>    #include<string.h>    int f[1000011],ans[1000011];     const  int  mod=1000000007;     void get()   {       int i,j;           f[1]=1;       for(i=2;i<=1000000;i++)         {             f[i]=i-f[f[i-1]];         }         ans[1]=1;         for(i=2;i<=1000000;i++)         {             ans[i]=(ans[i-1]%mod+ans[f[i-1]]%mod+1)%mod;         }     }   int main()     {       int i,j,m,n;         get();       while(scanf("%d",&n)==1)         {            printf("%d\n",ans[n]);         }            return 0;     }