蟠桃记-数字序列-Fibonacci Again

Description

喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！
什么问题？他研究的问题是蟠桃一共有多少个！
不过，到最后，他还是没能解决这个难题，呵呵^-^
当时的情况是这样的：
第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？

Input

输入数据有多组，每组占一行，包含一个正整数n（1 < n < 30），表示只剩下一个桃子的时候是在第n天发生的。

Output

输入数据有多组，每组占一行，包含一个正整数n（ 1 < n < 30），表示只剩下一个桃子的时候是在第n天发生的。

Sample Input

2
4

Sample Output

4
22

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 long long f(int n)
 7 {
 8 
 9     if (n==1) return 1;
10 
11     return 2*(f(n-1)+1);
12 }
13 
14 int main()
15 {
16     int n;
17     while (cin>>n)
18     {
19         cout<<f(n)<<endl;
20     }
21 
22 
23       return 0;
24 
25 }

题目源地址

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 
 7 
 8 int main()
 9 {
10 int a,b,n,data[101],i;
11 data[1]=data[2]=1;
12 while (scanf ("%d %d %d",&a,&b,&n)!=-1)
13 {
14     if (a==0&&b==0&&n==0)
15         break;
16     if (n<3)
17         cout<<"1"<<endl;
18     else
19     {
20 
21     for(i=3;i<50;i++)//循环节多大怎么估算
22     {
23         data[i]=(a*data[i-1]+b*data[i-2])%7;
24         if (data[i]==1&&data[i-1]==1)
25             break;
26     }
27 n=n%(i-2);
28     if (n==0)
29         cout<<data[i-2]<<endl;
30     else
31         cout<<data[n]<<endl;
32     }
33 
34 
35 
36 }
37 
38       return 0;
39 
40 }

大致思路：

1.输入a,b,n

2. 开数组，大致估算循环节的长度，把循环节输入直到一个循环节的结束。

3. 但是1 1 0 4 5 1 1,所以用n%（i-2),有两种情况0或者1 2 3 4 5分别对待。

4. i-2>0,所以i>3,再讨论

自动找出循环节：

for(i=3;i<=49;i++) 
{ 
data[i]=(a*data[i-1]+b*data[i-2])%7; 

if (data[i]==1&&data[i-1]==1) break;
}

题目源地址

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 5 using namespace std;
 6 int ha(int n)
 7 {
 8     if (n==0) return 1;
 9     if (n==1) return 2;
10     return (ha(n-1)+ha(n-2))%3;
11 }
12 
13 int main()
14 {
15     int n;
16     while (cin>>n)
17     {
18         n=n%8;
19         if (ha(n)==0)
20             cout<<"yes"<<endl;
21         else
22             cout<<"no"<<endl;
23     }
24 
25 
26       return 0;
27 
28 }