批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程
[批处理文件精品]批处理版照片整理器[批处理文件精品]纯批处理备份&还原驱动在线第三方下载
返回列表 发帖

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

本帖最后由 老刘1号 于 2019-3-15 08:34 编辑

某算法课程中看到的一个题,
一个人带三只狼和三只羚羊过河,只有一条船,同船可以容纳一个人和两只动物。没有人在的时候,如果狼的数量不少于羚羊的数量,狼就会吃掉羚羊。请编程求过河方案。

据说练回溯很好,欢迎大家回帖分享自己的代码

vbs版(无效率可言,仅为粗略实现)
  1. Rem Code By 老刘
  2. todo=Array("[人去对岸]","[人回该岸]","[带1狼去对岸]","[带2狼去对岸]","[带1狼回该岸]","[带2狼回该岸]","[带1羊去对岸]","[带2羊去对岸]","[带1羊回该岸]","[带2羊回该岸]","[带狼羊去对岸]","[带狼羊回该岸]")
  3. Dim [方法]
  4. [方法] = 1
  5. recursion New [三狼三羊过河问题],"3,0,3,0,1",""
  6. Sub recursion(ByRef obj,ByVal StatusLog,byVal StepLog)
  7. Dim nowStatus
  8. nowStatus = Join(obj.[当前情形],",")
  9. If nowStatus = "0,3,0,3,2" Then
  10. wsh.echo "方法"&[方法]&StepLog&vbNewLine
  11. [方法] = [方法] + 1
  12. Else
  13. For i = 0 To UBound(todo)
  14. If Eval("obj."&todo(i)) = True Then
  15. If InStr(StatusLog,Join(obj.[当前情形],",")) = 0 Then '避免执行步骤恢复到以前状态,陷入死循环
  16. recursion obj,StatusLog & vbNewLine & Join(obj.[当前情形],","),StepLog & vbNewLine & todo(i)
  17. End If
  18. End If
  19. Execute "obj.[加载情形] " & nowStatus
  20. Next
  21. End If
  22. End Sub
  23. Class [三狼三羊过河问题]
  24. Private [该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置]
  25. Private Sub Class_Initialize
  26. [该岸羊数] = 3
  27. [对岸羊数] = 0
  28. [该岸狼数] = 3
  29. [对岸狼数] = 0
  30. [人的位置] = 1 '表示该岸,2为对岸
  31. End Sub
  32. Public Sub [加载情形](a,b,c,d,e)
  33. [该岸羊数] = a
  34. [对岸羊数] = b
  35. [该岸狼数] = c
  36. [对岸狼数] = d
  37. [人的位置] = e
  38. End Sub
  39. Public Function [当前情形]
  40. [当前情形] = Array([该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置])
  41. End Function
  42. Private Function [可行性分析]
  43. If [人的位置] = 1 Then '人在该岸
  44. If [对岸狼数] >= [对岸羊数] And [对岸羊数] >= 1 Then
  45. [可行性分析] = False '对岸狼会吃羊
  46. Else
  47. [可行性分析] = True
  48. End If
  49. Else '人在对岸
  50. If [该岸狼数] >= [该岸羊数] And [该岸羊数] >= 1 Then
  51. [可行性分析] = False '该岸狼会吃羊
  52. Else
  53. [可行性分析] = True
  54. End If
  55. End If
  56. End Function
  57. Public Function [人去对岸]
  58. If [人的位置] = 2 Then
  59. [人去对岸] = False
  60. Else
  61. [人的位置] = 2
  62. If [可行性分析] = False Then
  63. [人的位置] = 1
  64. [人去对岸] = False '操作不可行
  65. Else
  66. [人去对岸] = True '操作可行
  67. End If
  68. End If
  69. End Function
  70. Public Function [人回该岸]
  71. If [人的位置] = 1 Then
  72. [人回该岸] = False
  73. Else
  74. [人的位置] = 1
  75. If [可行性分析] = False Then
  76. [人的位置] = 2
  77. [人回该岸] = False '操作不可行
  78. Else
  79. [人回该岸] = True '操作可行
  80. End If
  81. End If
  82. End Function
  83. Public Function [带1狼去对岸]
  84. If [人的位置] = 2 Then
  85. [带1狼去对岸] = False
  86. Else
  87. If [该岸狼数] = 0 Then '该岸无狼
  88. [带1狼去对岸] = False
  89. Else
  90. [人的位置] = 2
  91. [该岸狼数] = [该岸狼数] - 1
  92. [对岸狼数] = [对岸狼数] + 1
  93. If [可行性分析] = False Then
  94. [带1狼去对岸] = False
  95. Else
  96. [带1狼去对岸] = True
  97. End If
  98. End If
  99. End If
  100. End Function
  101. Public Function [带2狼去对岸]
  102. If [人的位置] = 2 Then
  103. [带2狼去对岸] = False
  104. Else
  105. If [该岸狼数] <= 1 Then '该岸狼不够
  106. [带2狼去对岸] = False
  107. Else
  108. [人的位置] = 2
  109. [该岸狼数] = [该岸狼数] - 2
  110. [对岸狼数] = [对岸狼数] + 2
  111. If [可行性分析] = False Then
  112. [带2狼去对岸] = False
  113. Else
  114. [带2狼去对岸] = True
  115. End If
  116. End If
  117. End If
  118. End Function
  119. Public Function [带1狼回该岸]
  120. If [人的位置] = 1 Then
  121. [带1狼回该岸] = False
  122. Else
  123. If [对岸狼数] = 0 Then '对岸无狼
  124. [带1狼回该岸] = False
  125. Else
  126. [人的位置] = 1
  127. [该岸狼数] = [该岸狼数] + 1
  128. [对岸狼数] = [对岸狼数] - 1
  129. If [可行性分析] = False Then
  130. [带1狼回该岸] = False
  131. Else
  132. [带1狼回该岸] = True
  133. End If
  134. End If
  135. End If
  136. End Function
  137. Public Function [带2狼回该岸]
  138. If [人的位置] = 1 Then
  139. [带2狼回该岸] = False
  140. Else
  141. If [对岸狼数] <= 1 Then '对岸狼不够
  142. [带2狼回该岸] = False
  143. Else
  144. [人的位置] = 1
  145. [该岸狼数] = [该岸狼数] + 2
  146. [对岸狼数] = [对岸狼数] - 2
  147. If [可行性分析] = False Then
  148. [带2狼回该岸] = False
  149. Else
  150. [带2狼回该岸] = True
  151. End If
  152. End If
  153. End If
  154. End Function
  155. Public Function [带1羊去对岸]
  156. If [人的位置] = 2 Then
  157. [带1羊去对岸] = False
  158. Else
  159. If [该岸羊数] = 0 Then '该岸无羊
  160. [带1羊去对岸] = False
  161. Else
  162. [人的位置] = 2
  163. [该岸羊数] = [该岸羊数] - 1
  164. [对岸羊数] = [对岸羊数] + 1
  165. If [可行性分析] = False Then
  166. [带1羊去对岸] = False
  167. Else
  168. [带1羊去对岸] = True
  169. End If
  170. End If
  171. End If
  172. End Function
  173. Public Function [带2羊去对岸]
  174. If [人的位置] = 2 Then
  175. [带2羊去对岸] = False
  176. Else
  177. If [该岸羊数] <= 1 Then '该岸羊不够
  178. [带2羊去对岸] = False
  179. Else
  180. [人的位置] = 2
  181. [该岸羊数] = [该岸羊数] - 2
  182. [对岸羊数] = [对岸羊数] + 2
  183. If [可行性分析] = False Then
  184. [带2羊去对岸] = False
  185. Else
  186. [带2羊去对岸] = True
  187. End If
  188. End If
  189. End If
  190. End Function
  191. Public Function [带1羊回该岸]
  192. If [人的位置] = 1 Then
  193. [带1羊回该岸] = False
  194. Else
  195. If [对岸羊数] = 0 Then '对岸无羊
  196. [带1羊回该岸] = False
  197. Else
  198. [人的位置] = 1
  199. [该岸羊数] = [该岸羊数] + 1
  200. [对岸羊数] = [对岸羊数] - 1
  201. If [可行性分析] = False Then
  202. [带1羊回该岸] = False
  203. Else
  204. [带1羊回该岸] = True
  205. End If
  206. End If
  207. End If
  208. End Function
  209. Public Function [带2羊回该岸]
  210. If [人的位置] = 1 Then
  211. [带2羊回该岸] = False
  212. Else
  213. If [对岸羊数] <= 1 Then '对岸羊不够
  214. [带2羊回该岸] = False
  215. Else
  216. [人的位置] = 1
  217. [该岸羊数] = [该岸羊数] + 2
  218. [对岸羊数] = [对岸羊数] - 2
  219. If [可行性分析] = False Then
  220. [带2羊回该岸] = False
  221. Else
  222. [带2羊回该岸] = True
  223. End If
  224. End If
  225. End If
  226. End Function
  227. Public Function [带狼羊去对岸]
  228. If [人的位置] = 2 Then
  229. [带狼羊去对岸] = False
  230. Else
  231. If [该岸羊数] = 0 Or [该岸狼数] = 0 Then
  232. [带狼羊去对岸] = False
  233. Else
  234. [人的位置] = 2
  235. [该岸羊数] = [该岸羊数] - 1
  236. [对岸羊数] = [对岸羊数] + 1
  237. [该岸狼数] = [该岸狼数] - 1
  238. [对岸狼数] = [对岸狼数] + 1
  239. If [可行性分析] = False Then
  240. [带狼羊去对岸] = False
  241. Else
  242. [带狼羊去对岸] = True
  243. End If
  244. End If
  245. End If
  246. End Function
  247. Public Function [带狼羊回该岸]
  248. If [人的位置] = 1 Then
  249. [带狼羊回该岸] = False
  250. Else
  251. If [对岸羊数] = 0 Or [对岸狼数] = 0 Then
  252. [带狼羊回该岸] = False
  253. Else
  254. [人的位置] = 1
  255. [该岸羊数] = [该岸羊数] + 1
  256. [对岸羊数] = [对岸羊数] - 1
  257. [该岸狼数] = [该岸狼数] + 1
  258. [对岸狼数] = [对岸狼数] - 1
  259. If [可行性分析] = False Then
  260. [带狼羊回该岸] = False
  261. Else
  262. [带狼羊回该岸] = True
  263. End If
  264. End If
  265. End If
  266. End Function
  267. End Class
