Board logo

标题: 不限语言解决“人狼羊菜过河问题” [打印本页]

作者: 老刘1号    时间: 2019-3-16 12:09     标题: 不限语言解决“人狼羊菜过河问题”

哈哈,看来工作日大家都忙着,今天再来一个类似的
题目描述:农夫需要把狼、羊、菜和自己运到河对岸去,只有农夫能够划船,而且船比较小,除农夫之外每次只能运一种东西,还有一个棘手问题,就是如果没有农夫看着,羊会偷吃菜,狼会吃羊。请考虑一种方法,让农夫能够安全地安排这些东西和他自己过河。

参考:https://blog.csdn.net/orbit/article/details/7563220
作者: xczxczxcz    时间: 2019-3-16 16:48

随机一种;因未考虑重复步骤。没有用循环。
  1. $one = @{'狼'='';'羊'='';'菜'=''};
  2. $two = @{};
  3. While ( $one.count -gt 0 ) {
  4. $ref1 = Get-Random @($one.keys) -count 1;
  5. $one.remove($ref1);
  6. if ( $two.kes -notcontains $ref1 ) { $two.add($ref1,'') };
  7. if ( ($one.keys -contains '狼' -and $one.keys -contains '羊') -or `
  8. ( $one.keys -contains '羊' -and $one.keys -contains '菜') ) {
  9. $one.add($ref1,'');
  10. $two.remove($ref1);
  11. } else {
  12. Write-host "人+$ref1 过河" -fore green;
  13. if ( $two.count -lt 3 ) {
  14. if ( ($two.keys -contains '狼' -and $two.keys -contains '羊') -or `
  15. ( $two.keys -contains '羊' -and $two.keys -contains '菜') ) {
  16. $ref2 = Get-Random @($two.keys) -count 1;
  17. $one.add($ref2,'');
  18. $two.remove($ref2);
  19. Write-host "人+$ref2 返回" -fore yellow;
  20. } else { Write-host "人 返回" }
  21. }
  22. }
  23. }
复制代码
每次运行都会有一种方法。把随机数改循环可以计算所有。
作者: 老刘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 编辑

补充完整,去重复。
  1. [Collections.Arraylist] $one = @('狼','羊','菜');
  2. [Collections.Arraylist] $two = @();
  3. $back = $null;
  4. While ( $one.count -gt 0 ) {
  5. $ref = Get-Random $one -count 1;
  6. if ( $ref -ne $back ) { $one.remove($ref) }
  7. if ( $two -notcontains $ref ) { $null = $two.add($ref) };
  8. if ( ($one -contains '狼' -and $one -contains '羊') -or `
  9. ( $one -contains '羊' -and $one -contains '菜') ) {
  10. $null = $one.add($ref);
  11. $two.remove($ref);
  12. } else {
  13. if ( $two.count -lt 3 ) {
  14. Write-host "人+$ref 过河 → " -fore green -NoNewLine;
  15. if ( $two.Count -eq 2 ) {
  16. if ( ($two -contains '狼' -and $two -contains '羊') -or `
  17. ( $two -contains '羊' -and $two -contains '菜') ) {
  18. if ( $two[0] -ne $ref ) { $back = $two[0] } else { $back = $two[1] };
  19. $null = $one.add($back);
  20. $two.remove($back);
  21. Write-host "人+$back 返回" -fore yellow;
  22. } else { Write-host "人 返回" }
  23. } else { Write-host "人 返回" }
  24. } else { Write-host "人+$ref 过河 Over" -fore red; break };
  25. }
  26. }
复制代码
随机一组,没有反复过程。编辑美化了一下。
作者: 老刘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