c語言-遞歸算法

計算機(jī)語言與程序設(shè)計諶衛(wèi)軍清華大學(xué)軟件學(xué)院IntroductiontoComputerProgramming第八章遞歸算法132基本概念基于回溯策略的遞歸基于分治策略的遞歸從前有座山，山上有座廟，廟里有一個老和尚和一個小和尚，老和尚正在給小和尚講故事。講的是什么故事呢？他說，從前……Recursion-See

"Recursion".

"Inordertounderstandrecursion,onemustfirstunderstandrecursion."C語言允許嵌套地調(diào)用函數(shù)，也就是說，在調(diào)用一個函數(shù)的過程中，又去調(diào)用另一個函數(shù)。函數(shù)的嵌套調(diào)用voidmain(){…

study_english();

…}voidstudy_english(){reading();listening();

writing()}voidlistening(){

………}函數(shù)的嵌套調(diào)用有一個特例，即遞歸調(diào)用，也就是說，在調(diào)用一個函數(shù)的過程中，又出現(xiàn)了直接或間接地去調(diào)用該函數(shù)本身。voidtell_story(){intold_monk,young_monk;tell_story(); //tell_story函數(shù)的遞歸調(diào)用}函數(shù)的遞歸調(diào)用?voidtell_story(){staticintold_monk,young_monk;old_monk=old_monk+1;//年齡大了一歲

young_monk=young_monk+1;if(old_monk<=60) //遞歸形式

tell_story();elseprintf("對不起，已退休！");//遞歸邊界}在語法上（簡單）遞歸即為普通的函數(shù)調(diào)用。在算法上（難）如何找到遞歸形式？如何找到遞歸邊界？如何編寫遞歸程序？遞歸算法的類型遞歸算法可以分為兩種類型：基于分治策略的遞歸算法；基于回溯策略的遞歸算法。第八章遞歸算法132基本概念基于回溯策略的遞歸基于分治策略的遞歸分而治之（divide-and-conquer）的算法設(shè)計思想：Divide：把問題劃分為若干個子問題；Conquer：以同樣的方式分別去處理各個子問題；Combine：把各個子問題的處理結(jié)果綜合起來，形成最終的處理結(jié)果。8.2.1

分而治之瑪特露什卡……調(diào)用調(diào)用……調(diào)用調(diào)用……調(diào)用調(diào)用如何編寫基于分治策略的遞歸程序？在算法分析上，要建立分治遞歸的思維方式。在編程實現(xiàn)上，要建立遞歸信心（Totursttherecursion,JerryCain,stanford）。 如何建立分治遞歸的思維方式？基本原則：目標(biāo)驅(qū)動！計算n!：n!=n*(n-1)!，且1!=1。遞歸形式遞歸邊界調(diào)用調(diào)用fact(3)fact(2)fact(1)voidmain(){intn;printf("請輸入一個整數(shù)：");scanf("%d",&n);printf("%d!=%d\n",n,fact(n));}intfact(intn){if(n==1)return(1);else return(n*fact(n-1));}請輸入一個整數(shù)：33!=6調(diào)用和返回的遞歸示意圖

如何建立遞歸信心？函數(shù)的遞歸調(diào)用到底是如何進(jìn)行的呢？在遞歸調(diào)用時，執(zhí)行的是不是相同的代碼？訪問的是不是相同的數(shù)據(jù)？如果是的話，那么大家會不會相互干擾、相互妨礙？main的棧幀m3voidmain(){intm;printf("請輸入一個整數(shù)：");scanf("%d",&m);printf("%d!=%d\n",m,fact(m));}intfact(intn){if(n==1)return(1);else return(n*fact(n-1));}3nfact的棧幀2nfact的棧幀1nfact的棧幀8.2.2

尋找最大值問題描述： 給定一個整型數(shù)組a，找出其中的最大值。如何設(shè)計相應(yīng)的遞歸算法？如何來設(shè)計相應(yīng)的遞歸算法？目標(biāo)：max{a[0],a[1],…a[n-1]}可分解為：max{a[0],max{a[1],…a[n-1]}}另外已知max{x}＝x這就是遞歸算法的遞歸形式和遞歸邊界，據(jù)此可以編寫出相應(yīng)的遞歸函數(shù)。intMax(inta[],intfirst,intn){intmax;if(first==n-1)returna[first];max=Max(a,first+1,n);if(max<a[first])returna[first];elsereturnmax;}Max(a,0,n)調(diào)用Max(a,1,n)調(diào)用…調(diào)用

Max(a,n-1,n)返回返回返回8.2.3

折半查找法問題描述： 查找（Searching）：根據(jù)給定的某個值，在一組數(shù)據(jù)（尤其是一個數(shù)組）當(dāng)中，確定有沒有出現(xiàn)相同取值的數(shù)據(jù)元素。順序查找、折半查找。前提：數(shù)據(jù)是有序排列的；基本思路：將目標(biāo)值與數(shù)組的中間元素進(jìn)行比較；若相等，查找成功。否則根據(jù)比較的結(jié)果將查找范圍縮小一半，然后重復(fù)此過程。412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874請問：4565926是否在此列表當(dāng)中？412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874請問：4565926是否在此列表當(dāng)中？數(shù)組正中間的元素。412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874請問：4565926是否在此列表當(dāng)中？不予考慮412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874請問：4565926是否在此列表當(dāng)中？正中間的元素412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874請問：4565926是否在此列表當(dāng)中？正中間的元素不予考慮4565925？voidmain(){intb[]={05,13,19,21,37,56,64,75,80,88,92};intx=21;printf("x位于數(shù)組的第%d個元素\n",bsearch(b,x,0,10));}如何用遞歸來實現(xiàn)？函數(shù)原型：

intbsearch(intb[],intx,intL,intR);遞歸的形式？遞歸的邊界？問題分析intbsearch(intb[],intx,intL,intR){intmid;if(L>R)return(-1);mid=(L+R)/2;if(x==b[mid])returnmid;elseif(x<b[mid])returnbsearch(b,x,L,mid-1);elsereturnbsearch(b,x,mid+1,R);}8.2.4

漢諾(Hanoi)塔問題相傳在古印度Bramah廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中遵守以下規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上（簡單嗎？若每秒移動一只盤子，需5800億年）ABC怎樣編寫這種程序？思路上還是先從最簡單的情況分析起，搬一搬看，慢慢理出思路。1、在A柱上只有一只盤子，假定盤號為1，這時只需將該盤直接從A搬至C，記為

move

from

A

to

CABC12、在A柱上有二只盤子，1為小盤2為大盤。 分三步進(jìn)行：ABC21movefromA

toB;movefromA

to

C;moveformB

toC;3、在A柱上有3只盤子，從小到大分別為1號，2號，3號。怎么移？ABC213分七步！

分三步進(jìn)行：

move

2

discsfrom

A

to

Busing

C；

movefrom

A

to

C；

move

2

discsfrom

B

to

Cusing

A；ABC2134、在A柱上有n個盤子,從小到大分別為1號、2號、3

號、…、n號。第1步：將1號、2號、…、n-1號盤作為一個整體，

在C的幫助下，從A移至B；第2步：將n號盤從A移至C；第3步：再將1號、2號、…、n-1號盤作為一個整

體，在A的幫助下，從B移至C；

這三步記為：

move

n-1

discsfrom

A

to

Busing

C；

move

1

discsfrom

A

to

C；

move

n-1

discsfrom

B

to

Cusing

A；遞歸形式！定義函數(shù)move(intn,charL,

charM,

char

R);表示move

n

discsfrom

L

to

R

using

M；如果n=1，即表示movefrom

L

to

R；移動的是誰？#include<stdio.h>voidmove(intn,charL,charM,charR);voidmain(){intn;printf("請輸入一個整數(shù)：");scanf("%d",&n);move(n,'A','B','C');}//L:Leftpost,M:Middlepost,R:Rightpostvoidmove(intn,charL,charM,charR){if(n==1)printf("move#1from%cto%c\n",L,R);else{move(n-1,L,R,M);

printf("move#%dfrom%cto%c\n",n,L,R);move(n-1,M,L,R);}}請輸入一個整數(shù)：3move#1fromAtoCmove#2fromAtoBmove#1fromCtoBmove#3fromAtoCmove#1fromBtoAmove#2fromBtoCmove#1fromAtoC一次運行結(jié)果8.2.5

