出个算法题，大家练练手【3个和尚和3个妖怪过河】

香川群子

题目很简单：
3个和尚和3个妖怪要过河，河里只有1个小船每次载2位。
限制条件是，河两岸、小船上必须保证和尚数量>=妖怪数量，否则妖怪多时就要吃掉和尚。

目的，安全过河。
求，过河的方法步骤，以及一共有多少种（最简）过河方法。（即重复步骤不算）

结论是，需要11步，只有4种解法。

	3	3				3	3				3	3				3	3
	3	1	0	2		3	1	0	2		2	2	1	1		2	2	1	1
	3	2	0	1		3	2	0	1		3	2	0	1		3	2	0	1
	3	0	0	3		3	0	0	3		3	0	0	3		3	0	0	3
	3	1	0	2		3	1	0	2		3	1	0	2		3	1	0	2
	1	1	2	2		1	1	2	2		1	1	2	2		1	1	2	2
	2	2	1	1		2	2	1	1		2	2	1	1		2	2	1	1
	0	2	3	1		0	2	3	1		0	2	3	1		0	2	3	1
	0	3	3	0		0	3	3	0		0	3	3	0		0	3	3	0
	0	1	3	2		0	1	3	2		0	1	3	2		0	1	3	2
	0	2	3	1		1	1	2	2		0	2	3	1		1	1	2	2
	0	0	3	3		0	0	3	3		0	0	3	3		0	0	3	3

第一行为起始状态，依次为和尚数、妖怪数、过河和尚数、过河妖怪数，所以是 3、3/0、0
最终的状态应该是：0、0/3、3

…………
请大家讨论解此题的算法过程。

一般说用递归算法比较好，过几天大家讨论充分后，我会详细进行递归算法的解剖，以便想要学习递归的坛友进步。

香川群子

算法要求是通解，小船固定一次只能载2位，但和尚数m和妖怪数n不确定时，都要能解出答案。
（即，和尚和妖怪数应设置为变量，而不是常数）

一般说m、n的限制条件为m>=n (否则一开始妖怪就要吃掉和尚了。)
当m>n时，解法会多一些，步骤数也不同。

例如，3个和尚2个妖怪时，有14种解法，步骤数从7到11


4个和尚4个妖怪时无解。

香川群子

此题用递归，同样可以有广度搜索和深度搜索两种做法，

关键是要避免重复步骤，即棋类比赛中的【同形重复】状态。
也就是说，走了几步以后出现和之前同样的状态时，这中间的步骤就是无效的。

这个是解题的关键之一。

香川群子

希望大家在不写出代码时，先进行充分的讨论。

锻炼一下形象思维能力。

excelvlookup

为什么不可以这样
1、送2个妖怪过去，空船返回。3、1；0、2
2、送2个和尚过去，空船返回。1、1；2、2
3、送1个妖怪1个和尚过去。    0、0；3、3
可能我没懂题哈

chaohuahch

excelvlookup 发表于 2018-9-2 20:27
为什么不可以这样
1、送2个妖怪过去，空船返回。3、1；0、2
2、送2个和尚过去，空船返回。1、1；2、2

话题都被你聊死了。没法聊了。哈哈！~

香川群子

excelvlookup 发表于 2018-9-2 20:27
为什么不可以这样
1、送2个妖怪过去，空船返回。3、1；0、2
2、送2个和尚过去，空船返回。1、1；2、2

空船怎么开？不要跟我说全球GPS自动驾驶仪。

香川群子

原来没人感兴趣。那我就不写下去了。

clyfd

香川群子 发表于 2018-9-2 20:41
空船怎么开？不要跟我说全球GPS自动驾驶仪。

逗死我啦。

ykqrs

第一步：两个妖过去，下一个妖，留一个妖开船返回，3-1；1；0-1
第二步：再上一个妖，下一个妖，留一个妖开船返回，3-0；1；0-2
第三步：上一个光头，到对岸后把妖推下，光头不上岸，开船跑回，2-0；1；0-3
第四步：上一个光头，到岸后一起下，把妖推一个上船开船返回，1-0；1；2-2
第五步：妖接光头一起走，0-0；0；3-3
也不知理解的对不对？