递归练习

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

InputInput consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
OutputPrint the word "yes" if 3 divide evenly into F(n).

Print the word "no" if not.
Sample Input

Sample Output

no
no
yes
no
no
no

一开始是用递归的，但发现n太大的，就推算了几个，发现了个规律，只要+2并能整除4的都是yes，否则是no

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int main(){
 7     int n;
 8     while(~scanf("%d",&n)){
 9         if((n+2)%4) cout << "no" << endl;
10         else cout << "yes" << endl;
11     }
12     return 0;
13 }

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Inputn (0 < n < 20).
OutputThe output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

是一个素数环问题，一开始我也不会做，但听了学长讲后，思路就很清晰了。下面是代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <cstring>
 5 using namespace std;
 6 int a[30], vis[30];
 7 bool prime(int x){
 8     bool flag = true;
 9     for(int i = 2; i <= sqrt(x); i++){
10         if(x%i==0){
11             return false;
12         }
13     }
14     if(x >= 2 && flag)
15         return true;
16     else return false;
17 }
18 void dfs(int n,int m){
19     if(n >= m && prime(a[0] + a[m-1])){
20         for(int i = 0; i < m; i ++){
21           if(i) cout<<' ';
22             cout << a[i];
23         }
24         cout << endl;
25     }
26     for(int i = 1; i <= m; i ++){
27         if(vis[i] == 0){
28             a[n] = i;
29             if(n==0 || prime(i+a[n-1])){
30                 vis[i] = 1;
31                 dfs(n+1,m);
32                 vis[i] = 0;
33             }
34         }
35     }
36 }
37 
38 int main(){
39     int n;
40     int ans = 1;
41     while(~scanf("%d",&n)){
42         memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));
43         a[0] = 1;vis[1] = 1;
44         printf("Case %d:
",ans++);
45         dfs(1,n);
46         cout << endl;
47     }
48 }

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。
Output对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。
Sample Input

2
1 2
3 6

Sample Output

1
3

从a到b，其实可以分解为a到b-1与a到b-2之和，然后一直递归下去，知道b-a等于1或者2返回。
下面是代码：

 1 #include <iostream>
 2 #define ll long long
 3 using namespace std;
 4 ll arr[55];
 5 int main(){
 6     int n;
 7     arr[1] = 1;arr[2] = 2;
 8     for(int i = 3; i < 52; i ++)
 9         arr[i] = arr[i-1] + arr[i-2];
10     cin >> n;
11     int a,b;
12     while(n--){
13         cin >> a >> b;
14         cout << arr[b-a] << endl;
15     }
16     return 0;
17 }

There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

InputThere are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)OutputFor each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.

Sample Input

1
2
3

Sample Output

1
2
4

将情况分为在n-1后追加一位人，
①追加一位男孩，这是肯定成立的，既a[n-1]
②追加一位女孩。
　　如果是追加一位女孩，那第n-2个一定要是一位女孩。所以第②中情况有可以分成在n-2后追加两位女孩，既a[n-2]。
　　但如果n-3是一位女孩话（不合法的），在n-2后追加两位女孩也变成合法了，而这种是n-4合法的加一位男孩和一位女孩造成的，既a[n-4]。
所以规律就是a[n] = a[n-1] + a[n-2] + a[n-4],先把前四个数字算出来，就可以打表了。
下面是代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
string arr[1010];
map<char,int> mp;
string f(string s,string ss){//这函数就是大数加法的，我写的有点长，请见谅！
    reverse(s.begin(),s.end());
    reverse(ss.begin(),ss.end());
    if(s.length()>ss.length())
        swap(s,ss);
    int a,b,sum,flags=0;
    string sss;
    for(int i=0;i<ss.length();++i){
        if(i>=s.length())
            a=0;
        else a=mp[s[i]];
        b=mp[ss[i]];
        sum=a+b+flags;
        if(sum>=10){
            sum-=10;
            flags=1;
        }
        else flags=0;
      //  v.push_back(sum);
        sss += '0' + sum;
    }
    if(flags)
        sss += '1';
    reverse(sss.begin(),sss.end());
    return sss;
}
int main(){
    int n;
    for(int i = 0; i < 10; i ++)
        mp['0'+i] = i;
    arr[0] = "1";arr[1] = "1";
    arr[2] = "2";arr[3] = "4";
    for(int i = 4; i < 1010; i++){
        arr[i] = f(f(arr[i-1], arr[i-2]),arr[i-4]);
    }
    //cout << arr[1000] << endl;
    while(~scanf("%d",&n)){
        cout << arr[n] << endl;
    }
    return 0;
}

度熊面前有一个全是由1构成的字符串，被称为全1序列。你可以合并任意相邻的两个1，从而形成一个新的序列。对于给定的一个全1序列，请计算根据以上方法，可以构成多少种不同的序列。

Input这里包括多组测试数据，每组测试数据包含一个正整数 $N$ 对于每组测试数据，输出一个整数，代表由题目中所给定的全1序列所能形成的新序列的数量。

Sample Input

1
3
5

Sample Output

1
3
8

这题的规律就是a[n] = a[n-1] + a[n-2] 不过数字有点大，要用到大数加法。
下面是我的代码：

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <map>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8 map<char,int> mp;
 9 vector<int> v;
10 string f(string s,string ss){
11     reverse(s.begin(),s.end());
12     reverse(ss.begin(),ss.end());
13     if(s.length()>ss.length())
14         swap(s,ss);
15     int a,b,sum,flags=0;
16     string sss;
17     for(int i=0;i<ss.length();++i){
18         if(i>=s.length())
19             a=0;
20         else a=mp[s[i]];
21         b=mp[ss[i]];
22         sum=a+b+flags;
23         if(sum>=10){
24             sum-=10;
25             flags=1;
26         }
27         else flags=0;
28       //  v.push_back(sum);
29         sss += '0' + sum;
30     }
31     if(flags)
32         sss += '1';
33     reverse(sss.begin(),sss.end());
34     return sss;
35 }
36 
37 int main(){
38     for(int i = 0; i < 10; i ++){
39         mp['0'+i] = i;
40     }
41     string arr[210];
42     //cout << f("111","222")<< endl;
43     arr[1] = "1"; arr[2] = "2";
44     for(int i = 3; i < 201; i++){
45         arr[i] = f(arr[i-1], arr[i-2]);
46     }
47     int n;
48     while(cin >> n){
49         cout << arr[n] << endl;
50     }
51     return 0;
52 }

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N，用一行输出相应的K。

Sample Input

1
7 3

Sample Output

8

典型的递归问题，把问题拆分成一个一个的小问题然后在说答案，下面是我的代码：

 1 #include <iostream>
 2 #define ll long long
 3 using namespace std;
 4 ll f(int m, int n){
 5     int ans = 0;
 6     if(m==0 || n==1) return 1;
 7     if(n > m) return f(m, m);
 8     else return f(m, n -1) + f(m-n, n);
 9 }
10 int main(){
11     int t, m, n;
12     cin >> t;
13     while(t--){
14         cin >> m >> n;
15         cout << f(m, n) << endl;
16     }
17     return 0;
18 }