青蛙過河一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個小。我們將青蛙從小到大，用1，2，…，n編號。規(guī)定初始時這隊青蛙只能趴在左岸的石頭L上，按編號一個落一個，小的落在大的上面。不允許大的在小的上面。在小溪中有S根石柱，有y片荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳，如有多只同樣要求按編號一個落一個，大的在下，小的在上，而且必須編號相鄰。對于荷葉只允許一只青蛙落腳，不允許多只在其上。對于右岸的石柱R，與左岸的石柱L一樣允許多個青蛙落腳，但須一個落一個，小的在上，大的在下，且編號相鄰。當(dāng)青蛙從左岸的L上跳走后就不允許再跳回來；同樣，從左岸L上跳至右岸R，或從溪中荷葉或溪中石柱跳至右岸R上的青蛙也不允許再離開。問在已知溪中有S根石柱和y片荷葉的情況下，最多能跳過多少只青蛙？ 這題看起來較難，但是如果我們認(rèn)真分析，理出思路，就可化難為易。思路：1、簡化問題，探索規(guī)律。先從個別再到一般，要善于對多個因素作分解，孤立出一個一個因素來分析，化難為易。2.定義函數(shù)

Jump(S,y)——最多可跳過河的青蛙數(shù)其中： S——河中柱子數(shù)

