過河問題演算法
你好，我來為你解答：
解法如下：
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, 這個應該不困難
當然, 如果樓主需要的話, 也可以給出程序