|
遞推與遞歸 一 實驗目的
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. 解題思路： 源程序：
- #include<iostream>
- using namespace std;
- int mat[1001][246];
- int main()
- {
- int i,j,k;
- int n,m;
- int flag,temp;
- int re,pr;
- mat[1][0]=1;
- mat[2][0]=2;
- mat[3][0]=4;
- mat[4][0]=7;
- for(i=5;i<=1001;i++)
- {
- temp=0;
- for(j=0;j<246;j++)
- {
- mat[ i][j]=mat[i-1][j]+mat[i-2][j]+mat[i-4][j]+temp;
- temp=0;
- if(mat[ i][j]>9)
- {
- temp=mat[ i][j]/10;
- mat[ i][j]=mat[ i][j]%10;
- }
- }
- }
- while(scanf("%d",&n)!=EOF)
- {
- flag=0;
- for(i=245;i>=0;i--)
- {
- if(!flag&&mat[n][ i]) flag=1;
- if(flag) printf("%d",mat[n][ i]);
- }
- printf("\n");
- }
- return 0;
- }
- 2. 解題思路：
- 源程序：#include<iostream>
- #include<string>
- using namespace std;
- string StringAdd(string a,string b){
- int maxlen=a.length()>b.length()?a.length()+1:b.length()+1,carry=0,i,result;
- string sum="";
- while(a.length()<maxlen)
- a="0"+a;
- while(b.length()<maxlen)
- b="0"+b;
- while(sum.length()<maxlen)
- sum="0"+sum;
- for(i=maxlen-1;i>0;i--){
- result=a[ i]+b[ i]-2*'0'+carry;
- sum[ i]=result%10+'0';
- carry=result/10;
- }
- sum[0]=carry+'0';
- while(sum[0]=='0' && sum.length()>1)
- sum.erase(0,1);
- return sum;
- }
- string StringAndNumberMultiply(string a,int n){
- if(n==0) return "0";
- string sum=a;
- n--;
- while(n--)
- sum=StringAdd(sum,a);
- return sum;
- }
- int main(){
- int i;
- string lib[21]={"0","0","1"};
- for(i=3;i<21;i++)
- lib[ i]=StringAndNumberMultiply(StringAdd(lib[i-1],lib[i-2]),i-1);
- while(cin>>i)
- cout<<lib[ i]<<endl;
- return 0;
- }
- 3. 解題思路：
- 源程序：#include<stdio.h>
- int a[11][11],i,j,num,size;
- int xuanzhuan(int n)
- {
- if(n==0)return 0;
- if(n==1)
- {
- a[ i][j]=num++;
- return 0;
- }
- for(int k=1;k<n;k++){//粉色方向
- a[ i][j]=num++;
- i++；
- }
- for(int k=1;k<n;k++){//藍色方向
- a[ i][j]=num++;
- j++；
- }
- for(int k=1;k<n;k++){
- //紅色方向
- a[ i][j]=num++;
- i--；
- }
- for(int k=1;k<n;k++){
- //黃色方向
- a[ i][j]=num++;
- j--；
- }
- i++; //注意用i++和j++來調整下一次遞歸時的起點
- j++; //第一圈的起點為圖中的1位置，第二圈的起點為圖中21位置，第三次在33
- xuanzhuan(n-2); //下次循環時邊長-2
- }
- int main()
- {
- i=j=1;
- num=1;
- printf("請輸入旋轉數組的邊長(1到10之間):\n");
- scanf("%d",&size);
- xuanzhuan(size);
- for(int i=1;i<=size;i++)//打印存儲好的數組
- {
- for(int j=1;j<=size;j++)
- printf("%3d ",a[ i][j]);
- printf("\n");
- }
- return 0;
- }
| 
