zl_4.c

用递归法解决商人渡河问题

用递归法解决商人渡河问题  
 


 


                              用递归法解决商人渡河问题

                                           作者：曹开锐

        递归确实是一种很了不起的方法，但是我感觉实在是太难掌握了，递归法可以用栈转换成为非递归法，但是递归法可以使程序简单，用递归法解决的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\n",pointer->x,pointer->y,pointer->state);
        pointer=pointer->next;
    }
    getch();
}