y——荷葉數(shù)

2

說明：河中有一片荷葉，可以過兩只青蛙，起始時L上有兩只青蛙，1#在2#上面。第一步：1#跳到荷葉上；第二步：2#從L直接跳至R上；第三步：1#再從荷葉跳至R上。如下圖：3.先看簡單情況，河中無柱子：S=0，

Jump(0,y)

當(dāng)y=1時，Jump(0,1)=；

3

說明：河中有兩片荷葉時，可以過3只青蛙。起始時：

1#，2#，3#3只青蛙落在L上，第一步：1#從L跳至葉1上，第二步：2#從L跳至葉2上，第三步：3#從L直接跳至R上，第四步：2#從葉2跳至R上，第五步：1#從葉1跳至R上，采用歸納法：Jump(0,y)=當(dāng)y=2時，

Jump(0,2)=；

y+1；意思是：在河中沒有石柱的情況下，過河的青蛙數(shù)僅取決于荷葉數(shù)，數(shù)目是荷葉數(shù)+1。再看Jump(S,y)

先看一個最簡單情況：S=1，y=1。從圖上看出需要步，跳過只青蛙。

94

1#青蛙從L－>Y；

2#青蛙從L－>S；

1#青蛙從Y－>S；

3#青蛙從L－>Y；

4#青蛙從L－>R；

3#青蛙從Y－>R；

1#青蛙從S－>Y；

2#青蛙從S－>R；

1#青蛙從Y－>R；對于S=1，y=1的情形，從另外一個角度來分析若沒有石柱S，最多可過y+1

=

2只青蛙。有了石柱S后，最多可過2*2=4只青蛙。步驟1：

1#和2#從L－>S；步驟2：

3#和4#從L－>R；步驟3：

1#和2#從S－>R；YSLR①:1#,2#②:3#,4#③:1#,2#YYY對于S=1，y>1的情形若沒有石柱S，最多可過y+1

只青蛙。有了石柱S后，最多可過2*(y+1)只青蛙。步驟1：

前y+1只從L－>S；步驟2：

后y+1只從L－>R；步驟3：

前y+1只從S－>R；YSLR①:前y+1只②:后y+1只③:前y+1只YYY對于S=2，y>1的情形若只有石柱S1，最多可過2*(y+1)

只青蛙。有了石柱S2后，最多可過 只青蛙。YS1LR4*(y+1)S2步驟1：

前2*(y+1)只從L－>S2；步驟2：

后2*(y+1)只從L－>R；步驟3：

