标题: 不限语言解决“人狼羊菜过河问题” [打印本页]
作者: 老刘1号 时间: 2019-3-16 12:09 标题: 不限语言解决“人狼羊菜过河问题”
哈哈,看来工作日大家都忙着,今天再来一个类似的
题目描述:农夫需要把狼、羊、菜和自己运到河对岸去,只有农夫能够划船,而且船比较小,除农夫之外每次只能运一种东西,还有一个棘手问题,就是如果没有农夫看着,羊会偷吃菜,狼会吃羊。请考虑一种方法,让农夫能够安全地安排这些东西和他自己过河。
参考:https://blog.csdn.net/orbit/article/details/7563220
作者: xczxczxcz 时间: 2019-3-16 16:48
随机一种;因未考虑重复步骤。没有用循环。- $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
回复 2# xczxczxcz
哈哈,这个解法比较清奇,
不过若改成循环,恐怕无法正常运行,
试想一下,是否会出现羊被拉来拉去不断死循环下去的情况?
作者: 老刘1号 时间: 2019-3-16 17:59
回复 2# xczxczxcz
若不考虑重复步骤,准确的说应该是执行步骤造成的状态与历史重复,也就无所谓“所有”解法,因为通过重复获得状态,步骤可以被无限延长,也就是可以获得无限种解法
若论有限解法的数目,这里有一个隐含条件,就是剔除重复状态。之所以没有在帖子上特别强调,是因为若真的写出获得所有解的代码来,必定会剔除掉重复状态,否则代码执行就永远不会结束。
作者: 523066680 时间: 2019-3-16 22:30
本帖最后由 523066680 于 2019-3-16 22:35 编辑
记得《算法谜题》里面有这两道。
最近看到题目就绕道,学得太少,加上脑袋也僵化了,空想太耗时(逃
作者: 老刘1号 时间: 2019-3-16 22:57
回复 5# 523066680
其实这个很简单的
作者: 523066680 时间: 2019-3-16 23:06
回复 6# 老刘1号
上一道我一看就蒙,人是一定要在船上的吗?光这个就开始纠结了,算了还是不去纠结了 —— 放弃。
作者: 老刘1号 时间: 2019-3-16 23:09
回复 7# 523066680
是的
作者: xczxczxcz 时间: 2019-3-22 15:40
本帖最后由 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
本帖最后由 老刘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
本帖最后由 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
回复 11# 523066680
感谢分享,分析可以看顶楼的链接
作者: 523066680 时间: 2019-3-25 11:13
回复 12# 老刘1号
评论摘选:
农夫山泉有点甜!
作者: 老刘1号 时间: 2019-3-25 12:26
回复 13# 523066680
评论区都是人才
欢迎光临 批处理之家 (http://www.bathome.net/) |
Powered by Discuz! 7.2 |