過河演算法

Ⅰ 有10個人要過河，河中有條船一次最多坐5個人，要過幾次才可過去

有10個人要過河，河中有條船一次最多坐5個人，要過3次才可過去；

雖然船上每次能坐5個人，但在船返回時，必須有一個人跟著船一起返回；因此，每次只能有5-1=4（個）人過河；

計算如下：

10÷（5-1）=2次……2人

2+1=3次

計算的定義

計算的定義有許多種使用方式，有相當精確的定義，例如使用各種演算法進行的「算術」，也有較為抽象的定義，例如在一場競爭中「策略的計算」或是「計算」兩人之間關系的成功機率。

將7乘以8（7x8）就是一種簡單的算術。數學中的計算有加，減，乘，除，乘方，開方等。其中加減乘除被稱為四則運算。

利用布萊克-舒爾斯定價模型（Black-Scholes Model）來算出財務評估中的公平價格（fair price）就是一種復雜的算術。

從投票意向計算評估出的選舉結果（民意調查）也包含了某種算術，但是提供的結果是「各種可能性的范圍」而不是單一的正確答案。

決定如何在人與人之間建立關系的方式也是一種計算的結果，但是這種計算難以精確、不可預測，甚至無法清楚定義。這種可能性無限的計算定義，和以上提到的數學算術大不相同。

英文中的計算為「Calculation」，來自拉丁文中的「Calculus」，指的是算盤上用來計算的小石頭。

Ⅱ 人帶著羊狼青菜過河,演算法編寫

將這個問題轉變成一個路徑查找問題
起始點（1111）2進製表示起始狀態，人 狼 羊 菜在左邊，，終點（0000）2進製表示過河成攻
一共有2的4次方，也就是16個點，其中一部分狀態不符合要求（可能是在岸左不符合要求，也可能是岸右不符合要求），根據題目要求排除這些點。點間路徑可以用 異或 變換來獲得，比如1100表示人和狼上船，與起始狀態1111異或後變成0011，岸左剩下羊和菜，表示存在從點1111到0011的路徑 。這一步要注意判斷那些點存在哪些路徑，比如：1010狀態下就不存在1100這條路徑。
路徑有三種分別為1100，1010，1001。建立了無向圖後，使用深搜廣搜都可以。

Ⅲ 關於帶錢袋過河的演算法。

如果用腦，比較費力，如果用電腦，只不過是一個窮舉法而已。

Ⅳ 求船夫渡河問題的演算法 急！！！

先運羊到對岸去，然後空船回來，再運狼到對岸去，再將羊裝上，載回去，將白菜運過去，現在對岸只有狼和白菜，現在空船回去，將羊再運過河去就行了。謝謝、

Ⅳ 野人過河新問題 演算法

野人過河問題演算法分析
野人過河問題演算法分析

野人過河問題屬於人工智慧學科中的一個經典問題，問題描述如下： 有三個牧師（也有的翻譯為傳教士）和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數大於牧師的人數，那麼牧師就會有危險. 你能不能找出一種安全的渡河方法呢？
一、演算法分析
先來看看問題的初始狀態和目標狀態，假設和分為甲岸和乙岸：
初始狀態：甲岸，3野人，3牧師；
乙岸，0野人，0牧師；
船停在甲岸，船上有0個人；
目標狀態：甲岸，0野人，0牧師；
乙岸，3野人，3牧師；
船停在乙岸，船上有0個人；
整個問題就抽象成了怎樣從初始狀態經中間的一系列狀態達到目標狀態。問題狀態的改變是通過劃船渡河來引發的，所以合理的渡河操作就成了通常所說的算符，根據題目要求，可以得出以下5個算符（按照渡船方向的不同，也可以理解為10個算符）：
渡1野人、渡1牧師、渡1野人1牧師、渡2野人、渡2牧師
算符知道以後，剩下的核心問題就是搜索方法了，本文採用深度優先搜索，通過一個FindNext(…)函數找出下一步可以進行的渡河操作中的最優操作，如果沒有找到則返回其父節點，看看是否有其它兄弟節點可以擴展，然後用Process(…)函數遞規調用FindNext(…)，一級一級的向後擴展。
搜索中採用的一些規則如下：
1、渡船優先規則：甲岸一次運走的人越多越好（即甲岸運多人優先），同時野人優先運走；
乙岸一次運走的人越少越好（即乙岸運少人優先），同時牧師優先運走；
2、不能重復上次渡船操作（通過鏈表中前一操作比較），避免進入死循環;
3、任何時候河兩邊的野人和牧師數均分別大於等於0且小於等於3；
4、由於只是找出最優解，所以當找到某一算符（當前最優先的）滿足操作條件後，不再搜索其兄弟節點，而是直接載入鏈表。
5、若擴展某節點a的時候，沒有找到合適的子節點，則從鏈表中返回節點a的父節點b，從上次已經選擇了的算符之後的算符中找最優先的算符繼續擴展b。

