admin 管理员组文章数量: 893893
人狼羊菜
前两天老师在讲课后题(人狼羊菜过河问题:人狼羊菜都在河的一边,人要带它们过河,每次只能带一个,而狼吃羊,羊吃菜,不能单独在一起)的时候突发灵感,道:这道题好玩啊!就把这道题留下来写程序吧!虽说这个脑残式环境问题想来不难,但要抽象模型还是要动下脑子的,想了一下,为了把它扩展成一类问题,还是关系矩阵要好一下,于是就试着写了一 下—————其实也不是无所谓的态度了,这也是老师留下来的作业啦!
#include<stdio.h>
#include<stdlib.h>
const int relate[10][10]={ /* 15,14,13,11,10, 5, 4, 2, 1, 0 状态编号*/
/* 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
/*15人狼羊菜0*/ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
/*14 人狼羊1*/ { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
/*13人狼菜2 */ { 0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
/*11 人羊菜3*/ { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
/*10 人羊 4 */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
/*5 狼菜 5 */ { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
/*4 狼 6 */ { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
/*2 羊 7*/ { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
/*1 菜 8 */ { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
/*0运送完成9*/ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
const char result[10][9]={"人狼羊菜","人狼羊","人狼菜","人羊菜","人羊","狼菜","狼","羊","菜","运送完成"};
const int charge[10]={15,14,13,11,10,5,4,2,1,0};
int main()
{
int flag[10]={0}; //跳转到每一行之后再继续往下走能有多少种选择
int i,num=1,cmp,temp=0,j=0,
line=0,a=0,b=0,big=1;
int copy[10][10]; //拷贝一份状态矩阵用来可以更改后继状态一遍扫描多条路径
int methods[10]={0}; //扫描出来的路径
for(i=0;i<10;i++)
for(j=0;j<10;j++)
copy[i][j]=relate[i][j];
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
flag[a]+=relate[i][j];
a++;
}
for(i=0;i<10;i++)
{
if(flag[i]==0)
continue;
else
big*=flag[i];
}
while(big--)
{
line=temp=j=a=0;
do{
if(copy[line][j]==1)
{
methods[a]=j;
a++;
temp=a-1;
if(flag[line]>1)
{
flag[line]--;
copy[line][j]=0;
}
line=j;
j=0;
continue;
}
else
j++;
}while(methods[temp]!=9);
printf("第%d条传送路线为:\n%s",num++,result[0]);
for(i=0;i<a;i++)
{
cmp=methods[i];
printf("-->%s",result[cmp]);
}
printf("\n");
for(i=0;i<10;i++)
methods[i]=0;
}
return 0;
}
其实仔细一想这个貌似是不带反回状态的,对于多环限制关系,应该会乱的吧!这些天忙的很,暂时也不想再改了。。。
本文标签: 人狼羊菜
版权声明:本文标题:人狼羊菜 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687330531h90327.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论