不限语言解决“人狼羊菜过河问题”

老刘1号

哈哈，看来工作日大家都忙着，今天再来一个类似的

题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。

参考：https://blog.csdn.net/orbit/article/details/7563220

老刘1号

回复 13# 523066680


    评论区都是人才

523066680

回复 12# 老刘1号

评论摘选：
     农夫山泉有点甜！

老刘1号

回复 11# 523066680


    感谢分享，分析可以看顶楼的链接

523066680

回复 10# 老刘1号
《算法谜题》英文版
http://booksdescr.org/item/index ... E970CD2C9C83A605B6E
第42道，有些相似的地方，不过这个更像是单纯的排列，不考虑两岸的问题。
42. The Other Wolf-Goat-Cabbage Puzzle
You have 4n counters of four types: n wolfs, n goats, n cabbages, and
n hunters. The object is to place the counters in a row such that no one is in
danger; that is, no hunter is next to a wolf, no wolf is next to a goat, and no
goat is next to a cabbage. In addition, no two counters of the same kind may
be next to each other either. How many ways are there to solve the puzzle?

解位于 116 页
Solution Let W, G, C, and H represent a wolf, a goat, a cabbage, and a hunter,
respectively. Then the puzzle has two symmetric solutions:
WCWC. . . WCHGHG . . . HG and GHGH . . . GHCWCW . . . CW.

令狼羊菜猎人分别为 W G C H，他们的数量一样（n），则该问题有两种对称解
WCWC. . . WC+HGHG . . . HG  和 GHGH . . . GH+CWCW . . . CW

当 n = 1 的时候，元素较少，很容易推算出两种结果： WCHG 和 GHCW，当N=2的时候，在1的基础上叠加：
WCWCHGHG 和 GHGHCWCW，以此类推。
（中间还有一段证明请看原PDF）

Comments: The solution to the puzzle can be considered based on decrease-andconquer
applied bottom up: the solution is obtained by solving smaller instances of
the same puzzle first and then extending their solutions to form the same patterns.
注：此问题可以采用减而治之的方案，将问题简化为最简版本（n=1），然后数量更多的问题的解可以从基础版本的答案中扩展得到。

老刘1号

我已深深迷上撸啊的语法
在线运行：https://tool.lu/coderunner/embed/6hX.html
状态不重复内只有两个解：

方法1
人羊过岸。(1,2,1,2)
人回来。(1,2,1,1)
人狼过岸。(2,2,1,2)
人羊回来。(2,1,1,1)
人菜过岸。(2,1,2,2)
人回来。(2,1,2,1)
人带着最后余下的过岸。

方法2
人羊过岸。(1,2,1,2)
人回来。(1,2,1,1)
人菜过岸。(1,2,2,2)
人羊回来。(1,1,2,1)
人狼过岸。(2,1,2,2)
人回来。(2,1,2,1)
人带着最后余下的过岸。

xczxczxcz

补充完整，去重复。

[Collections.Arraylist] $one = @('狼','羊','菜');
[Collections.Arraylist] $two = @();
$back = $null;
While ( $one.count -gt 0 ) {
	$ref = Get-Random $one -count 1;
	if ( $ref -ne $back ) { $one.remove($ref) }
	if ( $two -notcontains $ref ) { $null = $two.add($ref) };
	if ( ($one -contains '狼' -and $one -contains '羊') -or `
	( $one -contains '羊' -and $one -contains '菜') ) {
		$null = $one.add($ref);
		$two.remove($ref);
	} else {
		if ( $two.count -lt 3 ) {
			Write-host "人+$ref 过河 → " -fore green -NoNewLine;
			if ( $two.Count -eq 2 ) {
				if ( ($two -contains '狼' -and $two -contains '羊') -or `
				( $two -contains '羊' -and $two -contains '菜') ) {
					if ( $two[0] -ne $ref ) { $back = $two[0] } else { $back = $two[1] };
					$null = $one.add($back);
					$two.remove($back);
					Write-host "人+$back 返回" -fore yellow;
				} else { Write-host "人 返回" }
			} else { Write-host "人 返回" }
		} else { Write-host "人+$ref 过河 Over" -fore red; break };
	}
}
复制代码

随机一组，没有反复过程。编辑美化了一下。

老刘1号

回复 7# 523066680


    是的

523066680

回复 6# 老刘1号


    上一道我一看就蒙，人是一定要在船上的吗？光这个就开始纠结了，算了还是不去纠结了 —— 放弃。

老刘1号

回复 5# 523066680


    其实这个很简单的

523066680

记得《算法谜题》里面有这两道。
最近看到题目就绕道，学得太少，加上脑袋也僵化了，空想太耗时（逃

老刘1号

回复 2# xczxczxcz


    若不考虑重复步骤，准确的说应该是执行步骤造成的状态与历史重复，也就无所谓“所有”解法，因为通过重复获得状态，步骤可以被无限延长，也就是可以获得无限种解法
若论有限解法的数目，这里有一个隐含条件，就是剔除重复状态。之所以没有在帖子上特别强调，是因为若真的写出获得所有解的代码来，必定会剔除掉重复状态，否则代码执行就永远不会结束。

老刘1号

回复 2# xczxczxcz


    哈哈，这个解法比较清奇，
不过若改成循环，恐怕无法正常运行，
试想一下，是否会出现羊被拉来拉去不断死循环下去的情况？

xczxczxcz

随机一种；因未考虑重复步骤。没有用循环。

$one = @{'狼'='';'羊'='';'菜'=''};
$two = @{};
While ( $one.count -gt 0 ) {
	$ref1 = Get-Random @($one.keys) -count 1;
	$one.remove($ref1);
	if ( $two.kes -notcontains $ref1 ) { $two.add($ref1,'') };

	if ( ($one.keys -contains '狼' -and $one.keys -contains '羊') -or `
	( $one.keys -contains '羊' -and $one.keys -contains '菜') ) {
		$one.add($ref1,'');
		$two.remove($ref1);
	} else {
		Write-host "人+$ref1 过河" -fore green;
		if ( $two.count -lt 3 ) {
			if ( ($two.keys -contains '狼' -and $two.keys -contains '羊') -or `
			( $two.keys -contains '羊' -and $two.keys -contains '菜') ) {
				$ref2 = Get-Random @($two.keys) -count 1;
				$one.add($ref2,'');
				$two.remove($ref2);
				Write-host "人+$ref2 返回" -fore yellow;
			} else { Write-host "人 返回" }
		}
	}
}
复制代码

每次运行都会有一种方法。把随机数改循环可以计算所有。