二、基本數據結構
仔細閱讀問題，可以發現有些基本東西我們必須把握，例如：每時刻河兩岸野人牧師各自的數目、船的狀態、整個問題狀態。所以我們定義如下幾個數據結構：
typedef struct _riverside // 岸邊狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}RIVERSIDE;
typedef struct _boat // 船的狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}BOAT;
typedef struct _question // 整個問題狀態
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸為-1, 乙岸為1
BOAT boat; // 船的狀態
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向後一渡船操作
}QUESTION;
用QUESTION來聲明一個最基本的鏈表。

三、程序流程及具體設計
本文只找出了最優解，據我所知，本問題有三種解。如果真要找出這三種解，^_^，那就得加強對鏈表的操作了，比如說自己寫一個動態鏈表類，順便完成一些初始化工作，估計看起來會舒服些。
下面給出部分關鍵程序：
// 主函數
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍歷鏈表輸出結果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎樣才能渡河呢? 郁悶!"<<endl;
// 回收內存空間
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}

// 渡船過程, 遞規調用函數FindNext(...)

BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 無解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父節點重新再找
}
return TRUE;
}

// 判斷有否下一個渡河操作, 即根據比較算符找出可以接近目標節點的操作
// 算符共5個: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本規則
// 渡船的優先順序: 甲岸運多人優先, 野人優先; 乙岸運少人優先, 牧師優先.
static BOAT boatState[5]; // 5個算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用來控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始狀態, 第一次渡河時
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 擴展同一節點時, 已經用過的算符不再用, 按優先順序來
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判斷本次操作的安全性, 即牧師數量>=野人或牧師數為0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重復上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 該操作可行, 推出循環，只找出當前最優節點
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;

}

Ⅵ 演算法「農夫過河」程序 望高手指錯修改

v!=1111
能這么用么,這里的1111應該是十進制的1111了吧.
bitset沒用過,不知道是不是要用
v.to_ulong()!=0x0F

演算法上也有問題,就是當某種走法不成功時,退回上層遞歸後,沒有回復到走之前的狀態.應該設個臨時變數等於v,對臨時變數進行flip和search遞歸.

另外,採用某種走法前的判斷if語句也有問題,比如v[farmer]==v[sheep],我們已經知道正確走法的第一步就是農夫和羊過,但第二步的時候, 農夫和羊都在對岸,值都是1,仍相等,就又都走回來了.

我個人認為,這個問題應該構造樹,然後層次遍歷,而現在的程序是深度優先遍歷.

Ⅶ 高分跪求求過河問題程序演算法！

paddy102的專欄

CSDNBlog | 我的首頁 | 聯系作者 | 聚合 | 登錄 5篇文章 :: 0篇收藏:: 0篇評論:: 0個Trackbacks

文章
C++/Visual C++(RSS)
演算法設計(RSS)
游戲開發(RSS)
收藏
相冊
存檔
2004年06月(4)
2004年04月(1)

野人過河問題演算法分析
野人過河問題演算法分析

