The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

数学建模之——商人过河问题 算法核心:搜索法

问题描述： 三个商人各带一个随从乘船过河，一只小船只能容纳2人，由他们自己划船。三个商人窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？

数学建模课上，老师给我们出了这样一个问题，要我们编程解决，呵呵，于是，就写了下面这个程序，这个程序适用于商人数和随从数都《=1000的情况，并且约定小船的容量为2，此程序可以输出每一步的决策过程，还外包了界面以满足上课演示的需要；不过限于老师的要求，就没有写成小船容量为任意值的情况，如果有时间的话我会继续往下写的（貌似也比较容易的样子）~
如果程序中有BUG，欢迎反馈给我,QQ:64076241.

//本程序在商人数<=1000,随从数<=1000时测试通过，其余数据不能保证其正确性.
#include<iostream>
#include <windows.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include<time.h>
#include<conio.h>
using namespace std;



#define NMAX 1001


struct node
{

    int x;
    int y;
}line[10000001];

struct node2
{
    int data1;
    int data2;
    int prex1;
    int prey1;
    int prex2;
    int prey2;
};

node2 a[NMAX][NMAX];

int main ()
{

    
        int N=15;
        while(N--)
        {
            system("cls");
            cout<<endl<<endl<<endl<<endl<<endl<<endl;
            cout<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
            cout<<"     ★                                                                  ★"<<endl;
            cout<<"     ☆                                                                  ☆"<<endl;
            cout<<"     ★                   欢迎来到商人过河模型演示程序                   ★"<<endl;
            cout<<"     ☆                                                                  ☆"<<endl;    
            cout<<"     ★                       制    作：罗伟涛（abilitytao）             ★"<<endl;
            cout<<"     ☆                       指导老师：许春根（南京理工大学应用数学系） ☆"<<endl;
            cout<<"     ★                                                                  ★"<<endl;
            cout<<"     ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆"<<endl;
            Sleep(100);
            system("cls");
            cout<<endl<<endl<<endl<<endl<<endl<<endl;
            cout<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
            cout<<"     ☆                                                                  ☆"<<endl;
            cout<<"     ★                                                                  ★"<<endl;
            cout<<"     ☆                   欢迎来到商人过河模型演示程序                   ☆"<<endl;
            cout<<"     ★                                                                  ★"<<endl;
            cout<<"     ☆                       制    作：罗伟涛（abilitytao）             ☆"<<endl;
            cout<<"     ★                       指导老师：许春根（南京理工大学应用数学系） ★"<<endl;
            cout<<"     ☆                                                                  ☆"<<endl;
            cout<<"     ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★"<<endl;
            Sleep(100);
        }
        cout<<"\n\n\n\n                                                   请按任意键进入演示程序"<<endl;
        char any;
        getch();

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    int n;
    int m;
    int i,j;
    int flagnum1;
    int flagnum2;
    while(1)
    {    
        printf("请输入商人数：");
        scanf("%d",&n);
        printf("请输入随从数：");
        scanf("%d",&m);


        if(n>1000)
        {
            printf("本程序仅在1000以内保证其正确性，请重新输入\n");
            continue;
        }


    


        for(i=0;i<=n;i++)
        {

            for(j=0;j<=m;j++)
            {
                if(i==0||i==n)
                {
                    a[i][j].data1=1;
                    a[i][j].data2=1;
                    continue;
                }
                if(i>=j&&n-i>=m-j)
                {
                    a[i][j].data1=1;
                    a[i][j].data2=1;
                }
                    
            }
        }
        ////////////////////////////////////////////////////////////////////以上为初始化////////////////////////////////////////////////////////////////////////////////
        int flag;
        int front=1;
        int rear=1;
        line[rear].x=n;
        line[rear].y=m;
        flag=1;
        flagnum1=1;
        flagnum2=0;
        while(front<=rear)
        {
            if(line[front].x==0&&line[front].y==0)
                break;
            if(flag==1)
            {
                if(a[line[front].x][line[front].y].data1!=1)
                {
                    flagnum1--;
                    if(flagnum1==0)
                        flag=2;
                    front++;
                    continue;
                }
                
                a[line[front].x][line[front].y].data1=0;
                flagnum1--;
                if(flagnum1==0)
                    flag=2;
                if(line[front].x-1>=0&&a[line[front].x-1][line[front].y].data2==1)
                {
                    rear++;
                    line[rear].x=line[front].x-1;
                    line[rear].y=line[front].y;
                    a[line[rear].x][line[rear].y].prex2=line[front].x;
                    a[line[rear].x][line[rear].y].prey2=line[front].y;
                    flagnum2++;
                }
                if(line[front].y-1>=0&&a[line[front].x][line[front].y-1].data2==1)
                {
                    rear++;
                    line[rear].x=line[front].x;
                    line[rear].y=line[front].y-1;
                    a[line[rear].x][line[rear].y].prex2=line[front].x;
                    a[line[rear].x][line[rear].y].prey2=line[front].y;
                    flagnum2++;
                }
                if(line[front].x-1>=0&&line[front].y-1>=0&&a[line[front].x-1][line[front].y-1].data2==1)
                {
                    rear++;
                    line[rear].x=line[front].x-1;
                    line[rear].y=line[front].y-1;
                    a[line[rear].x][line[rear].y].prex2=line[front].x;
                    a[line[rear].x][line[rear].y].prey2=line[front].y;
                    flagnum2++;
                }
                if(line[front].x-2>=0&&a[line[front].x-2][line[front].y].data2==1)
                {
                    rear++;
                    line[rear].x=line[front].x-2;
                    line[rear].y=line[front].y;
                    a[line[rear].x][line[rear].y].prex2=line[front].x;
                    a[line[rear].x][line[rear].y].prey2=line[front].y;
                    flagnum2++;

                }
                if(line[front].y-2>=0&&a[line[front].x][line[front].y-2].data2==1)
                {
                    rear++;
                    line[rear].x=line[front].x;
                    line[rear].y=line[front].y-2;
                    a[line[rear].x][line[rear].y].prex2=line[front].x;
                    a[line[rear].x][line[rear].y].prey2=line[front].y;
                    flagnum2++;
                }
                front++;
                continue;
            }
            else if(flag==2)
            {
                if(a[line[front].x][line[front].y].data2!=1)
                {
                    flagnum2--;
                    if(flagnum2==0)
                        flag=1;
                    front++;
                    continue;
                    
                }
                if(line[front].x==0&&line[front].y==0)
                    break;
                a[line[front].x][line[front].y].data2=0;
                flagnum2--;
                if(flagnum2==0)
                    flag=1;
                if(line[front].x+1<=n&&a[line[front].x+1][line[front].y].data1==1)
                {

                
                rear++;
                line[rear].x=line[front].x+1;
                line[rear].y=line[front].y;
                a[line[rear].x][line[rear].y].prex1=line[front].x;
                a[line[rear].x][line[rear].y].prey1=line[front].y;
                flagnum1++;
                }
                if (line[front].y+1<=m&&a[line[front].x][line[front].y+1].data1==1)
                {
                
                    rear++;
                    line[rear].x=line[front].x;
                    line[rear].y=line[front].y+1;
                    a[line[rear].x][line[rear].y].prex1=line[front].x;
                    a[line[rear].x][line[rear].y].prey1=line[front].y;
                    flagnum1++;
                }
                if(line[front].x+1<=n&&line[front].y+1<=m&&a[line[front].x+1][line[front].y+1].data1==1)
                {
                    rear++;
                    line[rear].x=line[front].x+1;
                    line[rear].y=line[front].y+1;
                    a[line[rear].x][line[rear].y].prex1=line[front].x;
                    a[line[rear].x][line[rear].y].prey1=line[front].y;
                    flagnum1++;
                }
                if(line[front].x+2<=n&&a[line[front].x+2][line[front].y].data1==1)
                {
                    rear++;
                    line[rear].x=line[front].x+2;
                    line[rear].y=line[front].y;
                    a[line[rear].x][line[rear].y].prex1=line[front].x;
                    a[line[rear].x][line[rear].y].prey1=line[front].y;
                    flagnum1++;
                }
                if(line[front].y+2<=m&&a[line[front].x][line[front].y+2].data1==1)
                {

                
                rear++;
                line[rear].x=line[front].x;
                line[rear].y=line[front].y+2;
                a[line[rear].x][line[rear].y].prex1=line[front].x;
                a[line[rear].x][line[rear].y].prey1=line[front].y;
                flagnum1++;
                
                }
                front++;
                continue;
            }
            front++;
        }
        if(front>rear)
        {
            cout<<"没有可行的方案"<<endl;
            int choice;
            printf("如果您要继续测试，请输入1，退出请输入2:");
            scanf("%d",&choice);
            if(choice==1)
                continue;
            else
                break;
        }
        int tempx=0;
        int tempy=0;
        int markx=0;
        int marky=0;
        printf("初始状态下，河南岸有%d个商人，%d个随从\n",n,m);
        //Sleep(5000);

        int flagforreturn=1;
        int step=1;

        while(1)
        {
            
            if (flagforreturn==1)
            {
                if(markx==n&&marky==m)
                    break;
                flagforreturn=2;
                tempx=a[markx][marky].prex2;
                tempy=a[markx][marky].prey2;
                printf("第%d步：河南岸有%d个商人，%d个随从，此时，对岸有%d个商人，%d个随从（此时船在北岸）\n\n",step,n-tempx,m-tempy,tempx,tempy);
                ///////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
            /*    if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky>n-tempx+m-tempy))
                    cout<<"此步正确"<<endl;
                else
                    cout<<"此步错误"<<endl;*///
                ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
                markx=tempx;
                marky=tempy;
                step++;
                //Sleep(5000);
            }
            else if(flagforreturn==2)
            {
                if(markx==n&&marky==m)
                    break;
                flagforreturn=1;
                tempx=a[markx][marky].prex1;
                tempy=a[markx][marky].prey1;

                printf("第%d步：河南岸有%d个商人,%d个随从，此时，对岸有%d个商人，%d个随从（此时船在南岸）\n\n",step,n-tempx,m-tempy,tempx,tempy);

                ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
                /*    if(tempx==0||tempx==n||(tempx>=tempy&&n-tempx>=m-tempy)&&(n-markx+m-marky<n-tempx+m-tempy))
                    cout<<"此步正确"<<endl;
                else
                    cout<<"此步错误"<<endl;*/
                ////////////////////////////////////////////////////////////////////////////////////////正确性检测/////////////////////////////////////////////////////////////////////////////////////
                markx=tempx;
                marky=tempy;
                step++;
                //Sleep(5000);
            }
        }
        int choice;
        printf("如果您要继续测试，请输入1，退出请输入2:");
        scanf("%d",&choice);
        if(choice==1)
            continue;
        else
            break;


    }
     N=20;
    while(N--)
    {
        system("cls");
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                              谢谢您的使用！再见！                             "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                            ·                                                 "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                      ·                       "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        Sleep(10);
        system("cls");
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                              谢谢您的使用！再见！                             "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                            │                                                 "<<endl;
        cout<<"                         ＼    ／                                              "<<endl;
        cout<<"                       ─        ─                   │                       "<<endl;
        cout<<"                         ／    ＼                  ＼    ／                    "<<endl;
        cout<<"                            │                   ─        ─                  "<<endl;
        cout<<"                                                   ／    ＼                    "<<endl;
        cout<<"                                                      │                       "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        Sleep(10);
        system("cls");
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                              谢谢您的使用！再见！                             "<<endl;         
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                            │                                                 "<<endl;
        cout<<"                       ＼        ／                                            "<<endl;
        cout<<"                                                      │                       "<<endl;
        cout<<"                     ─            ─            ＼        ／                  "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                       ／        ＼            ─            ─                "<<endl;
        cout<<"                            │                                                 "<<endl;
        cout<<"                                                 ／        ＼                  "<<endl;
        cout<<"                                                      │                       "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        Sleep(10);
        system("cls");
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                              谢谢您的使用！再见！                             "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        cout<<"                                                                               "<<endl;
        Sleep(10);
    }

system("pause");
    return 0;
}

