用遞歸法解決商人渡河問題

用遞歸法解決商人渡河問題

作者:曹開銳

遞歸確實是一種很了不起的方法,但是我感覺實在是太難把握了,遞歸法可以用棧轉換成爲非遞歸法,但是遞歸法可以使程序簡單,用遞歸法解決的n皇後問題,還有漢諾塔問題,迷宮問題。。。。。。

商人渡河問題是這樣的:有三個商人,三個強盜,和一條船(船每次只可以載小于等于兩個人)他們同在河的一邊,想渡過河去,但是必須保證在河的任何一邊必須保證商人的數目大于等于強盜的數目,應該怎麽過這條河呢?

用遞歸的源程序如下:

開始時商人,強盜所在的河的這邊設爲0狀態,另一邊設爲1狀態(也就是船開始時的一邊設爲0,當船駛到對岸是設爲1狀態,在這兩個狀態時,都必須符合條件)

#include<stdlib.h>

strUCt node /*建立一個類似棧的數據結構並且可以浏覽每一個數據點*/

{

int x;

int y;

int state;

struct node *next;

};

typedef struct node state;

typedef state *link;

link PPointer1=NULL;

link PPointer2=NULL;

int a1,b1;

int a2,b2;

/*棧中每個數據都分爲0,1狀態*/

void Push(int a,int b,int n)

{

link newnode;

newnode=(link)malloc(sizeof(state));

newnode->x=a;

newnode->y=b;

newnode->state=n;

newnode->next=NULL;

if(PPointer1==NULL)

{

PPointer1=newnode;

PPointer2=newnode;

}

else

{

PPointer2->next=newnode;

PPointer2=newnode;

}

}

void Pop() /*彈棧*/

{

link pointer;

if(PPointer1==PPointer2)

{

free(PPointer1);

PPointer1=NULL;

PPointer2=NULL;

}

pointer=PPointer1;

while(pointer->next!=PPointer2)

pointer=pointer->next;

free(PPointer2);

PPointer2=pointer;

PPointer2->next=NULL;

}

int history(int a,int b,int n) /*比較輸入的數據和棧中是否有重複的*/

{

link pointer;

if(PPointer1==NULL)

return 1;

else

{

pointer=PPointer1;

while(pointer!=NULL)

{

if(pointer->x==a&&pointer->y==b&&pointer->state==n)

return 0;

pointer=pointer->next;

}

return 1;

}

}

int judge(int a,int b,int c,int d,int n) /*判定這個狀態是否可行,其中使用了history函數*/

{

if(history(a,b,n)==0) return 0;

if(a>=0&&b>=0&&a<=3&&b<=3&&c>=0&&d>=0&&c<=3&&d<=3&&a+c==3&&b+d==3)

{

switch(n)

{

case 1:

{

if(a==3)

{

Push(a,b,n);

return 1;

}

else if(a==0)

{

Push(a,b,n);

return 1;

}

else if(a==b)

{

Push(a,b,n);

return 1;

}

else return 0;

}

case 0:

{

if(a==3)

{

Push(a,b,n);

return 1;

}

else if(a==0)

{

Push(a,b,n);

return 1;

}

else if(a>=b)

{

Push(a,b,n);

return 1;

}

else return 0;

}

}

}

else return 0;

}

int Duhe(int a,int b,int n) /*遞歸法解決商人渡河問題,假如這一個狀態符合*/

{ /*則判定下一個狀態,直至問題解決*/

if(a==0&&b==0) return 1;

if(n==0) /*判定0狀態時,商匪狀態是否符合要求*/

{

if(judge(a-1,b-1,4-a,4-b,1))

{

if(Duhe(a-1,b-1,1)==1)

return 1;

}

if(judge(a,b-2,3-a,5-b,1))

{

if(Duhe(a,b-2,1)==1)

return 1;

}

if(judge(a-2,b,5-a,3-b,1))

{

if(Duhe(a-2,b,1)==1)

return 1;

}

if(judge(a-1,b,4-a,3-b,1))

{

if(Duhe(a-1,b,1)==1)

return 1;

}

if(judge(a,b-1,3-a,4-b,1))

{

if(Duhe(a,b-1,1)==1)

return 1;

}

else

{

Pop(0);

return 0;

}

}

if(n==1) /*判定0狀態時,商匪狀態是否符合要求*/

{

if(judge(a+1,b+1,2-a,2-b,0))

{

if(Duhe(a+1,b+1,0)==1)

return 1;

}

if(judge(a,b+2,3-a,1-b,0))

{

if(Duhe(a,b+2,0)==1)

return 1;

}

if(judge(a+2,b,1-a,3-b,0))

{

if(Duhe(a+2,b,0)==1)

return 1;

}

if(judge(a+1,b,2-a,3-b,0))

{

if(Duhe(a+1,b,0)==1)

return 1;

}

if(judge(a,b+1,3-a,2-b,0))

{

if(Duhe(a,b+1,0)==1)

return 1;

}

else

{

Pop(1);

return 0;

}

}

return 0;

}

