計算機程序設(shè)計基礎(chǔ)-第八講

力

A

討論問題“下樓問

從樓上走到樓下共有h個臺階，每一步有三種走法

A走一個臺階；

A走二個臺階；

A走三個臺階。

問可走出多少種方案，希望用遞歸思想來編程。

2

定義：

>Try(i,s)——站在第i級臺階上往下試走第s步的過程

>2,3—在每一步可以試著走的臺階數(shù)

Atake[s]----存儲第s步走過的臺階數(shù)

>i<j——說明第i級臺階已比要走的j級臺階小，j不

可取▼

>i>j——說明站在第i級臺階上可試走j個臺階為一步

>i==j——說明這一步走完后已到了樓下，這時一條

下樓方案已試成，即可輸出這一方案了

3

思在各：

1、用枚舉的方法，試著一步一步地走，從高到低，讓i

先取h值從樓上走到樓下，每走一步i的值會減去每一

步所走的臺階數(shù)j,即i*(初值)，以后；i-j,

(j=1,2,3),當i二。時，說明已走到樓下。

2、枚舉時，每一步都要試j或者是為1,或是為2,或是

為3。這時可用for循環(huán)結(jié)構(gòu)。

3、每一步走法都用相同的策略，故可以用遞歸算法。

4

在上圖中，A結(jié)點是被遞歸調(diào)用的結(jié)點，

形式參數(shù)為i,s,A結(jié)點為一個與結(jié)點，

進入B結(jié)點時的三個參數(shù)為i,s,產(chǎn)3；進

入C結(jié)點的參數(shù)為i,s,j=2；進入D結(jié)點

的參數(shù)為i,s,j=1。Lp是三個結(jié)點都可

用的循環(huán)體Lp。

Lp是一個分支結(jié)構(gòu)的或結(jié)點。

6

(1)當i〈j時，說明第i級已經(jīng)比一步該走的臺階數(shù)

小了。這是一個直接可解結(jié)點E,什么也不做。

(2)當i>=j時,要做相關(guān)聯(lián)的G和H,G是直接可解

結(jié)點，將第s步走過的臺階數(shù)j記入take數(shù)組，即

take[s]=j；接著做H,H為或結(jié)點，有兩個分支：

其一是：當i=j時,說明經(jīng)過第s步，已走到樓下，

輸出該下樓行走方案，并將方案號加1；

其二是：當i>j時，說明經(jīng)過第s步，尚未走到樓下,

尚需再試第s+1步的走法，注意這時站在第i-j級

臺階上。因此要調(diào)用try(i-j,s+1)o

7

for(j=3;j>0;j=j-l)

take[s]=j;

num=num+1;

輸出第num方案下的從第

1步到第s步的走法

8

#include<stdio.h>〃預(yù)編譯命令

inttakefll];〃定義全局變量：數(shù)組take,方案數(shù)num

intnum=0;

voidtry(inti,ints)〃被調(diào)用函數(shù)

intj,k;//定義整型變量j表示每步允許走的臺階數(shù),

〃㈤臨時變量

forQ=3;j>0;j=j-l)//循環(huán)

{〃循環(huán)體開始

if(i<j)〃如果所剩臺階數(shù)小于允許走的臺階數(shù)j,

!〃什么也不做

//else

else〃以下是i>=j的情況

(

take[s]=j;〃記錄第s步走j個臺階

if(i==j)//如果已經(jīng)到了樓下，做下列事情

{,_

num=num+1;//方案數(shù)加1

printf("方案％(1:n,num);//輸出方案數(shù)

for(k=l;k<=s;k=k+l)〃輸出本方案的每一步

{〃所走的臺階數(shù)

printf(n%dM,take[k]);

printf(H\nn);//換行

}

else〃尚未走到樓下

{

try(i-j,s+1);〃再試剩下的臺階(遞歸調(diào)用)

10

}〃循環(huán)體結(jié)束

)〃函數(shù)體結(jié)束

voidmain()〃主函數(shù)

inth;//定義整型變量h是樓梯的臺階數(shù)

printf(“請輸入樓梯的臺階數(shù)：")；//提示信息

scanf(ff%d!\&h);〃輸入樓梯的臺階數(shù)

try(h,l)；//調(diào)用函數(shù)try(h,l)

printf(“總方案數(shù)：%d\nn,num);〃輸出總方案數(shù)

11

2

八皇后問題

13

在8義8的棋盤上，放置8個皇后(棋子)，使兩兩之

間互不攻擊。所謂互不攻擊是說任何兩個皇后都

要滿足：

(1)不在棋盤的同一行；

(2)不在棋盤的同一■列!

(3)不在棋盤的同一對角線上。

因此可以推論出，棋盤共有8行，每行有且僅有一個

皇后，故至多有8個皇后。這8個皇后每個應(yīng)該放

在哪一列上是解該題的任務(wù)。我們還是用試探的

方法“向前走，碰壁回頭”的策略。這就是“回

溯法”的解題思路。

14

1、定義try(i)——試探放第i行上的皇后。

2、討論將第i行上的皇后放在j列位置上的安全性。

我們可以逐行地放每一個皇后，因此，在做這一

步時，假定第i行上還沒有皇后，不會在行上遭到

其它皇后的攻擊。只考慮來自列和對角線的攻擊。

我們定義q⑴司表示第i行上的皇后放在第j列，

一旦這樣做了，就要考慮第i個皇后所在的列不安

全了，這時讓C[J]=false,同時，要考慮通過

(i,j)位置的兩條對角線也不安全了。分析看出從

左上到右下的對角線上的每個位置都有i-＞常數(shù)

的特點；從左下到右上的對角線上的每個位置都

有i+產(chǎn)常數(shù)的特點。比如下圖的兩條對角線上的

點，一條有i—j=7,一條有i+j=7的特點。

15

8

利用這個特點，我們可以令

L[i-j]=false;

R[i+j]=false;

來表示在(i,j)位置放皇后之后，通過該位置的兩條

對角線上不安全了。

這樣我彳門得出了在(i,j)位置放皇后的安全條件為

為了判斷安全條件，在程序中要用到三個數(shù)組

(1)C[j]為布爾型的,產(chǎn)1,2,…,8,初始化時全部

置為true；

(2)L[k]為布爾型的,k=i-j,k=-7,-6,7,初始

化時全部置為true；

(3)R[m]為布爾型的,m=i+j,m=2,3,...,16,初始

化時全部直為true；1；

3、從思路上，在放第i個皇后時（當然在第i行），選第j列,

當nq為true時，就可將皇后放在（i,j）位置，這時做如下3

件事

（1）放皇后q[i]=j,同時讓第j列和過（i,j）位置的兩條對角

線變?yōu)椴话踩?。即?/p>

C[j]=false;L[i-j]=false;R[i+j]=false;

（2）之后查一下i是否為8,如果為8,則表明已經(jīng)放完8個皇

后，這時讓方案數(shù)Num加1,輸出該方案下8個皇后在棋盤上

的位置。否則，未到8個，還要讓皇后數(shù)i加1再試著放，這