Board logo

标题: 不限语言解决“三狼三羊过河问题” [打印本页]
作者: 老刘1号    时间: 2019-3-14 12:22     标题: 不限语言解决“三狼三羊过河问题”

本帖最后由 老刘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. 

  7. 

  8. Sub recursion(ByRef obj,ByVal StatusLog,byVal StepLog)

  9. 	Dim nowStatus

  10. 	nowStatus = Join(obj.[当前情形],",")

  11. 	If nowStatus = "0,3,0,3,2" Then

  12. 		wsh.echo "方法"&[方法]&StepLog&vbNewLine

  13. 		[方法] = [方法] + 1

  14. 	Else

  15. 		For i = 0 To UBound(todo)

  16. 			If Eval("obj."&todo(i)) = True Then

  17. 				If InStr(StatusLog,Join(obj.[当前情形],",")) = 0 Then	'避免执行步骤恢复到以前状态，陷入死循环

  18. 					recursion obj,StatusLog & vbNewLine & Join(obj.[当前情形],","),StepLog & vbNewLine & todo(i)

  19. 				End If

  20. 			End If

  21. 			Execute "obj.[加载情形] " & nowStatus

  22. 		Next

  23. 	End If

  24. End Sub

  25. 

  26. Class [三狼三羊过河问题]

  27. 	Private [该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置]

  28. 	

  29. 	Private Sub Class_Initialize

  30. 		[该岸羊数] = 3

  31. 		[对岸羊数] = 0

  32. 		[该岸狼数] = 3

  33. 		[对岸狼数] = 0

  34. 		[人的位置] = 1	'表示该岸，2为对岸

  35. 	End Sub

  36. 	

  37. 	Public Sub [加载情形](a,b,c,d,e)

  38. 		[该岸羊数] = a

  39. 		[对岸羊数] = b

  40. 		[该岸狼数] = c

  41. 		[对岸狼数] = d

  42. 		[人的位置] = e

  43. 	End Sub

  44. 	

  45. 	Public Function [当前情形]

  46. 		[当前情形] = Array([该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置])

  47. 	End Function

  48. 	

  49. 	Private Function [可行性分析]

  50. 		If [人的位置] = 1 Then	'人在该岸

  51. 			If [对岸狼数] >= [对岸羊数] And [对岸羊数] >= 1 Then

  52. 				[可行性分析] = False	'对岸狼会吃羊

  53. 			Else

  54. 				[可行性分析] = True

  55. 			End If

  56. 		Else	'人在对岸

  57. 			If [该岸狼数] >= [该岸羊数] And [该岸羊数] >= 1 Then

  58. 				[可行性分析] = False	'该岸狼会吃羊

  59. 			Else

  60. 				[可行性分析] = True

  61. 			End If

  62. 		End If

  63. 	End Function

  64. 	

  65. 	Public Function [人去对岸]

  66. 		If [人的位置] = 2 Then

  67. 			[人去对岸] = False

  68. 		Else

  69. 			[人的位置] = 2

  70. 			If [可行性分析] = False Then

  71. 				[人的位置] = 1

  72. 				[人去对岸] = False	'操作不可行

  73. 			Else

  74. 				[人去对岸] = True	'操作可行

  75. 			End If

  76. 		End If

  77. 	End Function

  78. 	

  79. 	Public Function [人回该岸]

  80. 		If [人的位置] = 1 Then

  81. 			[人回该岸] = False

  82. 		Else

  83. 			[人的位置] = 1

  84. 			If [可行性分析] = False Then

  85. 				[人的位置] = 2

  86. 				[人回该岸] = False	'操作不可行

  87. 			Else

  88. 				[人回该岸] = True	'操作可行

  89. 			End If

  90. 		End If

  91. 	End Function

  92. 	

  93. 	Public Function [带1狼去对岸]

  94. 		If [人的位置] = 2 Then

  95. 			[带1狼去对岸] = False

  96. 		Else

  97. 			If [该岸狼数] = 0 Then	'该岸无狼

  98. 				[带1狼去对岸] = False

  99. 			Else

  100. 				[人的位置] = 2

  101. 				[该岸狼数] = [该岸狼数] - 1

  102. 				[对岸狼数] = [对岸狼数] + 1

  103. 				If [可行性分析] = False Then

  104. 					[带1狼去对岸] = False

  105. 				Else

  106. 					[带1狼去对岸] = True

  107. 				End If

  108. 			End If

  109. 		End If

  110. 	End Function

  111. 	

  112. 	Public Function [带2狼去对岸]

  113. 		If [人的位置] = 2 Then

  114. 			[带2狼去对岸] = False

  115. 		Else

  116. 			If [该岸狼数] <= 1 Then	'该岸狼不够

  117. 				[带2狼去对岸] = False

  118. 			Else

  119. 				[人的位置] = 2

  120. 				[该岸狼数] = [该岸狼数] - 2

  121. 				[对岸狼数] = [对岸狼数] + 2

  122. 				If [可行性分析] = False Then

  123. 					[带2狼去对岸] = False

  124. 				Else

  125. 					[带2狼去对岸] = True

  126. 				End If

  127. 			End If

  128. 		End If

  129. 	End Function

  130. 	

  131. 	Public Function [带1狼回该岸]

  132. 		If [人的位置] = 1 Then

  133. 			[带1狼回该岸] = False

  134. 		Else

  135. 			If [对岸狼数] = 0 Then	'对岸无狼

  136. 				[带1狼回该岸] = False

  137. 			Else

  138. 				[人的位置] = 1

  139. 				[该岸狼数] = [该岸狼数] + 1

  140. 				[对岸狼数] = [对岸狼数] - 1

  141. 				If [可行性分析] = False Then

  142. 					[带1狼回该岸] = False

  143. 				Else

  144. 					[带1狼回该岸] = True

  145. 				End If

  146. 			End If

  147. 		End If

  148. 		

  149. 	End Function

  150. 	

  151. 	Public Function [带2狼回该岸]

  152. 		If [人的位置] = 1 Then

  153. 			[带2狼回该岸] = False

  154. 		Else

  155. 			If [对岸狼数] <= 1 Then	'对岸狼不够

  156. 				[带2狼回该岸] = False

  157. 			Else

  158. 				[人的位置] = 1

  159. 				[该岸狼数] = [该岸狼数] + 2

  160. 				[对岸狼数] = [对岸狼数] - 2

  161. 				If [可行性分析] = False Then

  162. 					[带2狼回该岸] = False

  163. 				Else

  164. 					[带2狼回该岸] = True

  165. 				End If

  166. 			End If

  167. 		End If

  168. 	End Function

  169. 	

  170. 	Public Function [带1羊去对岸]

  171. 		If [人的位置] = 2 Then

  172. 			[带1羊去对岸] = False

  173. 		Else

  174. 			If [该岸羊数] = 0 Then	'该岸无羊

  175. 				[带1羊去对岸] = False

  176. 			Else

  177. 				[人的位置] = 2

  178. 				[该岸羊数] = [该岸羊数] - 1

  179. 				[对岸羊数] = [对岸羊数] + 1

  180. 				If [可行性分析] = False Then

  181. 					[带1羊去对岸] = False

  182. 				Else

  183. 					[带1羊去对岸] = True

  184. 				End If

  185. 			End If

  186. 		End If

  187. 	End Function

  188. 	

  189. 	Public Function [带2羊去对岸]

  190. 		If [人的位置] = 2 Then

  191. 			[带2羊去对岸] = False

  192. 		Else

  193. 			If [该岸羊数] <= 1 Then	'该岸羊不够

  194. 				[带2羊去对岸] = False

  195. 			Else

  196. 				[人的位置] = 2

  197. 				[该岸羊数] = [该岸羊数] - 2

  198. 				[对岸羊数] = [对岸羊数] + 2

  199. 				If [可行性分析] = False Then

  200. 					[带2羊去对岸] = False

  201. 				Else

  202. 					[带2羊去对岸] = True

  203. 				End If

  204. 			End If

  205. 		End If

  206. 	End Function

  207. 	

  208. 	Public Function [带1羊回该岸]

  209. 		If [人的位置] = 1 Then

  210. 			[带1羊回该岸] = False

  211. 		Else

  212. 			If [对岸羊数] = 0 Then	'对岸无羊

  213. 				[带1羊回该岸] = False

  214. 			Else

  215. 				[人的位置] = 1

  216. 				[该岸羊数] = [该岸羊数] + 1

  217. 				[对岸羊数] = [对岸羊数] - 1

  218. 				If [可行性分析] = False Then

  219. 					[带1羊回该岸] = False

  220. 				Else

  221. 					[带1羊回该岸] = True

  222. 				End If

  223. 			End If

  224. 		End If

  225. 	End Function

  226. 	

  227. 	Public Function [带2羊回该岸]

  228. 		If [人的位置] = 1 Then

  229. 			[带2羊回该岸] = False

  230. 		Else

  231. 			If [对岸羊数] <= 1 Then	'对岸羊不够

  232. 				[带2羊回该岸] = False

  233. 			Else

  234. 				[人的位置] = 1

  235. 				[该岸羊数] = [该岸羊数] + 2

  236. 				[对岸羊数] = [对岸羊数] - 2

  237. 				If [可行性分析] = False Then

  238. 					[带2羊回该岸] = False

  239. 				Else

  240. 					[带2羊回该岸] = True

  241. 				End If

  242. 			End If

  243. 		End If

  244. 	End Function

  245. 	

  246. 	Public Function [带狼羊去对岸]

  247. 		If [人的位置] = 2 Then

  248. 			[带狼羊去对岸] = False

  249. 		Else

  250. 			If [该岸羊数] = 0 Or [该岸狼数] = 0 Then

  251. 				[带狼羊去对岸] = False

  252. 			Else

  253. 				[人的位置] = 2

  254. 				[该岸羊数] = [该岸羊数] - 1

  255. 				[对岸羊数] = [对岸羊数] + 1

  256. 				[该岸狼数] = [该岸狼数] - 1

  257. 				[对岸狼数] = [对岸狼数] + 1

  258. 				If [可行性分析] = False Then

  259. 					[带狼羊去对岸] = False

  260. 				Else

  261. 					[带狼羊去对岸] = True

  262. 				End If

  263. 			End If

  264. 		End If

  265. 	End Function

  266. 	

  267. 	Public Function [带狼羊回该岸]

  268. 		If [人的位置] = 1 Then

  269. 			[带狼羊回该岸] = False

  270. 		Else

  271. 			If [对岸羊数] = 0 Or [对岸狼数] = 0 Then

  272. 				[带狼羊回该岸] = False

  273. 			Else

  274. 				[人的位置] = 1

  275. 				[该岸羊数] = [该岸羊数] + 1

  276. 				[对岸羊数] = [对岸羊数] - 1

  277. 				[该岸狼数] = [该岸狼数] + 1

  278. 				[对岸狼数] = [对岸狼数] - 1

  279. 				If [可行性分析] = False Then

  280. 					[带狼羊回该岸] = False

  281. 				Else

  282. 					[带狼羊回该岸] = True

  283. 				End If

  284. 			End If

  285. 		End If

  286. 	End Function

  287. 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狼去对岸]