前2*(y+1)只從S2－>R；Y,S1Y,S1Y,S1采用歸納法，可得出如下的遞歸形式：Jump(S,y)=2*Jump(S-1,y)；意思是：先讓一半的青蛙利用y片荷葉和S-1根石柱，落在河中剩下的那根石柱上；然后讓另一半的青蛙利用y片荷葉和S-1根石柱，落在右岸的R上面；最后再讓先前的一半青蛙，利用y片荷葉和S-1根石柱，落在右岸的R上面。遞歸邊界：Jump(0,y)=y+1voidmain(){intS,y;printf("請輸入石柱和荷葉的數(shù)目：");scanf("%d%d",&S,&y);printf("最多有%d只青蛙過河\n",Jump(S,y));}intJump(intS,inty){if(S==0)return(y+1);return(2*Jump(S-1,y));}8.2.6

快速排序快速排序的基本思路：1、在數(shù)組a中，有一段待排序的數(shù)據(jù)，下標(biāo)從l到r。2、取a[l]放在變量value中，通過由右、左兩邊對value的取值的比較，為value選擇應(yīng)該排定的位置。這時要將比value大的數(shù)放右邊，比它小的數(shù)放左邊。當(dāng)value到達(dá)最終位置后（如下標(biāo)m），由它劃分了左右兩個集合[l..m-1]、[m+1..r]。然后轉(zhuǎn)第1步，再用相同的思路分別去處理左集合和右集合。令qsort(l,r)表示將數(shù)組元素從下標(biāo)為l到

下標(biāo)為r的共r-l+1個元素進(jìn)行從小到大的

快速排序。目標(biāo)：1、讓value=a[l]2、將value放在a[m]中，lmr3、使a[l],a[l+1],…,a[m-1]<=a[m]4、使a[m]<a[m+1],a[m+2],…,a[r]例子：數(shù)組a當(dāng)中有7個元素等待排序。5261734lr首先，讓value=a[l]=a[0]=5value5a0123456下標(biāo)5261734l第二步，從r=6開始，將a[r]與value進(jìn)行比較。

若a[r]value，則r--，繼續(xù)比較。否則，

a[l]=a[r]，l++。value5ra0123456下標(biāo)4l4261734第三步，從l=1開始，將a[l]與value進(jìn)行比較。

若a[l]value，則l++，繼續(xù)比較。否則，

a[r]=a[l]，r--。value5ra0123456下標(biāo)ll6r4261736又回到第二步，從r=5開始，將a[r]與value進(jìn)行比較。若a[r]value，則r--，繼續(xù)比較。否則

a[l]=a[r]，l++。value5a0123456下標(biāo)lr3l4231736又回到第三步，從l=3開始，將a[l]與value進(jìn)行比較。若a[l]value，則l++，繼續(xù)比較。否則，a[r]=a[l]，r--。value5a0123456下標(biāo)rll7r4231776現(xiàn)在l＝

r，已經(jīng)找到了value的正確位置，把value中的值放回到數(shù)組當(dāng)中。value5a0123456下標(biāo)lr54231576下面的任務(wù)：用剛才介紹的方法，對5左、右兩側(cè)的兩段數(shù)據(jù)，分別進(jìn)行排序。a0123456下標(biāo)×××1324a0123456下標(biāo)lr67×××××a0123456下標(biāo)lr1234567最后的結(jié)果：a0123456下標(biāo)具體實現(xiàn)：幾重循環(huán)語句？參考程序：略……第八章遞歸算法132基本概念基于回溯策略的遞歸基于分治策略的遞歸在程序設(shè)計當(dāng)中，有相當(dāng)一類求一組解、或求全部解或求最優(yōu)解的問題，不是根據(jù)某種確定的計算法則，而是利用試探和回溯（Backtracking）的搜索技術(shù)求解?；厮莘ㄒ彩窃O(shè)計遞歸算法的一種重要方法，它的求解過程實質(zhì)上是一個先序遍歷一棵“狀態(tài)樹”的過程，只不過這棵樹不是預(yù)先建立的，而是隱含在遍歷的過程當(dāng)中。8.3.1

分書問題有五本書，它們的編號分別為1，2，3，4，

5，現(xiàn)準(zhǔn)備分給A,B,C,D,E五個人，每個

人的閱讀興趣用一個二維數(shù)組來加以描述：希望編寫一個程序，輸出所有的分書方案，

讓人人皆大歡喜。假定這5個人對這5本書的閱讀興趣如下表：

