• 【中国梦·大国工匠篇】鸡蛋上钻孔显真功 潜心坚守一线练就绝活儿 2019-06-11
  • 【理上网来·喜迎十九大】塞尔维亚驻华大使:中国的发展是其他国家望尘莫及的 2019-06-10
  • 六大工程培育发展新动能 2019-06-10
  • 为推动上合组织发展提供中国智慧、中国方案 2019-05-29
  • 覆盖31亿人口!一图告诉你上合组织有多牛 2019-05-28
  • 德味手表了解一下 徕卡推出L1,L2机械表德味手表徕卡推出L1-手机行情 2019-05-28
  • 西部网(陕西新闻网)www.cnwest.com 2019-05-27
  • 穿越千年 感悟周公 2019-05-27
  • 2017年度一级建造师考试成绩已发布 2019-05-27
  • 【大考2018】2018高考首日众生相(组图) 2019-05-27
  • 浙江舟山定海区一国企非党管理人员涉嫌受贿被查 2019-05-23
  • 让山里娃感受智慧科技乐趣 2019-05-19
  • 香港田径锦标赛飞人夺冠 2019-05-19
  • 诽谤侮辱英烈可追刑责 2019-05-14
  • 图解:十二字“洞见”2017年保险业 2019-04-28
  • 批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程
    [批处理文件精品]批处理版照片整理器[批处理文件精品]纯批处理备份&还原驱动在线第三方下载
    返回列表 发帖

    广东十一选五人工计划:不限语言解决“三狼三羊过河问题”

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

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

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

    vbs版(无效率可言,仅为粗略实现)
     广东十一选五计划软件 www.qe-ar.com 
    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;人+2狼 过河。2;人返回。3;人+1羊过河。4;人+2狼返回。5;人+2羊过河。6;人返回。7;人+2狼过河。8;人返回。9;人+1狠过河。

    TOP

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

    回复 2# xczxczxcz


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

    TOP

    本帖最后由 523066680 于 2019-3-18 21:51 编辑

    写了,没有经常做题脑子又钝写这些很不划算,本来这些时间打算学学 MilkyTracker 和音频处理的。
    1. =info
    2.     Farmer across river problem
    3.     523066680/vicyang
    4.     2019-03
    5.     0. 过对岸时,狼+羊至少要有1个(不做无用功)
    6.     1. 返程不应该载羊,因为把羊送过去是首要任务。
    7.     2. 对岸羊 > 狼 时,不需要返回狼。
    8.     3. 对岸数量的历史记录不应该重复(可以消除冗余的过程和结果)。
    9. =cut
    10. my @arr = (1,3,3);
    11. my @brr = (0,0,0);
    12. my $space = 2;  # 船的空位,不包括人
    13. my @op;
    14. main([@arr], [@brr], 0, join(",", @brr), \@op);
    15. sub main
    16. {
    17.     my ($a, $b, $lv, $bhistory, $op ) = @_;
    18.     my $h = 1;
    19.     my ( $w_min, $w_max, $s_min, $s_max );
    20.     my $rest;
    21.     if ( $lv % 2 == 0) {
    22.         $w_min = 0;
    23.         $w_max = $a->[1] > $space ? $space : $a->[1];
    24.         for my $w ( $w_min .. $w_max )
    25.         {
    26.             $rest = $space - $w;
    27.             $s_min = $w == 0 ? 1 : 0;  # 确保不会空船渡河
    28.             $s_max = $a->[2] > $rest ? $rest : $a->[2];
    29.             for my $s ( $s_min .. $s_max )
    30.             {
    31.                 push @op, [$h, $w, $s];
    32.                 cross( $a, $b, $h, $w, $s, $lv, $bhistory, $op );
    33.                 pop @op;
    34.             }
    35.         }
    36.     } else {
    37.         $s = 0; # 羊:回去是不可能回去的,只有在对岸才能够生活这样子。
    38.         $w_min = 0;
    39.         $w_max = $b->[2] > $b->[1] ? 0 :
    40.                  $b->[2] > $space ? $space : $b->[2] ; # 如果对岸 羊>狼 则狼不必返回
    41.         for my $w ( $w_min .. $w_max )
    42.         {
    43.             push @op, [$h, $w, $s];
    44.             cross( $b, $a, $h, $w, $s, $lv, $bhistory, $op );
    45.             pop @op;
    46.         }
    47.     }
    48. }
    49. sub cross
    50. {
    51.     my ($a, $b, $h, $w, $s, $lv, $bhistory, $op) = @_;
    52.     cross_river($a, $b, [$h,$w,$s]);
    53.     my $chk = $lv % 2 == 0 ? check($a, $b) : check($b, $a);
    54.     # 过河后的状态
    55.     my $curr_a = join(",", @$a);
    56.     my $curr_b = join(",", @$b);
    57.     if ($chk == 1) {
    58.         if ( $lv % 2 == 0 ) {
    59.             unless ( $bhistory =~/$curr_b/ ) {
    60.                 main($a, $b, $lv+1, $bhistory ." ".$curr_b, $op );
    61.             }
    62.         } else {
    63.             unless ( $bhistory =~/$curr_a/ ) {
    64.                 main($b, $a, $lv+1, $bhistory ." ".$curr_a, $op );
    65.             }
    66.         }
    67.     }
    68.     if ($chk == 2) {
    69.         my $ta = [@arr];
    70.         my $tb = [@brr];
    71.         for my $id ( 0 .. $#$op ) {
    72.             if ( $id % 2 == 0 ) {
    73.                 cross_river( $ta, $tb, $op->[$id] );
    74.                 printf "[%2d]   Go %d,%d,%d ", $id+1, @{$op->[$id]};
    75.             } else {
    76.                 cross_river( $tb, $ta, $op->[$id] );
    77.                 printf "[%2d] Back %d,%d,%d ", $id+1, @{$op->[$id]};
    78.             }
    79.             printf "A [%d %d %d], B [%d %d %d]\n", @$ta, @$tb;
    80.         }
    81.         printf "\n";
    82.     }
    83.     cross_river( $b, $a, [$h,$w,$s] ); # 恢复
    84. }
    85. sub cross_river {
    86.     my ($a,$b,$c) = @_;
    87.     grep { $a->[$_]-=$c->[$_],
    88.            $b->[$_]+=$c->[$_]; } (0,1,2);
    89. }
    90. sub check {
    91.     my ($a, $b, $lv) = @_;
    92.     return 0 if ( $a->[1] >= $a->[2] and $a->[2] > 0 and $a->[0] == 0 );
    93.     return 0 if ( $b->[1] >= $b->[2] and $b->[2] > 0 and $b->[0] == 0 );
    94.     return 2 if ( $a->[1] == 0 and $a->[2] == 0 );
    95.     return 1;
    96. }
    复制代码
    33种结果。
    往返累计次数少于10的结果有:
    1. [ 1]   Go 1,1,0 A [0 2 3], B [1 1 0]
    2. [ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
    3. [ 3]   Go 1,2,0 A [0 0 3], B [1 3 0]
    4. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
    5. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
    6. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
    7. [ 7]   Go 1,0,1 A [0 2 0], B [1 1 3]
    8. [ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
    9. [ 9]   Go 1,2,0 A [0 0 0], B [1 3 3]
    10. [ 1]   Go 1,1,0 A [0 2 3], B [1 1 0]
    11. [ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
    12. [ 3]   Go 1,2,0 A [0 0 3], B [1 3 0]
    13. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
    14. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
    15. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
    16. [ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]
    17. [ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
    18. [ 9]   Go 1,1,0 A [0 0 0], B [1 3 3]
    19. [ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]
    20. [ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
    21. [ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]
    22. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
    23. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
    24. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
    25. [ 7]   Go 1,0,1 A [0 2 0], B [1 1 3]
    26. [ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
    27. [ 9]   Go 1,2,0 A [0 0 0], B [1 3 3]
    28. [ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]
    29. [ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
    30. [ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]
    31. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
    32. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]
    33. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
    34. [ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]
    35. [ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
    36. [ 9]   Go 1,1,0 A [0 0 0], B [1 3 3]
    复制代码
    其他可以跑完的测试数据
    (1,4,4) 船载空间为2(除人以外)
    (1,5,5) 船载空间为3(除人以外)
    (1,6,6) 船载空间为3(除人以外)
    (1,7,7) 船载空间为4(除人以外)
    (1,8,8) 船载空间为4(除人以外)
    ....

    (1,7,7) 船空间为4 的其中一个结果:
    1. [ 1]   Go 1,4,0 A [0 3 7], B [1 4 0]
    2. [ 2] Back 1,0,0 A [1 3 7], B [0 4 0]
    3. [ 3]   Go 1,3,0 A [0 0 7], B [1 7 0]
    4. [ 4] Back 1,0,0 A [1 0 7], B [0 7 0]
    5. [ 5]   Go 1,0,4 A [0 0 3], B [1 7 4]
    6. [ 6] Back 1,4,0 A [1 4 3], B [0 3 4]
    7. [ 7]   Go 1,1,3 A [0 3 0], B [1 4 7]
    8. [ 8] Back 1,0,0 A [1 3 0], B [0 4 7]
    9. [ 9]   Go 1,3,0 A [0 0 0], B [1 7 7]
    复制代码
    1

    评分人数

    综合型编程论坛
    Writing Code That Nobody Else Can Read.

    TOP

    本帖最后由 523066680 于 2019-3-18 22:53 编辑

    1. 船空间(除人以外)的规律:至少应该是 floor[(羊/狼 最大数量+1)/2]
    2. 就目前的情况来看,若按第一条规律设置船的数量,则最短往返次数的规律为:(羊/狼 最大数量)为奇数时,最短步骤为9;为偶数时,最短步骤为11
    最简步骤的操作过程是类似的(感觉这种数值的增减操作和平分水问题相似)。

    举个栗子,拿前面1,7,7的方案套用到 1,17,17 船载容量为9 的情况:
    1.     [ 1]   Go 1,9,0 A [0 8 17], B [1 9 0]
    2.     [ 2] Back 1,0,0 A [1 8 17], B [0 9 0]
    3.     [ 3]   Go 1,8,0 A [0 0 17], B [1 17 0]
    4.     [ 4] Back 1,0,0 A [1 0 17], B [0 17 0]
    5.     [ 5]   Go 1,0,9 A [0 0 8], B [1 17 9]
    6.     [ 6] Back 1,9,0 A [1 9 8], B [0 8 9]
    7.     [ 7]   Go 1,1,8 A [0 8 0], B [1 9 17]
    8.     [ 8] Back 1,0,0 A [1 8 0], B [0 9 17]
    9.     [ 9]   Go 1,8,0 A [0 0 0], B [1 17 17]
    复制代码
    1

    评分人数

    综合型编程论坛
    Writing Code That Nobody Else Can Read.

    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

    本帖最后由 523066680 于 2019-3-19 16:15 编辑

    回复 6# 老刘1号

    我测试的样本还是少了,过早做出判断,那个最少装载量的“规律”还需重新考虑。
    根据1,17,17的例子,退一步发现 1,9,9 装载量也可以是 4,而不是5

    对我来说就算写递归枚举也很用脑,并不是不用动脑的情况。

    ----补充
    也发现用这种往返方式,船载量只要达到4,狼/羊数再往上递增都可以处理,变化的只是往返的次数
    最少往返次数的规律 (狼 or 羊 个数 * 2)-5
    1. [ 1]   Go 1,4,0 A [0 13 17], B [1 4 0]
    2. [ 2] Back 1,0,0 A [1 13 17], B [0 4 0]
    3. [ 3]   Go 1,3,0 A [0 10 17], B [1 7 0]
    4. [ 4] Back 1,0,0 A [1 10 17], B [0 7 0]
    5. [ 5]   Go 1,0,4 A [0 10 13], B [1 7 4]
    6. [ 6] Back 1,4,0 A [1 14 13], B [0 3 4]
    7. [ 7]   Go 1,3,1 A [0 11 12], B [1 6 5]
    8. [ 8] Back 1,2,0 A [1 13 12], B [0 4 5]
    9. [ 9]   Go 1,3,1 A [0 10 11], B [1 7 6]
    10. [10] Back 1,2,0 A [1 12 11], B [0 5 6]
    11. [11]   Go 1,3,1 A [0 9 10], B [1 8 7]
    12. [12] Back 1,2,0 A [1 11 10], B [0 6 7]
    13. [13]   Go 1,3,1 A [0 8 9], B [1 9 8]
    14. [14] Back 1,2,0 A [1 10 9], B [0 7 8]
    15. [15]   Go 1,3,1 A [0 7 8], B [1 10 9]
    16. [16] Back 1,2,0 A [1 9 8], B [0 8 9]
    17. [17]   Go 1,3,1 A [0 6 7], B [1 11 10]
    18. [18] Back 1,2,0 A [1 8 7], B [0 9 10]
    19. [19]   Go 1,3,1 A [0 5 6], B [1 12 11]
    20. [20] Back 1,2,0 A [1 7 6], B [0 10 11]
    21. [21]   Go 1,3,1 A [0 4 5], B [1 13 12]
    22. [22] Back 1,2,0 A [1 6 5], B [0 11 12]
    23. [23]   Go 1,3,1 A [0 3 4], B [1 14 13]
    24. [24] Back 1,2,0 A [1 5 4], B [0 12 13]
    25. [25]   Go 1,3,1 A [0 2 3], B [1 15 14]
    26. [26] Back 1,2,0 A [1 4 3], B [0 13 14]
    27. [27]   Go 1,1,3 A [0 3 0], B [1 14 17]
    28. [28] Back 1,0,0 A [1 3 0], B [0 14 17]
    29. [29]   Go 1,3,0 A [0 0 0], B [1 17 17]
    复制代码
    综合型编程论坛
    Writing Code That Nobody Else Can Read.

    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

    本帖最后由 523066680 于 2019-3-19 17:08 编辑

    回复 9# 老刘1号

        明白的了,关键节点就是创造两岸狼羊都只差1的情况:
    左岸 狼 = n, 羊 = n+1;右岸 狼 = m, 羊 = m-1;人、船位于有危险的一边

    这个时候,船在往返时始终载2只狼,(这两只狼的隔离使得两岸刚好满足 羊>狼 的情况)
    然后根据船剩下的空间,携带等同数量(剩余空间/2,这样不会破坏平衡)的羊狼过岸。
    综合型编程论坛
    Writing Code That Nobody Else Can Read.

    TOP

    返回列表
  • 【中国梦·大国工匠篇】鸡蛋上钻孔显真功 潜心坚守一线练就绝活儿 2019-06-11
  • 【理上网来·喜迎十九大】塞尔维亚驻华大使:中国的发展是其他国家望尘莫及的 2019-06-10
  • 六大工程培育发展新动能 2019-06-10
  • 为推动上合组织发展提供中国智慧、中国方案 2019-05-29
  • 覆盖31亿人口!一图告诉你上合组织有多牛 2019-05-28
  • 德味手表了解一下 徕卡推出L1,L2机械表德味手表徕卡推出L1-手机行情 2019-05-28
  • 西部网(陕西新闻网)www.cnwest.com 2019-05-27
  • 穿越千年 感悟周公 2019-05-27
  • 2017年度一级建造师考试成绩已发布 2019-05-27
  • 【大考2018】2018高考首日众生相(组图) 2019-05-27
  • 浙江舟山定海区一国企非党管理人员涉嫌受贿被查 2019-05-23
  • 让山里娃感受智慧科技乐趣 2019-05-19
  • 香港田径锦标赛飞人夺冠 2019-05-19
  • 诽谤侮辱英烈可追刑责 2019-05-14
  • 图解:十二字“洞见”2017年保险业 2019-04-28