递推与递归

递推与递归

一 实验目的
        1. 掌握用递推方法建立问题的求解模型

2. 掌握用递归方法建立问题的求解模型

3. 掌握递推与递归的程序编写、调试与测试

二 实验设备

        一台PC机，Visual C++ 6.0开发环境

三 实验内容

1. Children’s Queue  

l 题目描述：

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?

l 输入：

There 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)

l 输出：

For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.

l 输入样例：

1

2

3

l 输出样例

1

2

4

2. 错排问题

l 题目描述：

大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！
做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。
话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。
不幸的是，这种小概率事件又发生了，而且就在我们身边：
事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！
现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？

l 输入：

输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=20），n表示8006的网友的人数。

l 输出：

对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。

l 输入样例：

2

3

l 输出样例

1

2

3. 数字旋转方阵

l 题目描述：

编程输出如图所示的数字旋转方阵。

file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml9532\wps6.png

l 输入：

输入数据有若干行，每行有一个整数(n < =30).

l 输出：

一个n*n的数字旋转方阵

l 输入样例：

5

6

l 输出样例

file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml9532\wps2.png

file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml9532\wps3.png

四 实验结果

1. 解题思路：

源程序：

1. #include<iostream>
   
2. using namespace std;
   
3. int mat[1001][246];
   
4. int main()
   
5. {
   
6. int i,j,k;
   
7. int n,m;
   
8. int flag,temp;
   
9. int re,pr;
   
10.         mat[1][0]=1;
    
11.   mat[2][0]=2;
    
12.   mat[3][0]=4;
    
13.   mat[4][0]=7;
    
14.   for(i=5;i<=1001;i++)
    
15.   {
    
16.    temp=0;
    
17.    for(j=0;j<246;j++)
    
18.    {
    
19.     mat[ i][j]=mat[i-1][j]+mat[i-2][j]+mat[i-4][j]+temp;
    
20.     temp=0;
    
21.     if(mat[ i][j]>9)
    
22.     {
    
23.      temp=mat[ i][j]/10;
    
24.      mat[ i][j]=mat[ i][j]%10;
    
25.     }
    
26.    }
    
27. 
    
28.   }
    
29. 
    
30. while(scanf("%d",&n)!=EOF)
    
31. {  
    
32.   flag=0;
    
33.   for(i=245;i>=0;i--)
    
34.   {
    
35.    if(!flag&&mat[n][ i]) flag=1;
    
36.    if(flag) printf("%d",mat[n][ i]);
    
37.   }
    
38.   printf("\n");
    
39. }
    
40. 
    
41. return 0;
    
42. }
    
43. 
    
44. 
    
45. 2. 解题思路：
    
46. 源程序：#include<iostream>
    
47. #include<string>
    
48. using namespace std;
    
49. string StringAdd(string a,string b){
    
50.     int maxlen=a.length()>b.length()?a.length()+1:b.length()+1,carry=0,i,result;  
    
51.     string sum="";
    
52.     while(a.length()<maxlen)
    
53.         a="0"+a;
    
54.     while(b.length()<maxlen)  
    
55.         b="0"+b;
    
56.     while(sum.length()<maxlen)
    
57.         sum="0"+sum;
    
58.     for(i=maxlen-1;i>0;i--){
    
59.         result=a[ i]+b[ i]-2*'0'+carry;
    
60.         sum[ i]=result%10+'0';
    
61.         carry=result/10;
    
62.     }
    
63.     sum[0]=carry+'0';
    
64.     while(sum[0]=='0' && sum.length()>1)  
    
65.         sum.erase(0,1);
    
66.     return sum;
    
67. }
    
68. 
    
69. string StringAndNumberMultiply(string a,int n){
    
70.     if(n==0) return "0";
    
71.     string sum=a;
    
72.     n--;
    
73.     while(n--)
    
74.         sum=StringAdd(sum,a);
    
75.     return sum;
    
76. }
    
77. 
    
78. int main(){
    
79.     int i;
    
80.     string lib[21]={"0","0","1"};
    
81.     for(i=3;i<21;i++)
    
82.         lib[ i]=StringAndNumberMultiply(StringAdd(lib[i-1],lib[i-2]),i-1);
    
83.     while(cin>>i)
    
84.         cout<<lib[ i]<<endl;
    
85.     return 0;
    
86. }
    
87. 
    
88. 
    
89. 
    
90. 3. 解题思路：
    
91. 源程序：#include<stdio.h>
    
92. int a[11][11],i,j,num,size;
    
93. int xuanzhuan(int n)
    
94. {
    
95.         if(n==0)return 0;
    
96.         if(n==1)
    
97.         {
    
98.                 a[ i][j]=num++;
    
99.                 return 0;
    
100.         }               
     
101.         for(int k=1;k<n;k++){//粉色方向
     
102.                 a[ i][j]=num++;
     
103.         i++；
     
104.         }
     
105.         for(int k=1;k<n;k++){//蓝色方向
     
106.                 a[ i][j]=num++;
     
107.                 j++；
     
108.         }
     
109.         for(int k=1;k<n;k++){
     
110.                 //红色方向
     
111.                 a[ i][j]=num++;
     
112. i--；
     
113.         }
     
114.         for(int k=1;k<n;k++){
     
115.                 //黄色方向
     
116.                 a[ i][j]=num++;
     
117.                 j--；
     
118.         }
     
119.         i++;                 //注意用i++和j++来调整下一次递归时的起点
     
120.         j++;                  //第一圈的起点为图中的1位置，第二圈的起点为图中21位置，第三次在33
     
121.         xuanzhuan(n-2);                        //下次循环时边长-2
     
122. }
     
123. int main()
     
124. {
     
125.         i=j=1;
     
126.         num=1;
     
127.         printf("请输入旋转数组的边长(1到10之间):\n");
     
128.         scanf("%d",&size);
     
129.         xuanzhuan(size);
     
130.         for(int i=1;i<=size;i++)//打印存储好的数组
     
131.         {
     
132.                 for(int j=1;j<=size;j++)
     
133.                         printf("%3d ",a[ i][j]);
     
134.                 printf("\n");
     
135.         }
     
136. return 0;
     
137. }

复制代码