过河问题算法
你好，我来为你解答：
解法如下：
1.农夫带羊过去，自己回来
2.农夫带狼过去，带羊回来
3.农夫带白菜过去，自己回来
4.农夫带羊过去
全部安全过岸.
程序暂时没有时间做
❷ 有三只大老虎ABC，三只小老虎abc，怎样过河
楼上，你是人才（a在岸上，B在船上），你还好意思说是离散数学的问题，倒
个人见解：
ab过，a回 ABCac b
ac过，a回 ABCa bc
BC过，Bb回 ABab Cc
Aa过，Cc回 BCbc Aa
BC过，a回 abc ABC
ab过，a回 ac ABCb
ac过 --- ABCabc
❸ c语言 《过河》
先带兔子过河,再回来,再带狮子过河,顺便把兔子带回来,再把白菜带过河,然后回来再把兔子带过去,就OK了
这个主要是人不在的时候,狮子会吃兔子,兔子会出白菜,但狮子肯定不会吃白菜是不,就根据这个想不就是了
简单的逻辑问题,我只说算法,你定义两个数组,数组一代表河这边的东西,数组二代表河那边的东西(其中加入一个空白东西,也就是不带东西的选择),循环带数组1中的东西,每次过河带东西之后,判断两个数组中是否有吃与被吃的关系(这个定义成一个函数),然后就是回来,回来的时候循环带数组2中的东西,判断两个数组中是否有吃与被吃的关系,这样循环下去,直到河这边的东西为空的时候就完了
❹ 求船夫渡河问题的算法 急！！！
先运羊到对岸去，然后空船回来，再运狼到对岸去，再将羊装上，载回去，将白菜运过去，现在对岸只有狼和白菜，现在空船回去，将羊再运过河去就行了。谢谢、
❺ 农夫过河问题，从java代码看算法
好繁琐...一堆if else...你不觉得很麻烦吗? 我给你提个思路. 你每个Goods object里面都设置一个天敌的list.
Goodsg=newGoods("Sheep");
g.setEnemy(Arrays.asList(newString[]{"wolf"}));
Goodsg2=newGoods("Cabbage");
g2.setEnemy(Arrays.asList(newString[]{"Sheep"}));
Goodsg3=newGoods("Wolf");
g3.setEnemy(Arrays.asList(newString[]{}));这样你的在check isFriendly的时候, 只要检测2个物品的enemyList里面没有自己就可以了.
return!good1.getEnemyList().contains(good2.getName())&&!good2.getEnemyList().contains(good1.getName());
❻ 农夫过河问题的求解
#include<iostream.h>
#include<stdio.h>
#defineMAXNUM 20
typedefstruct //顺序队列类型定义
{
int f, r; //f表示头，r 表示尾
int q[MAXNUM];//顺序队
}SeqQueue,*PSeqQueue;
PSeqQueuecreateEmptyQueue_seq( ) //创建队列
{
PSeqQueue paqu = new SeqQueue;
if(paqu == NULL)
cout<<"Out of space!"<<endl;
else
paqu->f=paqu->r=0;
return (paqu);
}
intisEmptyQueue_seq( PSeqQueue paqu ) //判断paqu 所指是否是空队列
{
return paqu->f==paqu->r;
}
voidenQueue_seq(PSeqQueue paqu,int x) //在队列中插入一元素 x
{
if ((paqu->r+1)%MAXNUM==paqu->f)
cout<<"队列已满."<<endl;
else
{
paqu->q[paqu->r]=x;
paqu->r=(paqu->r+1)%MAXNUM;
}
}
void deQueue_seq(PSeqQueue paqu) //删除队列头部元素
{
if( paqu->f==paqu->r)
cout<<"队列为空"<<endl;
else
paqu->f=(paqu->f+1)%MAXNUM;
}
intfrontQueue_seq( PSeqQueue paqu ) //对非空队列,求队列头部元素
{
return (paqu->q[paqu->f]);
}
intfarmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置
{
return 0 != (location & 0x08);
}
intwolf(int location) //判断狼位置
{
return 0 != (location & 0x04);
}
intcabbage(int location) //判断白菜位置
{
return 0 != (location & 0x02);
}
intgoat(int location) //判断羊的位置
{
return 0 !=(location & 0x01);
}
intsafe(int location) // 若状态安全则返回 true
{
if ((goat(location) == cabbage(location))&& (goat(location) != farmer(location)) )
return 0;
if ((goat(location) == wolf(location))&& (goat(location) != farmer(location)))
return 0;
return 1; //其他状态是安全的
}
void farmerProblem( )
{
int movers, i, location, newlocation;
int route[16]; //记录已考虑的状态路径
int print[MAXNUM];
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );//新的队列判断路径
enQueue_seq(moveTo, 0x00); //初始状态为0
for (i = 0; i < 16; i++)
route[i] = -1; //-1表示没有记录过路径
route[0]=0;
while(!isEmptyQueue_seq(moveTo)&&(route[15] == -1))//队列不为空，路径未满时循环
{
location = frontQueue_seq(moveTo); //从队头出队
deQueue_seq(moveTo);
for (movers = 1; movers <= 8;movers<<= 1)
{
if ((0 != (location & 0x08)) == (0 !=(location & movers)))
{
newlocation = location^(0x08|movers);//或运算
if (safe(newlocation) &&(route[newlocation] == -1))//判断是否安全，以及路径是否可用
{
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
/*打印出路径 */
if(route[15] != -1)
{
cout<<"过河步骤是 : "<<endl;
i=0;
for(location = 15; location >= 0; location= route[location])
{
print[i]=location;
i++;
if (location == 0)
break;
}
int num=i-1;
int temp[20][4];
int j;
for(i=num;i>=0;i--)
{
for(j=3;j>=0;j--)
{
temp[num-i][j]=print[i]%2;
print[i]/=2;
temp[0][j]=0;
temp[num+1][j]=1;
}
}
for(i=1;i<=num;i++)
{
cout<<"\t\t\tNO ."<<i<<"\t";
if(i%2==1)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊过南岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜过南岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼过南岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己过南岸";
}
else if(i%2==0)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊回北岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜回北岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼回北岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己回北岸";
}
cout<<endl;
}
}
else
cout<<"Nosolution."<<endl;
}
int main() /*主函数*/
{
farmerProblem();
return 0;
}
❼ 用计算机语言实现算法（商人安全过河问题）
这个你看看吧，就是太麻烦了
#include <stdlib.h>
struct node /*建立一个类似栈的数据结构并且可以浏览每一个数据点*/
{
int x;
int y;
int state;
struct node *next;
};
typedef struct node state;
typedef state *link;
link PPointer1=NULL;
link PPointer2=NULL;
int a1,b1;
int a2,b2;
/*栈中每个数据都分为0，1状态*/
void Push(int a,int b,int n)
{
link newnode;
newnode=(link)malloc(sizeof(state));
newnode-> x=a;
newnode-> y=b;
newnode-> state=n;
newnode-> next=NULL;
if(PPointer1==NULL)
{
PPointer1=newnode;
PPointer2=newnode;
}
else
{
PPointer2-> next=newnode;
PPointer2=newnode;
}
}
void Pop() /*弹栈*/
{
link pointer;
if(PPointer1==PPointer2)
{
free(PPointer1);
PPointer1=NULL;
PPointer2=NULL;
}
pointer=PPointer1;
while(pointer-> next!=PPointer2)
pointer=pointer-> next;
free(PPointer2);
PPointer2=pointer;
PPointer2-> next=NULL;
}
int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/
{
link pointer;
if(PPointer1==NULL)
return 1;
else
{
pointer=PPointer1;
while(pointer!=NULL)
{
if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n)
return 0;
pointer=pointer-> next;
}
return 1;
}
}
int judge(int a,int b,int c,int d,int n) /*判断这个状态是否可行，其中使用了history函数*/
{
if(history(a,b,n)==0) return 0;
if(a> =0&&b> =0&&a <=3&&b <=3&&c> =0&&d> =0&&c <=3&&d <=3&&a+c==3&&b+d==3)
{
switch(n)
{
case 1:
{
if(a==3)
{
Push(a,b,n);
return 1;
}
else if(a==0)
{
Push(a,b,n);
return 1;
}
else if(a==b)
{
Push(a,b,n);
return 1;
}
else return 0;
}
case 0:
{
if(a==3)
{
Push(a,b,n);
return 1;
}
else if(a==0)
{
Push(a,b,n);
return 1;
}
else if(a> =b)
{
Push(a,b,n);
return 1;
}
else return 0;
}
}
}
else return 0;
}
int Duhe(int a,int b,int n) /*递归法解决商人渡河问题，如果这一个状态符合*/
{ /*则判断下一个状态，直至问题解决*/
if(a==0&&b==0) return 1;
if(n==0) /*判断0状态时，商匪状态是否符合要求*/
{
if(judge(a-1,b-1,4-a,4-b,1))
{
if(Duhe(a-1,b-1,1)==1)
return 1;
}
if(judge(a,b-2,3-a,5-b,1))
{
if(Duhe(a,b-2,1)==1)
return 1;
}
if(judge(a-2,b,5-a,3-b,1))
{
if(Duhe(a-2,b,1)==1)
return 1;
}
if(judge(a-1,b,4-a,3-b,1))
{
if(Duhe(a-1,b,1)==1)
return 1;
}
if(judge(a,b-1,3-a,4-b,1))
{
if(Duhe(a,b-1,1)==1)
return 1;
}
else
{
Pop(0);
return 0;
}
}
if(n==1) /*判断0状态时，商匪状态是否符合要求*/
{
if(judge(a+1,b+1,2-a,2-b,0))
{
if(Duhe(a+1,b+1,0)==1)
return 1;
}
if(judge(a,b+2,3-a,1-b,0))
{
if(Duhe(a,b+2,0)==1)
return 1;
}
if(judge(a+2,b,1-a,3-b,0))
{
if(Duhe(a+2,b,0)==1)
return 1;
}
if(judge(a+1,b,2-a,3-b,0))
{
if(Duhe(a+1,b,0)==1)
return 1;
}
if(judge(a,b+1,3-a,2-b,0))
{
if(Duhe(a,b+1,0)==1)
return 1;
}
else
{
Pop(1);
return 0;
}
}
return 0;
}
main()
{
link pointer;
Push(3,3,0);
Duhe(3,3,0);
pointer=PPointer1;
while(pointer!=NULL)
{
printf( "%d,%d---%d\n ",pointer-> x,pointer-> y,pointer-> state);
pointer=pointer-> next;
}
getch();
}
❽ 一个人要将狼、羊、菜过河一次只能带一样，他不在时，狼要吃羊，羊要吃菜。怎样才能安全过河
2种方式：
1、把羊带到河对岸 -> 把狼带到河对岸，再把羊带回来 - 把白菜带到河对岸 - 把羊带到河对岸；
2、把羊带到河对岸 -> 把白菜带到河对岸，再把羊带回来 -把狼带到河对岸 -把羊带到河对岸；
问题分析：
抛开算法，把这个题当成是一个简单的逻辑题的话还是挺好解的，过不了多久你就会发现几个关键的问题：
1、要时刻注意农夫的位置，因为农夫不在地时候狼会吃羊，羊会吃菜；
2、第一步只能把羊带走；
3、最后一步只能是把羊从河对岸带过来；
会发现羊其实是问题的关键，只要保证羊和狼和白菜隔离开来，那么就很容易解这个问题。
(8)过河问题算法扩展阅读：
过河问题，其实质就是一种状态的改变，就像这个问题说的，农夫狼羊菜都要从河的这边到对岸去，也就对应了两个状态，一个是没过河的状态，一个是过了河的状态。
所以很自然的联想到了用0和1来表示他们的状态，并且每时每刻，农夫狼羊菜的状态都对应一个特定的状态，比如没过河的状态是0000，四个都没有过河，而过河的状态是1111。这样做的好处是将问题抽象成了计算机能够处理的数据。
当然可以选择暴力穷举法，列出所有可能并找出合理的，这是屡试不爽而且行之有效的方法。但这并不是聪明的做法。如果学习数据结构学习得好的同学，会想到用图的V来描述每一种状态，用E来描述状态之间的对应关系，最后进行图的遍历就能找到答案了
❾ 算法“农夫过河”程序 望高手指错修改
v!=1111
能这么用么,这里的1111应该是十进制的1111了吧.
bitset没用过,不知道是不是要用
v.to_ulong()!=0x0F
算法上也有问题,就是当某种走法不成功时,退回上层递归后,没有回复到走之前的状态.应该设个临时变量等于v,对临时变量进行flip和search递归.
另外,采用某种走法前的判断if语句也有问题,比如v[farmer]==v[sheep],我们已经知道正确走法的第一步就是农夫和羊过,但第二步的时候, 农夫和羊都在对岸,值都是1,仍相等,就又都走回来了.
我个人认为,这个问题应该构造树,然后层次遍历,而现在的程序是深度优先遍历.
❿ C语言经典题目
1.正确的算法:
如果n=3, 过河时间为A+B+C
如果n<=2, 好算, 不费口舌了
如果n>=4, 这个是重点:
每次优先考虑把最慢两人送过河
把n人中最快两人记为A,B, 最慢两人记为C,D(过河时间A<B<C<D), n人问题实质上转换为4人过河问题, 参考到4人过河时的优化,
记AB过河, A回, CD过河, B回, 为方法X, 实质是利用最快两人进行优化, 耗时A+2B+D
记AD过河, A回, AC过河, A回, 为方法y, 实质是利用最快一人来过河, 耗时2A+C+D
每次比较这两个方法, 如果x快, 使用x方法, 如果y快, 则用y, 并且, 一旦某次使用y方法后, 以后都不用比较了, 全部使用y方法过河
2.算法正确性证明:
为什么每次先让最慢两人过河? 因为他们迟早要过河...早过晚过一样, 而晚过的话, 有可能时间不能被优化, 所以选择最先过
为什么是两人, 不是三人? 因为这船一次只能两人, 三人问题和两人问题的优化一样, 所以一次考虑三人毫无意义, 同理, 三人以上不加考虑
为什么某次用y过河后不用再比较xy了?
先看这个例子:
1 99 100 101
用x方法是99+1+101+99= 300
y方法是 101+1+100+1 = 203
y比x快的原因是2A+C+D < A+2B+D, 即 A+C<2B
容易想到, 从此以后A+C都会小于2B了(因为C越来越小)
3.补充:
算法分析就到这里了, 至于具体的程序...楼主既然是ACMer, 这个应该不困难
当然, 如果楼主需要的话, 也可以给出程序