The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

數學建模之——商人過河問題算法核心:搜索法

問題描述：三個商人各帶一個隨從乘船過河，一只小船只能容納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;

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;

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;

Sleep(10);

system("cls");

cout<<" "<<endl;

cout<<" 謝謝您的使用！再見！ "<<endl;

cout<<" "<<endl;

Sleep(10);

}

system("pause");

return 0;

}

posted on 2009-02-26 11:07 abilitytao 閱讀(9279) 評論(15) 編輯收藏引用

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 11:59 陳梓瀚(vczh)

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 12:21 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 15:32 winsty

# re: 數學建模之——商人過河問題算法核心:搜索法[未登錄] 2009-02-26 17:10 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-27 13:41 yindf

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-04 13:06 馬文旭

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-04 22:25 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-07 20:58 愛你

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-08 01:31 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-22 16:41 shizhanwei

# re: 數學建模之——商人過河問題算法核心:搜索法[未登錄] 2009-05-22 17:25 abilitytao

# 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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

數學建模之——商人過河問題算法核心:搜索法

評論

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

數學建模之——商人過河問題 算法核心:搜索法

評論

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-02-26 11:59 陳梓瀚(vczh)

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-02-26 12:21 abilitytao

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-02-26 15:32 winsty

# re: 數學建模之——商人過河問題 算法核心:搜索法[未登錄] 2009-02-26 17:10 abilitytao

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-02-27 13:41 yindf

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-05-04 13:06 馬文旭

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-05-04 22:25 abilitytao

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-05-07 20:58 愛你

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-05-08 01:31 abilitytao

# re: 數學建模之——商人過河問題 算法核心:搜索法 2009-05-22 16:41 shizhanwei

# re: 數學建模之——商人過河問題 算法核心:搜索法[未登錄] 2009-05-22 17:25 abilitytao

# 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

數學建模之——商人過河問題算法核心:搜索法

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 11:59 陳梓瀚(vczh)

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 12:21 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-26 15:32 winsty

# re: 數學建模之——商人過河問題算法核心:搜索法[未登錄] 2009-02-26 17:10 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-02-27 13:41 yindf

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-04 13:06 馬文旭

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-04 22:25 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-07 20:58 愛你

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-08 01:31 abilitytao

# re: 數學建模之——商人過河問題算法核心:搜索法 2009-05-22 16:41 shizhanwei

# re: 數學建模之——商人過河問題算法核心:搜索法[未登錄] 2009-05-22 17:25 abilitytao

# 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