計算機(jī)程序設(shè)計基礎(chǔ)——第八講PPT學(xué)習(xí)教案

1、會計學(xué)1計算機(jī)程序設(shè)計基礎(chǔ)計算機(jī)程序設(shè)計基礎(chǔ)第八講第八講2從樓上走到樓下共有h個臺階，每一步有三種走法 走一個臺階； 走二個臺階； 走三個臺階。問可走出多少種方案，希望用遞歸思想來編程。第1頁/共20頁3定義： Try(i,s)站在第i級臺階上往下試走第s步的過程 j=1,2,3 在每一步可以試著走的臺階數(shù) takes 存儲第s步走過的臺階數(shù) ij 說明站在第i級臺階上可試走j個臺階為一步 i=j 說明這一步走完后已到了樓下，這時一條下樓方案已試成，即可輸出這一方案了第2頁/共20頁4思路：1、用枚舉的方法，試著一步一步地走，從高到低，讓i先取h值從樓上走到樓下，每走一步i的值會減去每一步所走

2、的臺階數(shù)j，即i=h（初值），以后i=i-j，(j=1,2,3)，當(dāng)i=0時，說明已走到樓下。2、枚舉時，每一步都要試j或者是為1，或是為2，或是為3。這時可用for循環(huán)結(jié)構(gòu)。3、每一步走法都用相同的策略，故可以用遞歸算法。第3頁/共20頁5見圖輸出輸出A try(i,s)i=jtakes=ji=jij第4頁/共20頁6在上圖中，A結(jié)點是被遞歸調(diào)用的結(jié)點，形式參數(shù)為i,s，A結(jié)點為一個與結(jié)點，進(jìn)入B結(jié)點時的三個參數(shù)為i,s,j=3；進(jìn)入C結(jié)點的參數(shù)為i,s,j=2；進(jìn)入D結(jié)點的參數(shù)為i,s,j=1。Lp是三個結(jié)點都可用的循環(huán)體Lp。Lp是一個分支結(jié)構(gòu)的或結(jié)點。第5頁/共20頁7（1）當(dāng)i=j時

3、，要做相關(guān)聯(lián)的G和H，G是直接可解結(jié)點，將第s步走過的臺階數(shù)j記入take數(shù)組，即takes=j；接著做H，H為或結(jié)點，有兩個分支：其一是：當(dāng)i=j時，說明經(jīng)過第s步，已走到樓下，輸出該下樓行走方案，并將方案號加1；其二是：當(dāng)ij時，說明經(jīng)過第s步，尚未走到樓下，尚需再試第s+1步的走法，注意這時站在第i-j級臺階上。因此要調(diào)用try(i-j,s+1)。第6頁/共20頁8 for( j=3; j0; j=j-1) T F ij takes=j; i=j T F num = num + 1; 輸輸出出第第num方方案案下下的的從從第第1 步步到到第第s 步步的的走走法法 try(i-j,s+1)

4、; 第7頁/共20頁9#include / 預(yù)編譯命令int take11; / 定義全局變量：數(shù)組take，方案數(shù)numint num = 0;void try(int i, int s)/ 被調(diào)用函數(shù)int j,k;/ 定義整型變量j表示每步允許走的臺階數(shù), / k臨時變量 for (j = 3; j 0; j = j - 1)/ 循環(huán)/ 循環(huán)體開始if (i =j的情況takes = j;/ 記錄第s步走j個臺階if (i=j) / 如果已經(jīng)到了樓下，做下列事情num = num + 1;/ 方案數(shù)加1printf(方案%d : ,num);/ 輸出方案數(shù)for (k=1; k=s; k

5、=k+1) / 輸出本方案的每一步 / 所走的臺階數(shù)printf(%d ,takek);printf(n);/ 換行else/ 尚未走到樓下try(i-j, s+1);/ 再試剩下的臺階（遞歸調(diào)用）第9頁/共20頁11/ 循環(huán)體結(jié)束/ 函數(shù)體結(jié)束void main()/ 主函數(shù)int h;/ 定義整型變量h是樓梯的臺階數(shù)printf(“請輸入樓梯的臺階數(shù)：); / 提示信息scanf(%d,&h);/ 輸入樓梯的臺階數(shù) try(h,1);/ 調(diào)用函數(shù)try(h,1)printf(總方案數(shù)：%dn,num);/ 輸出總方案數(shù)第10頁/共20頁121 13 3 2 21 11 13 32 21 1

6、2 22 21 11 11 11 14 4第11頁/共20頁13八皇后問題第12頁/共20頁14在88的棋盤上，放置8個皇后（棋子），使兩兩之間互不攻擊。所謂互不攻擊是說任何兩個皇后都要滿足：（1）不在棋盤的同一行；（2）不在棋盤的同一列；（3）不在棋盤的同一對角線上。因此可以推論出，棋盤共有8行，每行有且僅有一個皇后，故至多有8個皇后。這8個皇后每個應(yīng)該放在哪一列上是解該題的任務(wù)。我們還是用試探的方法“向前走，碰壁回頭”的策略。這就是“回溯法”的解題思路。第13頁/共20頁151、定義try(i)試探放第i行上的皇后。2、討論將第i行上的皇后放在j列位置上的安全性。我們可以逐行地放每一個皇后

7、，因此，在做這一步時，假定第i行上還沒有皇后，不會在行上遭到其它皇后的攻擊。只考慮來自列和對角線的攻擊。我們定義q(i)=j表示第i行上的皇后放在第j列，一旦這樣做了，就要考慮第i個皇后所在的列不安全了，這時讓Cj=false，同時，要考慮通過(i,j)位置的兩條對角線也不安全了。分析看出從左上到右下的對角線上的每個位置都有i-j=常數(shù)的特點；從左下到右上的對角線上的每個位置都有i+j=常數(shù)的特點。比如下圖的兩條對角線上的點，一條有i-j=-1，一條有i+j=7的特點。第14頁/共20頁16 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8第15頁/共20頁17利用這個特點，我們

8、可以令Li-j = false;Ri+j = false;來表示在(i,j)位置放皇后之后，通過該位置的兩條對角線上不安全了。這樣我們得出了在(i,j)位置放皇后的安全條件為nq=Cj&Li-j&Ri+j為了判斷安全條件，在程序中要用到三個數(shù)組（1）Cj為布爾型的，j=1,2,8，初始化時全部置為true；（2）Lk為布爾型的，k=i-j,k=-7,-6,7，初始化時全部置為true；（3）Rm為布爾型的，m=i+j,m=2,3,16，初始化時全部置為true；第16頁/共20頁183、從思路上，在放第i個皇后時（當(dāng)然在第i行），選第j列，當(dāng)nq為true時，就可將皇后放在(i,j)位置，這時

9、做如下3件事（1）放皇后qi=j，同時讓第j列和過(i,j)位置的兩條對角線變?yōu)椴话踩?。即讓Cj=false;Li-j=false;Ri+j=false;（2）之后查一下i是否為8，如果為8，則表明已經(jīng)放完8個皇后，這時讓方案數(shù)Num加1，輸出該方案下8個皇后在棋盤上的位置。否則，未到8個，還要讓皇后數(shù)i加1再試著放，這時還要遞歸調(diào)用tri(i+1)。（3）是為了尋找不同方案用的。當(dāng)著一個方案輸出之后，要回溯，將先前放的皇后從棋盤上拿起來，看看還有沒有可能換一處放置。這時要將被拿起來的皇后的所在位置的第j列，和兩條對角線恢復(fù)為安全的。我們用與或圖來描述8皇后問題的解題思路。第17頁/共20頁19try(i+1)try(i+1)A try(i)不安