野人過河問題屬於人工智慧學科中的一個經典問題，問題描述如下： 有三個牧師（也有的翻譯為傳教士）和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數大於牧師的人數，那麼牧師就會有危險. 你能不能找出一種安全的渡河方法呢？
一、演算法分析
先來看看問題的初始狀態和目標狀態，假設和分為甲岸和乙岸：
初始狀態：甲岸，3野人，3牧師；
乙岸，0野人，0牧師；
船停在甲岸，船上有0個人；
目標狀態：甲岸，0野人，0牧師；
乙岸，3野人，3牧師；
船停在乙岸，船上有0個人；
整個問題就抽象成了怎樣從初始狀態經中間的一系列狀態達到目標狀態。問題狀態的改變是通過劃船渡河來引發的，所以合理的渡河操作就成了通常所說的算符，根據題目要求，可以得出以下5個算符（按照渡船方向的不同，也可以理解為10個算符）：
渡1野人、渡1牧師、渡1野人1牧師、渡2野人、渡2牧師
算符知道以後，剩下的核心問題就是搜索方法了，本文採用深度優先搜索，通過一個FindNext(…)函數找出下一步可以進行的渡河操作中的最優操作，如果沒有找到則返回其父節點，看看是否有其它兄弟節點可以擴展，然後用Process(…)函數遞規調用FindNext(…)，一級一級的向後擴展。
搜索中採用的一些規則如下：
1、渡船優先規則：甲岸一次運走的人越多越好（即甲岸運多人優先），同時野人優先運走；
乙岸一次運走的人越少越好（即乙岸運少人優先），同時牧師優先運走；
2、不能重復上次渡船操作（通過鏈表中前一操作比較），避免進入死循環;
3、任何時候河兩邊的野人和牧師數均分別大於等於0且小於等於3；
4、由於只是找出最優解，所以當找到某一算符（當前最優先的）滿足操作條件後，不再搜索其兄弟節點，而是直接載入鏈表。
5、若擴展某節點a的時候，沒有找到合適的子節點，則從鏈表中返回節點a的父節點b，從上次已經選擇了的算符之後的算符中找最優先的算符繼續擴展b。

二、基本數據結構
仔細閱讀問題，可以發現有些基本東西我們必須把握，例如：每時刻河兩岸野人牧師各自的數目、船的狀態、整個問題狀態。所以我們定義如下幾個數據結構：
typedef struct _riverside // 岸邊狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}RIVERSIDE;
typedef struct _boat // 船的狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}BOAT;
typedef struct _question // 整個問題狀態
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸為-1, 乙岸為1
BOAT boat; // 船的狀態
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向後一渡船操作
}QUESTION;
用QUESTION來聲明一個最基本的鏈表。

三、程序流程及具體設計
本文只找出了最優解，據我所知，本問題有三種解。如果真要找出這三種解，^_^，那就得加強對鏈表的操作了，比如說自己寫一個動態鏈表類，順便完成一些初始化工作，估計看起來會舒服些。
下面給出部分關鍵程序：
// 主函數
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍歷鏈表輸出結果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎樣才能渡河呢? 郁悶!"<<endl;
// 回收內存空間
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}

// 渡船過程, 遞規調用函數FindNext(...)

BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 無解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父節點重新再找
}
return TRUE;
}

// 判斷有否下一個渡河操作, 即根據比較算符找出可以接近目標節點的操作
// 算符共5個: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本規則
// 渡船的優先順序: 甲岸運多人優先, 野人優先; 乙岸運少人優先, 牧師優先.
static BOAT boatState[5]; // 5個算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用來控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始狀態, 第一次渡河時
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 擴展同一節點時, 已經用過的算符不再用, 按優先順序來
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判斷本次操作的安全性, 即牧師數量>=野人或牧師數為0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重復上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 該操作可行, 推出循環，只找出當前最優節點
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;

}

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=21630

[點擊此處收藏本文] 發表於 2004年04月07日 2:18 PM

沒有評論。
發表評論

大名：
請輸入尊姓大名
網址：
驗證碼
評論
請輸入評論

記住我？

--------------------------------------------------------------------------------
網站簡介－廣告服務－網站地圖－幫助信息－聯系方式－English－問題報告

CSDN北京百聯美達美數碼科技有限公司 版權所有 京 ICP 證 020026 號 CSDN

&; 2000-04, CSDN.NET, All Rights Reserved

--------------------------------------------------------------------------------

Copyright &; paddy102 Powered By .Text

Ⅷ 猴子過河 java演算法

importjava.util.Arrays;
importjava.util.List;
importjava.util.Stack;

