修道士和野人java_修道士和野人问题

亦凉 2022-11-09 12:31 13阅读 0赞

休闲时刻看看神经网络方面的书，发现了修道士和野人的问题，不禁勾引起我写算法的欲望，曾经的三只大老虎三只小老虎过河问题、人狼羊白菜过河问题、汉诺塔、哈夫曼等等各种算法瞬间在脑海中约隐约现，修道士和野人问题我以前好像没有解开，中午吃饭的时候在脑海中重新构造思路，下午耗了点时间把它干掉。(算法不在代码里，而在思想中；所以尽量不要看我的代码，而要仔细分析我写的思路)

题目：

设有３个修道士和３个野人来到河边， 打算用一条船从河的左岸渡到河的右岸。但该船每次只能装载两个人， 在任何岸边野人的数目都不得超过修道士的人数， 否则修道士就会被野人吃掉。假设野人服从任何一种过河安排， 请问如何规划过河计划才能把所有人都安全地渡过河去。

首先考虑总共有(3+1)\*(3+1)= 16 种不同的状态(因为左岸可以有0，1，2，3个传教士，左岸可以有0，1，2，3个野人)，所以可以考虑使用穷举法。

使用如下C\#程序语言：

int MaxNum = 3;for (int monk = MaxNum; monk >= 0; monk--)