复制代码
部分结果
方法1
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]

方法2
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[人回该岸]
[带2狼去对岸]

方法3
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[带1狼回该岸]
[带2狼去对岸]
[人回该岸]
[带1狼去对岸]

方法4
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带1狼去对岸]
[人回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带1羊去对岸]
[带1狼回该岸]
[带2狼去对岸]
[带1狼回该岸]
[带2狼去对岸]

...

方法260
[带2狼去对岸]
[带1狼回该岸]
[带狼羊去对岸]
[带1羊回该岸]
[带狼羊去对岸]
[带1羊回该岸]
[带2羊去对岸]
[带2狼回该岸]
[带狼羊去对岸]
[带2狼回该岸]
[带1狼去对岸]
[人回该岸]
[带2狼去对岸]

本帖最后由 老刘1号 于 2019-3-15 08:29 编辑

回复 2# xczxczxcz


    哈哈,这只是一种方法吧,欢迎编程求所有状态不和历史重复下的方法(260种)

TOP

本帖最后由 老刘1号 于 2019-3-19 14:34 编辑

回复 5# 523066680


    第二条学习了,
第一条,其实限制没有那么严,因为船舱中可以“常驻”生物(我研究我代码跑出的结果时偶然发现的
假设船舱容量8,狼、羊均17只,
可以如下操作:
  1. 拉8狼过,回 此时wolf=9,8
  2. 拉7狼过,回 此时wolf=2,15
  3. 拉8羊过,拉8狼回 此时wolf=10,7 sheep=9,8
  4. 船上放置2狼,每次载3狼3羊过去即可。
复制代码
其实也没必要太纠结这个问题本身,现实意义不大,
主要是练下回溯法,让程序深度优先遍历所有可能路径。
程序跑出来就有,跑不出就没有,不用动脑,岂不美哉。
1

评分人数

    • 523066680: 消化一下再评价,出乎意料的操作。技术 + 1

TOP

本帖最后由 老刘1号 于 2019-3-19 15:47 编辑

回复 7# 523066680


    哈哈,这个不穷举一下有时候人脑就是考虑不全,正常正常
刚看你的说法也觉得没有毛病,突然觉得有些不太对,就测试了一下

递归枚举这个一类题的套路都一样,只不过每个题要求“回溯”的条件不同,有的还需要判断历史状态
什么人狼羊菜过河,八皇后问题,3水桶分8升水问题,走迷宫问题不是都差不多嘛,基本属于一劳永逸型

TOP

本帖最后由 老刘1号 于 2019-3-19 16:21 编辑

回复 7# 523066680


    装载量的话,当狼、羊数=1的时候,>0即可,当狼、羊数=2,3,4的时候,>1即可,当狼、羊数=5,6的时候,>2即可,当狼、羊数>6的时候,>3即可

设狼、羊数目为n,装载量为4
可以
  1. 载4狼过,回
  2. 载3狼过,回
  3. 载4羊过,载4狼回
  4. 船上装2狼,每次运送1狼1羊
复制代码
题目的关键点在于让人不在的位置羊>狼
而准确说有3个位置,当岸、对岸,船
当岸和对岸,人有时候在,有时候不在,而船上人永远是在的
所以船可以无视题目条件,来做“周转”

其实可以假设题目条件为 n羊,n-2狼
这样只要先在对岸放1羊,两岸羊数就都比狼数大1,
每次移动1狼1羊,都不会触发狼吃羊条件。
而上面的结论是将2狼加回来,放在“船上”得到的

更直观的离子
  1. 载2狼1羊过,载2狼回
  2. 船上装2狼,每次运送1狼1羊
复制代码

TOP

返回列表