不限语言解决“人狼羊菜过河问题”
哈哈，看来工作日大家都忙着，今天再来一个类似的[quote]题目描述：农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。[/quote]
参考：[url]https://blog.csdn.net/orbit/article/details/7563220[/url] 随机一种；因未考虑重复步骤。没有用循环。[code]
$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 "人 返回" }
}
}
}
[/code]每次运行都会有一种方法。把随机数改循环可以计算所有。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218272&ptid=52289]2#[/url] [i]xczxczxcz[/i] [/b]
哈哈，这个解法比较清奇，
不过若改成循环，恐怕无法正常运行，
试想一下，是否会出现羊被拉来拉去不断死循环下去的情况？ [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218272&ptid=52289]2#[/url] [i]xczxczxcz[/i] [/b]
若不考虑重复步骤，准确的说应该是执行步骤造成的状态与历史重复，也就无所谓“所有”解法，因为通过重复获得状态，步骤可以被无限延长，也就是可以获得无限种解法
若论有限解法的数目，这里有一个隐含条件，就是剔除重复状态。之所以没有在帖子上特别强调，是因为若真的写出获得所有解的代码来，必定会剔除掉重复状态，否则代码执行就永远不会结束。 [i=s] 本帖最后由 523066680 于 2019-3-16 22:35 编辑 [/i]
记得《算法谜题》里面有这两道。
最近看到题目就绕道，学得太少，加上脑袋也僵化了，空想太耗时（逃 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218292&ptid=52289]5#[/url] [i]523066680[/i] [/b]
其实这个很简单的:D [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218294&ptid=52289]6#[/url] [i]老刘1号[/i] [/b]
上一道我一看就蒙，人是一定要在船上的吗？光这个就开始纠结了，算了还是不去纠结了 —— 放弃。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218296&ptid=52289]7#[/url] [i]523066680[/i] [/b]
是的 [i=s] 本帖最后由 xczxczxcz 于 2019-3-22 15:58 编辑 [/i]
补充完整，去重复。[code]
[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 };
}
}[/code]随机一组，没有反复过程。编辑美化了一下。 [i=s] 本帖最后由 老刘1号 于 2019-3-24 22:49 编辑 [/i]
我已深深迷上撸啊的语法
在线运行：[url]https://tool.lu/coderunner/embed/6hX.html[/url]
状态不重复内只有两个解：
[quote]方法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)
人带着最后余下的过岸。[/quote] [i=s] 本帖最后由 523066680 于 2019-3-25 09:33 编辑 [/i]
[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218617&ptid=52289]10#[/url] [i]老刘1号[/i] [/b]
《算法谜题》英文版
[url]http://booksdescr.org/item/index.php?md5=ECF78B0903AEBE970CD2C9C83A605B6E[/url]
第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），然后数量更多的问题的解可以从基础版本的答案中扩展得到。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218628&ptid=52289]11#[/url] [i]523066680[/i] [/b]
感谢分享，分析可以看顶楼的链接 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218634&ptid=52289]12#[/url] [i]老刘1号[/i] [/b]
评论摘选：
农夫山泉有点甜！ [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=218636&ptid=52289]13#[/url] [i]523066680[/i] [/b]
评论区都是人才
页:
[1]