1 2 3 4 5ABCDE0011011001011010001001001人書解題思路：1、定義一個整型的二維數(shù)組，將上表中的閱讀喜好

用初始化的方法賦給這個二維數(shù)組。

可定義：intLike[6][6]={{0},{0,0,0,1,1,0},{0,1,1,0,0,1}, {0,0,1,1,0,1},{0,0,0,0,1,0},

{0,0,1,0,0,1}};2、定義一個整型一維數(shù)組BookFlag[6]用來記錄書

是否已被選用。用后五個下標(biāo)作為五本書的標(biāo)號，

被選用的元素值為1,未被選用的值為0,初始化皆為0.intBookFlag[6]={0};3、定義一個整型一維數(shù)組BookTaken[6]用來記錄

每一個人選用了哪一本書。用數(shù)組元素的下標(biāo)來作

為人的標(biāo)號，用數(shù)組元素的值來表示書號。如果某

個人還沒有選好書，則相應(yīng)的元素值為0。初始化

時，所有的元素值均為0。intBookTaken[6]={0};4、循環(huán)變量i表示人，j表示書，i,j{1,2,3,4,5}一種方法：枚舉法。

把所有可能出現(xiàn)的分書方案都枚舉出來，然后逐一判斷它們是否滿足條件，即是否使得每個人都能夠得到他所喜歡的書。缺點：計算量太大。i=1j=1j=2i=2j=3j=5i=3j=1i=3j=2j=4i=4j=2j=4i=4j=5i=5j=4j=5j=5j=2i=5j=4j=2j=1j=4i=4j=5j=1i=5j=4j=1i=3j=5…i=2j=4…如何抽取出

遞歸形式？voidperson(inti);intLike[6][6]={{0},{0,0,0,1,1,0},{0,1,1,0,0,1}, {0,0,1,1,0,1},{0,0,0,0,1,0}, {0,0,1,0,0,1}};intBookFlag[6]={0};intBookTaken[6]={0};voidmain(){person(1);}voidperson(inti) //嘗試給第i個人分書{

intj,k;

for(j=1;j<=5;j++) //嘗試把每本書分給第i個人

{

if((BookFlag[j]!=

0)||(Like[i][j]==0))continue;//失敗

BookTaken[i]=j;//

把第j本書分給第i個人

BookFlag[j]=1;

if(i==5){ //已找到一種分書方案

for(k=1;k<=5;k++)printf("%d",BookTaken[k]);

printf("\n");}

else{

person(i+1); //給第i+1個人分書

}

BookTaken[i]=0; //回溯，把這一次分得的書退回

BookFlag[j]=0;

}}8.3.2

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

走法：走一個臺階；走二個臺階；走三個臺階。問可以走出多少種方案，希望用遞歸思想來

編程。數(shù)據(jù)的定義：

j=1,2,3——表示在每一步可以試著走

的臺階數(shù)

s——表示步數(shù)

i——表示當(dāng)前的高度；

pace[s]——保存第s步走過的臺階數(shù)基本思路：讓i先取h值，然后在下樓時，試著一步一步地走，從高到低。每走一步

i的值就會減去這一步所走的臺階數(shù)

j，即

i=h（初值），以后i=i-j，(j=1,2,3)，當(dāng)

i=0時，說明已走到樓下。每一步都要試

j的三種不同取值，即或者為1，或者為2，或者為3。這時可用for循環(huán)結(jié)構(gòu)。每一步走法都用相同的策略，故可以用遞歸算法。i=4i=3j=1

s=1i=2j=2

s=1i=2j=1

s=2i=1j=2

s=2i=1j=3

s=1i=1j=1

s=3j=1

s=4i=0j=2j=3j=2

s=3i=0j=3j=1

s=3i=0j=2j=3j=3

s=2i=0i=1j=1

s=2

j=1

s=3i=0j=2j=3j=2

s=2i=0j=3

j=1

s=2i=0j=2j=3定義TryStep(i,s)——站在第i級臺階上往下試

走第s步的過程如何實現(xiàn)？

第一步：j=1；第二步：如果j>i,表明這一步不可能走j級臺階,函

數(shù)返回；否則，轉(zhuǎn)第三步；第三步：這一步走j級臺階，即pace[s]=j;

