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

老刘1号 · 发表于 2019-3-16 12:09:41

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

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

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

xczxczxcz · 发表于 2019-3-16 16:48:44

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

$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 "人返回" }
}
}
}

复制代码

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

老刘1号 · 发表于 2019-3-16 17:38:51

回复 2# xczxczxcz

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

老刘1号 · 发表于 2019-3-16 17:59:14

回复 2# xczxczxcz

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

523066680 · 发表于 2019-3-16 22:30:19

本帖最后由 523066680 于 2019-3-16 22:35 编辑

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

老刘1号 · 发表于 2019-3-16 22:57:21

回复 5# 523066680

其实这个很简单的

523066680 · 发表于 2019-3-16 23:06:21

回复 6# 老刘1号

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

老刘1号 · 发表于 2019-3-16 23:09:27

回复 7# 523066680

是的

xczxczxcz · 发表于 2019-3-22 15:40:17

本帖最后由 xczxczxcz 于 2019-3-22 15:58 编辑

补充完整，去重复。

[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号 · 发表于 2019-3-24 22:45:02

本帖最后由老刘1号于 2019-3-24 22:49 编辑

我已深深迷上撸啊的语法
在线运行：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)
人带着最后余下的过岸。

523066680 · 发表于 2019-3-25 09:26:22

本帖最后由 523066680 于 2019-3-25 09:33 编辑

回复 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号 · 发表于 2019-3-25 10:51:07

回复 11# 523066680

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

523066680 · 发表于 2019-3-25 11:13:16

回复 12# 老刘1号

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

老刘1号 · 发表于 2019-3-25 12:26:58

回复 13# 523066680

评论区都是人才

		自动登录	找回密码
密码			注册

[新手上路]批处理新手入门导读	[视频教程]批处理基础视频教程	[视频教程]VBS基础视频教程	[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动	[批处理精品]CMD命令50条不能说的秘密	[在线下载]第三方命令行工具	[在线帮助]VBScript / JScript 在线参考

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

评分

评分

浏览过的版块