main()

{

link pointer;

Push(3,3,0);

Duhe(3,3,0);

pointer=PPointer1;

while(pointer!=NULL)

{

printf("%d,%d---%d ",pointer->x,pointer->y,pointer->state);

pointer=pointer->next;

}

getch();

}

非遞歸解決組合問題
從m 個互不相同元素中取 n 個元素,一般選用遞歸或回溯算法解決,本文旨在利用進制轉換的方法達到這一目的。代碼如下 Sub GETALL(ByVal num As Integer, ByRef x As Variant, ByRef RESULT() As String, Optional...查看完整版>>非遞歸解決組合問題
 
非遞歸解決組合問題
從m 個互不相同元素中取 n 個元素,一般選用遞歸或回溯算法解決,本文旨在利用進制轉換的方法達到這一目的。代碼如下 Sub GETALL(ByVal num As Integer, ByRef x As Variant, ByRef RESULT() As String, Optional...查看完整版>>非遞歸解決組合問題
 
用彙編與c解決遞歸問題之比較
用彙編與c解決遞歸問題之比較 owlbird 事先聲明不是有意刺激大家,絕沒有打擊大家學習彙編語言的高漲熱情,只是由于用彙編...查看完整版>>用彙編與c解決遞歸問題之比較
 
八皇後問題的非遞歸實現
  我們都知道八皇後問題是一個很經典的問題,當時很多解決八皇後問題的編程解法都是用遞歸解法,下面我用非遞歸的解法來實現如下:...查看完整版>>八皇後問題的非遞歸實現
 
HANOI塔問題的遞歸解
HANOI塔問題是《數據結構》中用來介紹遞歸算法的最典型的例題。 本程序可同時將HANOI塔問題的解題步驟的中間結果顯示在屏幕上和保存在文本文件中。(後一點對于顯示結果很多無法在一屏中顯示時,非凡有用) 程...查看完整版>>HANOI塔問題的遞歸解
 
八皇後問題遞歸算法 + Pascal 程序
[這個貼子最後由cinc在 2002/09/11 01:58pm 編輯]在網上找到的一個 八皇後問題的 pascal 解法。可以參考參考:八皇後問題--------------------------------------------------------------------------------〖問題描...查看完整版>>八皇後問題遞歸算法 + Pascal 程序
 
STL學習筆記:用非遞歸的方法實現漢諾塔問題
STL學習筆記:用非遞歸的方法實現漢諾塔問題 shaohui_1983#163.com http://blog.csdn.net/shaohui 早就想寫篇關于用非遞歸的方法解決漢諾塔問題的文章,但是一直都沒有時間去研究這個。最近學了點STL,但是一直都沒有...查看完整版>>STL學習筆記:用非遞歸的方法實現漢諾塔問題
 
分治與遞歸策略_整數劃分問題
// 將一個正整數n表示成一系列正整數之和,// n = n1 + n2 + ... + nk ( 其中, n1 >= n2 >= ... >= nk , k >= 1 )// 正整數n的一個這種表示稱爲正整數n的一個劃分。// 正整數n的不同的劃分個數稱爲正整...查看完整版>>分治與遞歸策略_整數劃分問題
 
皇後問題之C#版(非遞歸)
/* *Author:Junyi Sun @CCNU* E-mail:fxsjy@yahoo.com.cn*/using System;namespace sunjoy{ public class Queen { public static int Main() { int board_size = 0,x=0,y=0;//棋盤大...查看完整版>>皇後問題之C#版(非遞歸)
 
 
回到王朝網路移動版首頁