找回密碼
 立即注冊(cè)

QQ登錄

只需一步，快速開(kāi)始

帖子
查看: 2436|回復(fù): 0
收起左側(cè)

遞推與遞歸

[復(fù)制鏈接]
ID:670425 發(fā)表于 2019-12-22 14:30 | 顯示全部樓層 |閱讀模式
遞推與遞歸
一 實(shí)驗(yàn)?zāi)康?/font>
        1. 掌握用遞推方法建立問(wèn)題的求解模型
2. 掌握用遞歸方法建立問(wèn)題的求解模型
3. 掌握遞推與遞歸的程序編寫、調(diào)試與測(cè)試
二 實(shí)驗(yàn)設(shè)備
        一臺(tái)PC機(jī)，Visual C++ 6.0開(kāi)發(fā)環(huán)境
三 實(shí)驗(yàn)內(nèi)容
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. 錯(cuò)排問(wèn)題

l 題目描述：
大家常常感慨，要做好一件事情真的不容易，確實(shí)，失敗比成功容易多了！
做好“一件”事情尚且不易，若想永遠(yuǎn)成功而總從不失敗，那更是難上加難了，就像花錢總是比掙錢容易的道理一樣。
話雖這樣說(shuō)，我還是要告訴大家，要想失敗到一定程度也是不容易的。比如，我高中的時(shí)候，就有一個(gè)神奇的女生，在英語(yǔ)考試的時(shí)候，竟然把40個(gè)單項(xiàng)選擇題全部做錯(cuò)了！大家都學(xué)過(guò)概率論，應(yīng)該知道出現(xiàn)這種情況的概率，所以至今我都覺(jué)得這是一件神奇的事情。如果套用一句經(jīng)典的評(píng)語(yǔ)，我們可以這樣總結(jié)：一個(gè)人做錯(cuò)一道選擇題并不難，難的是全部做錯(cuò)，一個(gè)不對(duì)。
不幸的是，這種小概率事件又發(fā)生了，而且就在我們身邊：
事情是這樣的——HDU有個(gè)網(wǎng)名叫做8006的男性同學(xué)，結(jié)交網(wǎng)友無(wú)數(shù)，最近該同學(xué)玩起了浪漫，同時(shí)給n個(gè)網(wǎng)友每人寫了一封信，這都沒(méi)什么，要命的是，他竟然把所有的信都裝錯(cuò)了信封！注意了，是全部裝錯(cuò)喲！
現(xiàn)在的問(wèn)題是：請(qǐng)大家?guī)涂蓱z的8006同學(xué)計(jì)算一下，一共有多少種可能的錯(cuò)誤方式呢？

l 輸入：
輸入數(shù)據(jù)包含多個(gè)多個(gè)測(cè)試實(shí)例，每個(gè)測(cè)試實(shí)例占用一行，每行包含一個(gè)正整數(shù)n（1<n<=20），n表示8006的網(wǎng)友的人數(shù)。
l 輸出：
對(duì)于每行輸入請(qǐng)輸出可能的錯(cuò)誤方式的數(shù)量，每個(gè)實(shí)例的輸出占用一行。
l 輸入樣例：
2
3
l 輸出樣例
1
2

3. 數(shù)字旋轉(zhuǎn)方陣
l 題目描述：
編程輸出如圖所示的數(shù)字旋轉(zhuǎn)方陣。
file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml9532\wps6.png
l 輸入：
輸入數(shù)據(jù)有若干行，每行有一個(gè)整數(shù)(n < =30).
l 輸出：
一個(gè)n*n的數(shù)字旋轉(zhuǎ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

四 實(shí)驗(yàn)結(jié)果
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.    }

  28.   }

  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. }

  41. return 0;
  42. }


  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. }

  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. }

  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. }



  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++){//藍(lán)色方向
  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++來(lái)調(diào)整下一次遞歸時(shí)的起點(diǎn)
  120.         j++;                  //第一圈的起點(diǎn)為圖中的1位置，第二圈的起點(diǎn)為圖中21位置，第三次在33
  121.         xuanzhuan(n-2);                        //下次循環(huán)時(shí)邊長(zhǎng)-2
  122. }
  123. int main()
  124. {
  125.         i=j=1;
  126.         num=1;
  127.         printf("請(qǐng)輸入旋轉(zhuǎn)數(shù)組的邊長(zhǎng)(1到10之間):\n");
  128.         scanf("%d",&size);
  129.         xuanzhuan(size);
  130.         for(int i=1;i<=size;i++)//打印存儲(chǔ)好的數(shù)組
  131.         {
  132.                 for(int j=1;j<=size;j++)
  133.                         printf("%3d ",a[ i][j]);
  134.                 printf("\n");
  135.         }
  136. return 0;
  137. }
復(fù)制代碼


回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表