publicclassMonkey{
publicString[]monkeys={"a","b","c","A","B","C"};

Rulerule1=newRule1();

Rulerule2=newRule2();

publicintcount=0;

publicStringBuffersuccess=newStringBuffer(2000);

publicvoidboat(){
Stack<String>left=newStack<String>();
Stack<String>right=newStack<String>();
for(inti=0;i<monkeys.length;i++){
left.add(monkeys[i]);
}
go(left,right,"");
System.out.println("***********************共"+count+"種成功方案***********************");
System.out.println(success.toString());
System.out.println("***********************共"+count+"種成功方案***********************");

}

privatevoidgo(Stack<String>left,Stack<String>right,Strings){
for(inti=0;i<left.size();i++){
Stringmonkey1=left.get(i);
for(intj=i+1;j<left.size();j++){
StringBuffersb=newStringBuffer();
Stringmonkey2=left.get(j);
sb.append(s);
sb.append(monkey1);
sb.append(monkey2);
sb.append("->");
sb.append("");
if((rule1.isCanBoat(monkey1,monkey2,sb))&&(rule2.isCanBoat(monkey1,monkey2,sb))){
Stack<String>nextLeft=newStack<String>();
Stack<String>nextRight=newStack<String>();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.remove(monkey1);
nextLeft.remove(monkey2);

nextRight.push(monkey1);
nextRight.push(monkey2);

if(nextLeft.size()==0){
success.append(sb.toString()+nextLeft.toString()+nextRight.toString());
success.append("
");
count++;
continue;
}
back(nextLeft,nextRight,sb.toString());
}
}
}

}

privatevoidback(Stack<String>left,Stack<String>right,Strings){
for(inti=0;i<right.size();i++){
Stringmonkey1=right.get(i);
StringBuffersb=newStringBuffer();
sb.append(s);
sb.append(monkey1);
sb.append("<-");
sb.append("");
if(rule2.isCanBoat(monkey1,monkey1,sb)){
Stack<String>nextLeft=newStack<String>();
Stack<String>nextRight=newStack<String>();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.push(monkey1);
nextRight.remove(monkey1);
go(nextLeft,nextRight,sb.toString());
}
}
}

publicstaticvoidmain(String[]args){
Monkeymonkey=newMonkey();
monkey.boat();
}
}

interfaceRule{
booleanisCanBoat(Stringm1,Stringm2,StringBuffersb);
}

classRule1implementsRule{

String[]childMonkeys={"a","b","c"};

String[]monkeys={"A","B","C"};

publicbooleanisCanBoat(Stringm1,Stringm2,StringBuffersb){

if(m1.toLowerCase().equals(m2.toLowerCase())){
returntrue;
}
List<String>childMonkeysList=Arrays.asList(childMonkeys);
List<String>monkeysList=Arrays.asList(monkeys);
if((monkeysList.contains(m1)&&monkeysList.contains(m2))
||(childMonkeysList.contains(m1)&&childMonkeysList.contains(m2))){
returntrue;
}
sb.append("大猴欺負小猴！");
System.out.println(sb.toString());
returnfalse;
}

}

classRule2implementsRule{

String[]smartMonkeys={"A","B","C","a"};

publicbooleanisCanBoat(Stringm1,Stringm2,StringBuffersb){
List<String>smartMonkeysList=Arrays.asList(smartMonkeys);

if(smartMonkeysList.contains(m1)||smartMonkeysList.contains(m2)){
returntrue;
}
sb.append("沒有會劃船的猴子！");
System.out.println(sb.toString());
returnfalse;
}

}

Ⅸ 三個強盜三個商人過河 簡單的入門級別演算法

3個商人和3個強盜要過一條河,如果在河的任意一邊商人數目比強盜少,商人就會被搶劫,如何過河?

河邊有一隻小船，小船上原本無人，小船最多能坐2人，他們都不會去游泳，要保證商人不會被搶劫。

先簡化一下商人和強盜：

商人為0 強盜為X 河為-

初始情況：商人和強盜都在河的一邊，即000xxx-

操作步驟：

1商人1強盜過去 一商人回000xx-x

2強盜過去 1強盜回 000x-xx

2商人過去 1商人1強盜回 00xx-x0

2商人過去 1強盜回 xxx-000

2強盜過去 1強盜回 xx-000x

2強盜過去 完畢 -xxx000

Ⅹ 人鬼過河 演算法 c或java

import java.util.*;

public class RiverGame {
private boolean sf = true;
private final int pairs;
private final String PERSON = "1"; // 人
private final String GHOST = "2"; // 鬼
private List<String> leftCount; // 開始的岸上的人和鬼集合
private List<String> middleCount; // 船上的人和鬼集合
private List<String> rightCount; // 到達的岸上的人和鬼集合

public RiverGame (){
this(0);
}
public RiverGame (int count) {
if(count<3){
pairs = 3;
}else{
pairs = count;
}
leftCount = new ArrayList<String>();
for (int i = 0; i < pairs; i++) {
leftCount.add(PERSON);
leftCount.add(GHOST);
}
middleCount = new ArrayList<String>();
rightCount = new ArrayList<String>();
}

public int getCount(List<String> list, String name) {
int count = 0;
for (String s : list) {
if (name.equals(s)) {
count++;
}
}
return count;
}

public void leftToMiddle(String str1,String str2,int step){
int personCount = 0;
int ghostCount = 0;
if(str1.equals(PERSON)){
personCount++;
}else{
ghostCount++;
}
leftCount.remove(str1);
middleCount.add(str1);
if(str2 != null&&str2.equals(PERSON)){
personCount++;
leftCount.remove(str2);
middleCount.add(str2);
}else if(str2 != null&&str2.equals(GHOST)){
ghostCount++;
leftCount.remove(str2);
middleCount.add(str2);
}
System.out.println("第"+step+"步：");
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+"上船 ");
printc("過河 ");
}

public void middleToRight(String str1,String str2){
int personCount = 0;
int ghostCount = 0;
if(str1.equals(PERSON)){
personCount++;
}else{
ghostCount++;
}
middleCount.remove(str1);
rightCount.add(str1);
if(str2 != null&&str2.equals(PERSON)){
personCount++;
middleCount.remove(str2);
rightCount.add(str2);
}else if(str2 != null&&str2.equals(GHOST)){
ghostCount++;
middleCount.remove(str2);
rightCount.add(str2);
}
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+"上岸; ");
}