作者: xczxczxcz    时间: 2019-3-14 18:58

口算：
1；人+2狼 过河。2；人返回。3；人+1羊过河。4；人+2狼返回。5；人+2羊过河。6；人返回。7；人+2狼过河。8；人返回。9；人+1狠过河。
作者: 老刘1号    时间: 2019-3-15 08:10

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

回复 2# xczxczxcz


    哈哈，这只是一种方法吧，欢迎编程求所有状态不和历史重复下的方法（260种）
作者: 523066680    时间: 2019-3-18 21:38

本帖最后由 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. 

  11. my @arr = (1,3,3);

  12. my @brr = (0,0,0);

  13. my $space = 2;  # 船的空位，不包括人

  14. my @op;

  15. 

  16. main([@arr], [@brr], 0, join(",", @brr), \@op);

  17. 

  18. sub main

  19. {

  20.     my ($a, $b, $lv, $bhistory, $op ) = @_;

  21. 

  22.     my $h = 1;

  23.     my ( $w_min, $w_max, $s_min, $s_max );

  24.     my $rest;

  25. 

  26.     if ( $lv % 2 == 0) {

  27.         $w_min = 0;

  28.         $w_max = $a->[1] > $space ? $space : $a->[1];

  29.         for my $w ( $w_min .. $w_max )

  30.         {

  31.             $rest = $space - $w;

  32.             $s_min = $w == 0 ? 1 : 0;  # 确保不会空船渡河

  33.             $s_max = $a->[2] > $rest ? $rest : $a->[2];

  34.             for my $s ( $s_min .. $s_max )

  35.             {

  36.                 push @op, [$h, $w, $s];

  37.                 cross( $a, $b, $h, $w, $s, $lv, $bhistory, $op );

  38.                 pop @op;

  39.             }

  40.         }

  41.     } else {

  42.         $s = 0; # 羊：回去是不可能回去的，只有在对岸才能够生活这样子。

  43.         $w_min = 0;

  44.         $w_max = $b->[2] > $b->[1] ? 0 : 

  45.                  $b->[2] > $space ? $space : $b->[2] ; # 如果对岸 羊>狼 则狼不必返回

  46.         for my $w ( $w_min .. $w_max )

  47.         {

  48.             push @op, [$h, $w, $s];

  49.             cross( $b, $a, $h, $w, $s, $lv, $bhistory, $op );

  50.             pop @op;

  51.         }

  52.     }

  53. }

  54. 

  55. sub cross

  56. {

  57.     my ($a, $b, $h, $w, $s, $lv, $bhistory, $op) = @_;

  58. 

  59.     cross_river($a, $b, [$h,$w,$s]);

  60.     my $chk = $lv % 2 == 0 ? check($a, $b) : check($b, $a);

  61.     # 过河后的状态

  62.     my $curr_a = join(",", @$a);

  63.     my $curr_b = join(",", @$b);

  64.     if ($chk == 1) {

  65.         if ( $lv % 2 == 0 ) {

  66.             unless ( $bhistory =~/$curr_b/ ) {

  67.                 main($a, $b, $lv+1, $bhistory ." ".$curr_b, $op );

  68.             }

  69.         } else { 

  70.             unless ( $bhistory =~/$curr_a/ ) {

  71.                 main($b, $a, $lv+1, $bhistory ." ".$curr_a, $op );

  72.             }

  73.         }

  74.     }

  75. 

  76.     if ($chk == 2) {

  77.         my $ta = [@arr];

  78.         my $tb = [@brr];

  79.         for my $id ( 0 .. $#$op ) {

  80.             if ( $id % 2 == 0 ) {

  81.                 cross_river( $ta, $tb, $op->[$id] );

  82.                 printf "[%2d]   Go %d,%d,%d ", $id+1, @{$op->[$id]};

  83.             } else {

  84.                 cross_river( $tb, $ta, $op->[$id] );

  85.                 printf "[%2d] Back %d,%d,%d ", $id+1, @{$op->[$id]};

  86.             }

  87.             printf "A [%d %d %d], B [%d %d %d]\n", @$ta, @$tb;

  88.         }

  89.         printf "\n";

  90.     }

  91. 

  92.     cross_river( $b, $a, [$h,$w,$s] ); # 恢复

  93. }

  94. 

  95. sub cross_river {

  96.     my ($a,$b,$c) = @_;

  97.     grep { $a->[$_]-=$c->[$_],

  98.            $b->[$_]+=$c->[$_]; } (0,1,2);

  99. }

  100. 

  101. sub check {

  102.     my ($a, $b, $lv) = @_;

  103.     return 0 if ( $a->[1] >= $a->[2] and $a->[2] > 0 and $a->[0] == 0 );

  104.     return 0 if ( $b->[1] >= $b->[2] and $b->[2] > 0 and $b->[0] == 0 );

  105.     return 2 if ( $a->[1] == 0 and $a->[2] == 0 );

  106.     return 1;

  107. }
