river cossin.txt

一个关于商人过河的问题

#include<stdio.h>
#include<stdlib.h>
#include<math.h>                                                    /*double pow(x,y)*/


typedef struct S                                                    /*允许状态集合数据类型*/
{
    int x;                                                            /*商人数*/
    int y;                                                            /*随从数*/
    int boat;                                                        /*船位置标志0此岸,1对岸*/
}S;

typedef    struct D                                                    /*允许决策集合数据类型*/
{
    int u;                                                            /*渡船上商人数*/
    int v;                                                            /*渡船上随从数*/
    int flag;                                                        /*5种渡河状态标志*/
                                                                    /*(flag=1:u=1,v=1);(flag=2:u=2,v=0);*/
                                                                    /*(flag=3:u=0,v=2);(flag=4:u=1,v=0);*/
                                                                    /*(flag=5:u=0,v=1)*/
}D;

typedef struct LNode                                                /*状态链表*/
{
    int lx;
    int ly;
    int lboat;
    int lflag;
    struct LNode *front;
    struct LNode *next;
}LNode,*LinkList;



void main()
{
    S s;                                                            /*定义允许状态集合s*/
    LinkList p1,p2,p3,search;
    D d;                                                            /*定义决策状态集合d*/
    int n,k,ok;                                                        /*商人数n,渡河次数k,渡河策略状态allFall*/
    clrscr();
    printf("Displaying System of  Trader & Retinue");
    printf("\n   (C)Copyright  LiliSoftWare 1996-2005");
    printf("\n                       Designed by Lili Wang!\n");
    printf("\nPlease input number of trader:");
    scanf("%d",&s.x);
    s.y=s.x;
    n=s.x;
    s.boat=0;                                                        /*第一次渡河前船在此岸*/
    k=0;        ok=0;        ;                                        /*初始状态量,allFall=0找到策略allFall=1未找到*/
    p1=(LinkList)malloc(sizeof(LNode));                                /*构建状态表*/
    p1->lx=s.x;
    p1->ly=s.y;
    p1->lboat=s.boat;
    p1->lflag=0;
    p1->front=NULL;
    p1->next=NULL;
    p3=p1;

    do
    {
        ok=0;                                                        /*开使新一次渡河*/
        k++;                                                        /*渡河次数加1*/
        d.flag=1;                                                    /*每次都从第一种渡河策略开始判断*/
        do
        {
RELLOW:
            switch(d.flag)
            {
            case 1:    d.u=1;d.v=1;break;
            case 2:    d.u=2;d.v=0;break;
            case 3:    d.u=0;d.v=2;break;
            case 4:    d.u=1;d.v=0;break;
            case 5:    d.u=0;d.v=1;break;
            default: 
                    p2=p3->front;free(p3);                            /*没有策略符合回到前一次状态*/
                    p3=p2;p3->next=NULL;
                    if(p3==NULL)
                    {
                        printf("\nNo answer!");
                        getch();
                        exit(0);
                    }
                    else
                    {
                        s.x=p3->lx;s.y=p3->ly;s.boat=p3->lboat;
                        d.flag=p3->lflag;
                        d.flag++;
                        k--;
                        /*goto RELLOW;*/
                        continue;
                    }

            }/*switch*/
        s.x+=(int)(pow(-1,k))*d.u;
        s.y+=(int)(pow(-1,k))*d.v;
        if(s.boat==0)
            s.boat=1;
        else
            s.boat=0;

        if((s.x==s.y||s.x==0||s.x==n)&&s.x<=n&&s.y<=n&&s.x>=0&&s.y>=0)/*附和允许状态集合*/
        {
            search=p1;

            for(;(search->lx!=s.x||search->ly!=s.y||search->lboat!=s.boat)&&search!=NULL;search=search->next);

            if(search!=NULL)                                        /*若状态已在表中则为死循环,放弃该策略*/
            {
                d.flag++;
                s.x=p3->lx;                                            /*恢复s状态*/
                s.y=p3->ly;
                s.boat=p3->lboat;
                continue;
            }
            else
            {
                /*状态不在表中,该策略可行*/
                ok=1;                                                /*置标志*/
                p2=(LinkList)malloc(sizeof(LNode));                    /*将该状态放入允许状态表*/
                p2->next=NULL;
                p2->lx=s.x;
                p2->ly=s.y;
                p2->lboat=s.boat;
                p2->lflag=0;
                p3->next=p2;
                p2->front=p3;
                p3->lflag=d.flag;
                p3=p2;
            }/*else*/
        }/*if*/
        else                                                        /*不在允许状态集合*/
        {
            d.flag++;
            s.x=p3->lx;                                                /*恢复s状态*/
            s.y=p3->ly;
            s.boat=p3->lboat;

        }

        }while(ok!=1);/*选择每次渡河策略*/

    }while(s.x!=0||s.y!=0);/*全部过河*/

    p3=p1;

    p1=p1->next;
    for(;p1!=NULL;p1=p1->next)
    {
        /*printf("\ntrader:%d,retinue:%d,boat:%d",p1->lx,p1->ly,p1->lboat);*/  /*这是允许状态集合,去掉注释符即可显示*/
        if(p1->lboat==1)
        {
            printf("\nS(trader:%d,retinue:%d):",p1->lx,p1->ly);        /*允许状态集合*/
                                                                    /*渡河策略*/    
            printf("      trader:%d,retinue:%d   ->",abs((p1->front)->lx-(p1->lx)),abs((p1->front)->ly-(p1->ly)));
        }
        else
        {
            printf("\nS(trader:%d,retinue:%d):",p1->lx,p1->ly);        /*允许状态集合*/
                                                                    /*渡河策略*/
            printf("      trader:%d,retinue:%d   <-",abs((p1->front)->lx-(p1->lx)),abs((p1->front)->ly-(p1->ly)));
        }

        getch();
    }
    printf("\n   Success!!!");
    getch();

    while(p3!=NULL)                                                    /*释放内存*/
    {
        p1=p3;
        p3=p3->next;
        free(p1);
    }

}3