public void rightToMiddle(String str){
if(str != null){
rightCount.remove(str);
middleCount.add(str);
System.out.print(1+(str.equals(PERSON)?"人":"鬼")+"上船 ");
}
printc("回來 ");
}

public void middleToLeft(String str){
if(str != null){
middleCount.remove(str);
leftCount.add(str);
System.out.print(1+(str.equals(PERSON)?"人":"鬼")+"上岸 ");
}
System.out.println();
}

private void printc(String s){
int personCount = getCount(middleCount, PERSON);
int ghostCount = getCount(middleCount, GHOST);
System.out.print((personCount>0?personCount+"人":"")+(ghostCount>0?ghostCount+"鬼":"")+" "+s);
if(leftCount.contains(PERSON)&&getCount(leftCount, GHOST)>getCount(leftCount, PERSON)){
sf = false;
}else if(rightCount.contains(PERSON)&&getCount(rightCount, GHOST)>getCount(rightCount, PERSON)){
sf = false;
}
}

public void crossRiver() {
int step = 0;
while(leftCount.size() != 0){
step++;
if(leftCount.size()==pairs*2){
leftToMiddle(GHOST, GHOST,step);
middleToRight(GHOST,null);
rightToMiddle(null);
middleToLeft(null);
}else if(getCount(leftCount, PERSON)-2==getCount(leftCount, GHOST)&&middleCount.size()!=0){
leftToMiddle(GHOST, null,step);
middleToRight(GHOST,null);
rightToMiddle(null);
middleToLeft(GHOST);
}else if(getCount(leftCount, PERSON)-2==getCount(leftCount, GHOST)&&middleCount.size()==0){
leftToMiddle(PERSON, PERSON,step);
middleToRight(PERSON,null);
rightToMiddle(GHOST);
middleToLeft(GHOST);
}
else if(getCount(leftCount, PERSON)>getCount(leftCount, GHOST)){
leftToMiddle(PERSON, null,step);
middleToRight(PERSON,null);
rightToMiddle(null);
middleToLeft(null);
}else if(leftCount.contains(PERSON)){
leftToMiddle(PERSON, null, step);
middleToRight(PERSON,PERSON);
rightToMiddle(GHOST);
middleToLeft(null);
}else{
leftToMiddle(GHOST, null, step);
if(leftCount.size()==0){
middleToRight(GHOST,GHOST);
}else{
middleToRight(GHOST,null);
}
rightToMiddle(null);
middleToLeft(null);
}
if(!sf){
System.out.println("過河失敗！！！");
return;
}
}
System.out.println("成功過河了！");
}

public static void main(String[] args) {
RiverGame gr = new RiverGame ();
gr.crossRiver();
}
}

第1步：
2鬼上船 2鬼 過河 1鬼上岸; 1鬼 回來
第2步：
1鬼上船 2鬼 過河 1鬼上岸; 1鬼 回來 1鬼上岸
第3步：
2人上船 2人 過河 1人上岸; 1鬼上船 1人1鬼 回來 1鬼上岸
第4步：
1人上船 2人 過河 2人上岸; 1鬼上船 1鬼 回來
第5步：
1鬼上船 2鬼 過河 1鬼上岸; 1鬼 回來
第6步：
1鬼上船 2鬼 過河 2鬼上岸; 回來
成功過河了！