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

2019-11-17 05:48:56

字體：大中小

來源：轉載

供稿：網友

                              用遞歸法解決商人渡河問題                                           作者：曹開銳        遞歸確實是一種很了不起的方法，但是我感覺實在是太難把握了，遞歸法可以用棧轉換成為非遞歸法，但是遞歸法可以使程序簡單，用遞歸法解決的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)
    {
                pointer=pointer->next;
    }
    getch();
}