\{for (int savage = MaxNum; savage >= 0; savage--)

Console.Write("\{ \{" + monk + "," + savage + "\},\{" + (MaxNum - monk) + "," + (MaxNum - savage) + "\}\}");

Console.Write("\\n");

生成16种状态图↓↓↓↓↓↓↓↓↓↓↓

状态图含义：

\{a,b\}：a，左岸修道士数量；b，左岸野人数量。

\--------仅考虑左岸传教士和野蛮人数量(所有状态图)------------------------\{3,3\} \{3,2\} \{3,1\} \{3,0\}

\{2,3\} \{2,2\} \{2,1\} \{2,0\}

\{1,3\} \{1,2\} \{1,1\} \{1,0\}

\{0,3\} \{0,2\} \{0,1\} \{0,0\}

其中\{3,3\}是起始状态图；\{0,0\}是终止状态图。

去除在任何岸边野人的人数超过修道士的人数，保留所有可满足的状态图：

\--------仅考虑左岸传教士和野蛮人数量(符合要求状态图)----------------------\{3,3\} \{3,2\} \{3,1\} \{3,0\}

\{2,2\}

\{1,1\}

\{0,3\} \{0,2\} \{0,1\} \{0,0\}

可知，左岸修道士和野人的总数是先减少、再增加、再减少、再增加...直到左岸的总人数为零(这个由船行动的方向决定的，请仔细思考)，所求的最终状态图 \{0,0\}，而且每次增减人数最多为2个(条件提示：该船每次只能装载两个人)，由此可知左岸总人数的增减趋势是： -1或-2、+1或+2、-1或-2、+1或+2...。

左岸人头数作为参照：

\--------仅考虑左岸传教士和野蛮人数量(分组)------------------------

heads num：6 \{3,3\}

heads num：5 \{3,2\}

heads num：4 \{3,1\} \{2,2\}

heads num：3 \{3,0\} \{0,3\}

heads num：2 \{1,1\} \{0,2\}

heads num：1 \{0,1\}

heads num：0 \{0,0\}

将船的停靠岸考虑在内，其中L、R分别表示船在左岸或右岸：

\--------仅考虑左岸传教士和野蛮人数量,以及船的状态------------------------

heads num：6 \{3,3,L\}

heads num：5 \{3,2,L\} \{3,2,R\}

heads num：4 \{3,1,L\} \{3,1,R\} \{2,2,L\} \{2,2,R\}

heads num：3 \{3,0,L\} \{3,0,R\} \{0,3,L\} \{0,3,R\}

heads num：2 \{1,1,L\} \{1,1,R\} \{0,2,L\} \{0,2,R\}

heads num：1 \{0,1,L\} \{0,1,R\}

heads num：0 \{0,0,R\}

此时，初始状态图为 \{3,3,L\}，终止状态图为\{0,0,R\}。

其实讲到这里，几乎答案已经很明显了。上面已经提到：左岸总人数的增减趋势是： -1或-2、+1或+2、-1或-2、+1或+2...，假设每种状态图只能使用一次，按照-1或-2、+1或+2的循环模式的增长趋势，可得到如下几种走法：

\--------可能的路径----------------------------------------

\{3,3,L\} \{3,1,R\} \{3,2,L\} \{3,0,R\} \{3,1,L\} \{1,1,R\} \{2,2,L\} \{0,2,R\} \{0,3,L\} \{0,1,R\} \{0,2,L\} \{0,0,R\}

\{3,3,L\} \{3,1,R\} \{3,2,L\} \{3,0,R\} \{3,1,L\} \{1,1,R\} \{2,2,L\} \{0,2,R\} \{0,3,L\} \{0,1,R\} \{1,1,L\} \{0,0,R\}

\{3,3,L\} \{2,2,R\} \{3,2,L\} \{3,0,R\} \{3,1,L\} \{1,1,R\} \{2,2,L\} \{0,2,R\} \{0,3,L\} \{0,1,R\} \{0,2,L\} \{0,0,R\}

\{3,3,L\} \{2,2,R\} \{3,2,L\} \{3,0,R\} \{3,1,L\} \{1,1,R\} \{2,2,L\} \{0,2,R\} \{0,3,L\} \{0,1,R\} \{1,1,L\} \{0,0,R\}

![8f900a89c6347c561fdf2122f13be562.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespaceConsoleApplication1

\{public enumState

Left, Right

\}public classRiverBank

\{public State state =State.Left;public int monk = 0;public int savage = 0;public bool used = false;

\}public classItem

\{public int index = 0;public List list = new List();

\}classProgram

\{const int MaxNum = 3;static State state =State.Left;publicState GetState

\{get\{

State r=state;

state= (state == State.Left ?State.Right : State.Left);returnr;

\}static void Add(List list, int index, paramsRiverBank\[\] objs)

\{foreach (Item i inlist)

\{if (i.index ==index)

\{foreach (RiverBank ii inobjs)

\{bool flag = true;for (int iii = 0; iii < i.list.Count; iii++)

\{if (i.list\[iii\].monk == ii.monk && i.list\[iii\].monk == ii.monk && i.list\[iii\].state ==ii.state)

flag= false;break;

\}if(flag)

i.list.Add(ii);

\}return;

Item item= newItem();

item.index=index;

item.list.AddRange(objs);

list.Add(item);

\}static voidWriteDivInfo(String msg)

Console.WriteLine("\\n--------" + msg.PadRight(45, ‘-‘));

\}static void WriteInfo(ListriverBankList)

\{foreach (var i inriverBankList)

Console.Write("\{" + i.monk + "," + i.savage + "," + (i.state == State.Right ? "R" : "L") + "\}");

Console.WriteLine();

\}static void Main(string\[\] args)

List list = new List();

WriteDivInfo("仅考虑左岸传教士和野蛮人数量(所有状态图)");for (int monk = MaxNum; monk >= 0; monk--)

\{for (int savage = MaxNum; savage >= 0; savage--)

Console.Write("\{" + monk + "," + savage + "\}\\t");

Console.Write("\\n");

WriteDivInfo("仅考虑左岸传教士和野蛮人数量(符合要求状态图)");for (int monk = MaxNum; monk >= 0; monk--)

\{for (int savage = MaxNum; savage >= 0; savage--)

\{if (monk == 0 || monk == MaxNum || monk ==savage)

\{int index = monk +savage;//RiverBank p = new RiverBank \{ monk = monk, savage = savage \};//Add(list, index, p);

if (index > 0)

RiverBank p= new RiverBank \{ monk = monk, savage = savage, state =State.Left \};

Add(list, index, p);

\}if (index < 2 \*MaxNum)

RiverBank p= new RiverBank \{ monk = monk, savage = savage, state =State.Right \};

Add(list, index, p);

Console.Write("\{" + monk + "," + savage + "\}\\t");

\}else\{

Console.Write("\\t");

Console.Write("\\n");

WriteDivInfo("仅考虑左岸传教士和野蛮人数量,以及船的状态");foreach (Item item inlist)

Console.Write("heads num：" + item.index + "\\t");foreach (RiverBank i initem.list)

\{//Console.Write("\{" + i.monk + "," + i.savage + "\} ");

Console.Write("\{" + i.monk + "," + i.savage + "," + (i.state == State.Right ? "R" : "L") + "\}");

Console.Write("\\n");

list.Sort((a, b)=> \{ return a.index < b.index ? 1 : -1; \});

WriteDivInfo("可能的路径");

List usedList = new List();

list\[0\].list\[0\].used = true;

usedList.Add(list\[0\].list\[0\]);

Cycle(ref list, refusedList);

Console.ReadKey();

\}private static void Cycle(ref List list, ref ListusedList)

RiverBank item= usedList\[usedList.Count - 1\];

State state=item.state;int monk =item.monk;int savage =item.savage;for (int i = 1; i <= 2; i++)

\{//±1或±2

for (int j = 0; j <= i; j++)

\{//每次变化的传教士数

int k = i - j;//每次变化的野人数

int value = (state == State.Left ? -1 : 1);int m = monk + j \*value;int s = savage + k \*value;if (m == 0 && s == 0 && state ==State.Left)

list\[6\].list\[0\].used = true;

usedList.Add(list\[6\].list\[0\]);

WriteInfo(usedList);

list\[6\].list\[0\].used = false;

usedList.Remove(list\[6\].list\[0\]);

\}else if (m >= 0 && s >= 0 && m <= MaxNum && s <=MaxNum)

\{foreach (var it inlist)

\{foreach (var v init.list)

\{if (v.used == false && v.state != state && v.monk == m && v.savage ==s)

v.used= true;

usedList.Add(v);

Cycle(ref list, refusedList);

v.used= false;

usedList.Remove(v);

源代码

原文：http://www.cnblogs.com/preacher/p/5997442.html

[8f900a89c6347c561fdf2122f13be562.png]: /images/20221023/3d14c1147aaa4b05bbf44cac2a4ac752.png
[961ddebeb323a10fe0623af514929fc1.png]: /images/20221023/8332e82daa144acfa48a529660f92f4b.png