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 阅读(9167) 评论(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   知识库   博问   管理