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;
}
补充：软件开发 , C++ ,