如果i-j=0，說明已經(jīng)到達(dá)地面了，也就是

已經(jīng)找到一種方案了，把它顯示出來；否則

的話，接著走下一步，TryStep(i-j,s+1)；第四步：j=j+1，如果j3，轉(zhuǎn)第二步；否則函數(shù)

結(jié)束。能否用分治策略？8.3.3

八皇后問題在8×8的棋盤上，放置8個皇后（棋子），使兩兩之

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

滿足：（1）不在棋盤的同一行；

（2）不在棋盤的同一列；

（3）不在棋盤的同一對角線上。因此可以推論出，棋盤共有8行，故至多有8個皇后，

即每一行有且僅有一個皇后。這8個皇后中的每一個

應(yīng)該擺放在哪一列上是解該題的任務(wù)?！瓟?shù)據(jù)的定義（1）：

i——第i行（個）皇后，1i8；

j——第j列，1j8；

Queen[i]——第i行皇后所在的列；

Column[j]——第j列是否安全，{0,1}；

1234567812345678數(shù)據(jù)的定義（2）：

Down[-7..7]——記錄每一條從上到下的對

角線，是否安全，{0,1}Up[2..16]——記錄每一條從下到上的對角

角線，是否安全，{0,1}利用以上的數(shù)據(jù)定義：當(dāng)我們需要在棋盤的(i,j)位置擺放一個皇后的時候，可以通過Column數(shù)組、Down

數(shù)組和Up數(shù)組的相應(yīng)元素，來判斷該位置是否安全；當(dāng)我們已經(jīng)在棋盤的(i,j)位置擺放了一個皇后以后，就應(yīng)該去修改Column數(shù)組、Down數(shù)組和Up數(shù)組的相應(yīng)元素，把相應(yīng)的列和對角線設(shè)置為不安全。voidTryQueen(inti);intQueen[9]={0};intColumn[9]={0};intDown[15]={0};intUp[15]={0};voidmain(){TryQueen(1);}voidTryQueen(inti) //擺放第i行的皇后{intj,k;for(j=1;j<=8;j++) //嘗試把該皇后放在每一列

{if(Column[j]||Down[i-j+7]||Up[i+j-2])continue;//失敗

Queen[i]=j;//把該皇后放在第j列上

Column[j]=1;Down[i-j+7]=1;Up[i+j-2]=1;if(i==8) //已找到一種解決方案

{for(k=1;k<=8;k++)printf("%d",Queen[k]);printf("\n");}elseTryQueen(i+1); //擺放第i+1行的皇后

Queen[i]=0; //回溯，把該皇后從第j列拿起

Column[j]=0;Down[i-j+7]=0;Up[i+j-2]=0;

}}共92組解，部分答案如下：方案1：15863724方案2：16837425方案3：17468253方案4：17582463方案5：24683175方案6：25713864方案7：25741863方案8：26174835方案9：26831475方案10：27368514假設(shè)在棋盤上事先已經(jīng)擺放了一個國王，位置為<X,Y>，即第X行第Y列，在擺放八個皇后時，要求皇后間不能互相攻擊且不能被國王攻擊。國王的攻擊范圍如下圖所示：思考題：對題目做如下的修改先輸入某一個皇后所在的位置<X,Y>，即第X行第Y列，在此情形下，如何擺放其余的7個皇后，要求找到所有解決方案。8.3.4

過河問題問題描述：

