加载中…牧师野人过河算法
(2012-11-14 09:51:47)
标签：
杂谈 |
分类： C/C |
这也是一个牧师野人过河问题的算法，问题在上一篇博文中有，就一再描述了，这个算法只考虑单向，比较容易理解，以下是算法代码：
char
s[30];
//非法状态
if(m<0||c<0||M<0||C<0){
return false;
}
//野人多于传教士，传教士会被吃掉
if((m&&c>m)||(M&&C>M)){
return false;
}
//运送到了对岸,甲岸没有牧师和野人或乙岸没有牧师和野人(任何一岸没有牧师和野人都表示运送成功)
if((boat&&M==0&&C==0)||(!boat&&m==0&&c==0)){
return true;
}
if(boat==true){//船在甲岸
sprintf(s,"M=%d,C=%d,m=%d,c=%d,boat=left",M,C,m,c);//
把当前状态存放在s内
}else{
sprintf(s,"M=%d,C=%d,m=%d,c=%d,boat=right",M,C,m,c);
//把当前状态存放在s内
}
for(int i=0;i
//如果此状态已存在过
if(vect[i]==s){
return false;
}
}
//搜索五种状态
boat =
!boat;
vect.push_back(s); //把s存放在vect中
if(dfs(m+2,c,M-2,C)){
cout<<"两个传教士过河."<<endl;
return
true;
}else
if(dfs(m,c+2,M,C-2)){
cout<<"两个野人过河."<<endl;
return
true;
}else
if(dfs(m+1,c+1,M-1,C-1)){
cout<<"一个野人和一个传教士过河."<<endl;
return
true;
}else
if(dfs(m+1,c,M-1,C)){
cout<<"一个传教士过河."<<endl;
return
true;
}else
if(dfs(m,c+1,M,c-1)){
cout<<"一个野人过河."<<endl;
return
true;
}
boat =
!boat;
vect.pop_back();
return
false;
//假设一种情况
int
M=6,C=6,m=0,c=0;
char
s[30];
sprintf(s,"M=%d,C=%d,m=%d,c=%d,boat=left",M,C,m,c);
cout<<s<<endl;
if(!dfs(m,c,M,C)){
cout<<"can not find a
solution."<<endl;
}
system("pause");
return 0;
#include
#include
#include
using namespace std;
vector vect;
bool boat = true;//true表示船在对岸(甲岸)
//用深度搜索的方法进行解答
bool dfs(int m,int c,int M,int C){
//可以是甲岸到乙岸也可以是乙岸到岸,由初始状态决定
}
int main() {
}
喜欢
0
赠金笔