posted on 2009-02-26 11:07 abilitytao 阅读(9174) 评论(15)  编辑 收藏 引用

评论

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-02-26 11:59 陈梓瀚(vczh)

这里可以用最短路经法。  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-02-26 12:21 abilitytao

@陈梓瀚(vczh)
恩 开始我也想过的 可是貌似有两种状态吧
一种是船在南岸，一种是船在北岸，如果用dij，貌似在这里就卡住了
不知道要怎么改进才能识别这两种状态呢？

  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-02-26 15:32 winsty

边权相等的最短路啊
BFS就可以了  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法[未登录] 2009-02-26 17:10 abilitytao

@winsty
难道我用的不是BFS?

  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-02-27 13:41 yindf

片尾很帅！  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-04 13:06 马文旭

有没有C版的呢？
我怎么运行不了呢？  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-04 22:25 abilitytao

@马文旭
VC6.0肯定能运行的  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-07 20:58 爱你

四个人的是不是可定能过去啊 ？  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-08 01:31 abilitytao

@爱你
如果船的容量是2人的话 无解 ，3个人以上应该是可以的:-)  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-05-22 16:41 shizhanwei

3以上怎么不行？  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法[未登录] 2009-05-22 17:25 abilitytao

@shizhanwei
因为无解  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2009-10-28 20:06 侠客西风

这个貌似和传教士过河一样,我学人工智能的时候,也做过这个搜索算法...  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法[未登录] 2010-02-09 14:02 abilitytao

现在在一看这个搜索代码　写得真是差劲。。。。  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2011-06-10 10:33 hyzdou

什么是搜索发，求指教。  回复  更多评论   

# re: 数学建模之——商人过河问题 算法核心:搜索法 2012-10-07 20:12 abilitytao

@hyzdou
这个代码写的很差 请无视吧。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理