M條狼和N條狗（N≥M）渡船過河，從河西到河?xùn)|。在每次航行中，該船最多能容納2只動物，且最少需搭載1只動物。安全限制：無論在河?xùn)|、河西還是船上，狗的數(shù)量不能小于狼的數(shù)量。請問：能否找到一種方案，使所有動物都能順利過河。如果能，移動的步驟是什么？如何描述系統(tǒng)的當(dāng)前狀態(tài)？位置：河西岸、河?xùn)|岸、河；對象：船、狼、狗。問題分析三元組（W、D、B）WolfDogBoat例如：(2,2,W)若M＝2、N＝2(2,2,W)(0,2,E)(1,2,W)(0,0,E)(2,0,W)(1,0,E)問題實質(zhì)：在一個有向圖中尋找一條路徑；狀態(tài)轉(zhuǎn)換：如何從一個結(jié)點跳轉(zhuǎn)到另一個結(jié)點；狀態(tài)樹？問題分析如何避免訪問重復(fù)的結(jié)點？如何用簡練的語句實現(xiàn)狀態(tài)的轉(zhuǎn)換？如何將5種情形歸納為同一種形式？技術(shù)難點#include<stdio.h>#defineMAX_M20#defineMAX_N20intM,N;structStatus{intW,D,B;}steps[1000];ints=0,num=0;intflags[MAX_M][MAX_N][2]={0};voidCrossRiver(intW,intD,intB);intIsValid(intw,intd,intb);voidmain(){scanf("%d%d",&M,&N);flags[M][N][0]=1;steps[0].W=M;steps[0].D=N;steps[0].B=0;s=1;CrossRiver(M,N,0);}voidCrossRiver(intW,intD,intB) {inti,j,f;intw,d,b;if(B==0)f=-1;elsef=1;for(j=1;j<=5;j++){switch(j){case1:w=W+f*1;d=D;break;case2:w=W+f*2;d=D;break;case3:d=D+f*1;w=W;break;case4:d=D+f*2;w=W;break;case5:w=W+f*1;d=D+f*1;break;}b=1-B;if(IsValid(w,d,b))

{flags[w][d][b]=1;steps[s].W=w;steps[s].D=d;steps[s].B=b;s++;if(w==0&&d==0&&b==1){num++;printf("Solutions%d:\n",num);for(i=0;i<s;i++)printf("%d%d%d\n",steps[i].W,steps[i].D,steps[i].B);}elseCrossRiver(w,d,b);flags[w][d][b]=0;s--;}}}intIsValid(intw,intd,intb){if(w<0||w>M)return0;if(d<0||d>N)return0;if(flags[w][d][b]==1)return0;if(d>0&&w>d)return0;if((N-d>0)&&(M-w>N-d))return0;return1;}22Solutions1:220021120101200001Solutions2:220021120101110001Solutions3:220111120101200001Solutions4:2201111201011100018.3.5

排列問題n個對象的一個排列，就是把這

n個不同的對象放在同一行上的一種安排。例如，對于三個對象

a,b,c，總共有6個排列：

abc acb bac bca cab cban個對象的排列個數(shù)就是

n!。如何生成排列？基于分治策略的遞歸算法：假設(shè)這n

個對象為1,2,3,…,n；對于前n-1個元素的每一個排列a1a2…an-1，1ai

n-1，通過在所有可能的位置上插入

數(shù)字n，來形成n

個所求的排列，即：

n

a1a2…an-1

a1n

a2…an-1

……

a1a2…n

an-1

a1

a2…an-1n例如：生成1,2,3的所有排列permutation(3)permutation(2)permutation(1)permutation(1)：1permutation(2)：21，12permutation(3)：321，231，213，

312，132，123基于回溯策略的遞歸算法：基本思路：每一個排列的長度為N，對這N個不同的位置，按照順序逐一地枚舉所有

可能出現(xiàn)的數(shù)字。定義一維數(shù)組NumFlag[N+1]用來記錄1-N之間的每一個數(shù)字是否已被使用，1表示已使用，0表示尚未被使用，初始化皆為0；定義一維數(shù)組NumTaken[N+1]，用來記錄每一個位置上使用的是哪一個數(shù)字。如果在某個位置上還沒有選好數(shù)字，則相應(yīng)的數(shù)組元素值為0。初始化時，所有元素值均為0；循環(huán)變量i表示第i個位置，j表示整數(shù)j，

i,j{1,2,…,N}。i=1[]i=2j=1

[1]j=1i=3j=2[12]j=3i=3[13]j=1j=2j=3[123]j=1j=2[132]j=3i=2j=2[2]i=3j=1[21]j=2j=3i=3[23]j=1j=2j=3[213]j=1[231]j=2j=3i=2j=3

[3]i=3j=1[31]j=3j=2i=3[32]j=1j=2[312]j=3j=1[321]j=2,3假定N=3#define N 3voidTryNumber(inti);intNumFlag[N+1]={0};intNumTaken[N+1]={0};main(){TryNumber(1);}voidTryNumber(inti) {intj,k;for(j=1