傳教士過(guò)河問(wèn)題(實(shí)驗(yàn)二)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上傳教士過(guò)河問(wèn)題實(shí)驗(yàn)報(bào)告計(jì)研-12 15 宋玲玲1實(shí)驗(yàn)?zāi)康模?）了解知識(shí)表示相關(guān)技術(shù)；（2）掌握問(wèn)題規(guī)約法或者狀態(tài)空間法的分析方法。2實(shí)驗(yàn)內(nèi)容從前有一條河，河的左岸有m個(gè)傳教士、m個(gè)野人和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒(méi)有傳教士，或者野人數(shù)量少于傳教士，否則野人會(huì)把傳教士吃掉。搜索一條可使所有的野人和傳教士安全渡到右岸的方案。3實(shí)驗(yàn)原理及方法假設(shè)開始時(shí)傳教士、野人和船都在右岸，用數(shù)組(a,b,c)分別表示右岸傳教士個(gè)數(shù)、右岸野人個(gè)數(shù)、船的位置，則可分為三種情況討論:A、n>m/2。此種情況下，先把所有的野人度過(guò)去，每次返回一個(gè)野人，當(dāng)出現(xiàn)(m,0

2、,0)情況時(shí)，返回m-n個(gè)野人(若m=n,返回1個(gè)野人)。然后渡n個(gè)傳教士，此時(shí)野人=傳教士，然后返回一個(gè)野人和傳教士，再開始最大限度的渡傳教士，每次返回一個(gè)野人,最終直到a=b=c=0；B、n<=3&&n<=m/2 | n=1，顯然此時(shí)無(wú)解；C、n>=4&&n<=m/2，此時(shí)只能每次傳n/2個(gè)傳教士和野人,每次返回一個(gè)野人和傳教士,直到最終結(jié)果。程序流程圖如下：4、源程序清單：本程序用C+語(yǔ)言編寫。#include "iostream"using namespace std;bool flag = false;/標(biāo)記

3、是否有解bool af = false;/標(biāo)記a是否為0bool bf = false;/當(dāng)b變?yōu)?后賦值為true;bool ef = false;/當(dāng)a=b后賦值為truebool f = false;/判斷n是否大于m/2int m;/傳教士野人的個(gè)數(shù)int n;/船一次能裝載的人數(shù)void mc(int a,int b,int c);int main()cout<<"傳教士與野人過(guò)河問(wèn)題。n假設(shè)最初時(shí)傳教士與野人在河的右岸。n"cout<<"請(qǐng)輸入傳教士野人的個(gè)數(shù)：n"cin>>m;cout<<&q

4、uot;請(qǐng)輸入船一次能裝載的人數(shù): n"cin>>n;cout<<"右岸傳教士人數(shù)t"<<"右岸野人個(gè)數(shù)t"<<"船的位置（1.右岸 0左岸）"<<endl;if(m<=3 && n<=m/2) | n=1)/此種情況無(wú)解cout<<"No solution!n"system("pause");return 0;if(n > m/2)f = true;mc(m,m,1);if(fl

5、ag = true)cout<<"Success!n"elsecout<<"No solution!n"system("pause");return 0; void mc(int a,int b,int c)if(flag=true) return;if(c = 1)cout<<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(f=t

6、rue)/如果n>m/2if(bf!=true)/b未達(dá)到過(guò)0if(a+b<=n)/如果a+b<=n,完全渡過(guò)mc(0,0,1-c);/遞歸elsefor(int j = n;j >= 0;j-)if(b >= j)mc(a,b-j,1-c);/遞歸if(flag=true) return;else if(ef!=true&& af=false)for(int i = n;i>=0;i-)if(a>=i)mc(a-i,b,1-c);/遞歸if(flag=true) return;if(ef = true && af=fa

7、lse)if(a>=n)mc(a-n,b,1-c);/遞歸else if(a+b<n)mc(0,0,1-c);elsemc(0,b-(n-a),1-c);if(af=true)if(b>=n)mc(a,b-n,1-c);/遞歸elsemc(a,0,1-c);else mc(a-n/2,b-n/2,1-c); /遞歸if(c = 0)cout<<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(a =

8、 b && b = c && a = 0)flag = true;return;if(f=true)/如果n>m/2if(b=0)bf = true;if(m <= n)mc(a,b+1,1-c);/遞歸elsemc(a,b+m-n,1-c);if(a=b)ef = true;mc(a+1,b+1,1-c);/遞歸if(a = 0)af = true;mc(a,b+1,1-c);/遞歸while(bf!=true)mc(a,b+1,1-c);/遞歸else/k<=n/2&&k>3mc(a+1,b+1,1-c);/遞歸 5、實(shí)驗(yàn)結(jié)果及分析。程序?qū)嶒?yàn)結(jié)果如下圖。當(dāng)然，傳教士與野人個(gè)數(shù)為3，船一次能載兩個(gè)人，這是最經(jīng)典的例子。本程序也可輸入其