复制代码
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. 

  11. [ 1]   Go 1,1,0 A [0 2 3], B [1 1 0]

  12. [ 2] Back 1,0,0 A [1 2 3], B [0 1 0]

  13. [ 3]   Go 1,2,0 A [0 0 3], B [1 3 0]

  14. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]

  15. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]

  16. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]

  17. [ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]

  18. [ 8] Back 1,0,0 A [1 1 0], B [0 2 3]

  19. [ 9]   Go 1,1,0 A [0 0 0], B [1 3 3]

  20. 

  21. [ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]

  22. [ 2] Back 1,0,0 A [1 1 3], B [0 2 0]

  23. [ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]

  24. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]

  25. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]

  26. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]

  27. [ 7]   Go 1,0,1 A [0 2 0], B [1 1 3]

  28. [ 8] Back 1,0,0 A [1 2 0], B [0 1 3]

  29. [ 9]   Go 1,2,0 A [0 0 0], B [1 3 3]

  30. 

  31. [ 1]   Go 1,2,0 A [0 1 3], B [1 2 0]

  32. [ 2] Back 1,0,0 A [1 1 3], B [0 2 0]

  33. [ 3]   Go 1,1,0 A [0 0 3], B [1 3 0]

  34. [ 4] Back 1,0,0 A [1 0 3], B [0 3 0]

  35. [ 5]   Go 1,0,2 A [0 0 1], B [1 3 2]

  36. [ 6] Back 1,2,0 A [1 2 1], B [0 1 2]

  37. [ 7]   Go 1,1,1 A [0 1 0], B [1 2 3]

  38. [ 8] Back 1,0,0 A [1 1 0], B [0 2 3]

  39. [ 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]
复制代码
作者: 523066680    时间: 2019-3-18 21:56

本帖最后由 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号    时间: 2019-3-19 14:22

本帖最后由 老刘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羊过去即可。
复制代码
其实也没必要太纠结这个问题本身，现实意义不大，
主要是练下回溯法，让程序深度优先遍历所有可能路径。
程序跑出来就有，跑不出就没有，不用动脑，岂不美哉。
作者: 523066680    时间: 2019-3-19 15:06

本帖最后由 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]
复制代码
作者: 老刘1号    时间: 2019-3-19 15:44

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

回复 7# 523066680


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

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

本帖最后由 老刘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羊
复制代码
作者: 523066680    时间: 2019-3-19 16:26

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

回复 9# 老刘1号

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

这个时候，船在往返时始终载2只狼，（这两只狼的隔离使得两岸刚好满足 羊>狼 的情况）
然后根据船剩下的空间，携带等同数量（剩余空间/2，这样不会破坏平衡）的羊狼过岸。



欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2