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

老刘1号 · 发表于 2019-3-14 12:22:03

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

某算法课程中看到的一个题，

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

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

vbs版（无效率可言，仅为粗略实现）

Rem Code By 老刘
todo=Array("[人去对岸]","[人回该岸]","[带1狼去对岸]","[带2狼去对岸]","[带1狼回该岸]","[带2狼回该岸]","[带1羊去对岸]","[带2羊去对岸]","[带1羊回该岸]","[带2羊回该岸]","[带狼羊去对岸]","[带狼羊回该岸]")
Dim [方法]
[方法] = 1
recursion New [三狼三羊过河问题],"3,0,3,0,1",""
Sub recursion(ByRef obj,ByVal StatusLog,byVal StepLog)
Dim nowStatus
nowStatus = Join(obj.[当前情形],",")
If nowStatus = "0,3,0,3,2" Then
wsh.echo "方法"&[方法]&StepLog&vbNewLine
[方法] = [方法] + 1
Else
For i = 0 To UBound(todo)
If Eval("obj."&todo(i)) = True Then
If InStr(StatusLog,Join(obj.[当前情形],",")) = 0 Then '避免执行步骤恢复到以前状态，陷入死循环
recursion obj,StatusLog & vbNewLine & Join(obj.[当前情形],","),StepLog & vbNewLine & todo(i)
End If
End If
Execute "obj.[加载情形] " & nowStatus
Next
End If
End Sub
Class [三狼三羊过河问题]
Private [该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置]
Private Sub Class_Initialize
[该岸羊数] = 3
[对岸羊数] = 0
[该岸狼数] = 3
[对岸狼数] = 0
[人的位置] = 1 '表示该岸，2为对岸
End Sub
Public Sub [加载情形](a,b,c,d,e)
[该岸羊数] = a
[对岸羊数] = b
[该岸狼数] = c
[对岸狼数] = d
[人的位置] = e
End Sub
Public Function [当前情形]
[当前情形] = Array([该岸羊数],[对岸羊数],[该岸狼数],[对岸狼数],[人的位置])
End Function
Private Function [可行性分析]
If [人的位置] = 1 Then '人在该岸
If [对岸狼数] >= [对岸羊数] And [对岸羊数] >= 1 Then
[可行性分析] = False '对岸狼会吃羊
Else
[可行性分析] = True
End If
Else '人在对岸
If [该岸狼数] >= [该岸羊数] And [该岸羊数] >= 1 Then
[可行性分析] = False '该岸狼会吃羊
Else
[可行性分析] = True
End If
End If
End Function
Public Function [人去对岸]
If [人的位置] = 2 Then
[人去对岸] = False
Else
[人的位置] = 2
If [可行性分析] = False Then
[人的位置] = 1
[人去对岸] = False '操作不可行
Else
[人去对岸] = True '操作可行
End If
End If
End Function
Public Function [人回该岸]
If [人的位置] = 1 Then
[人回该岸] = False
Else
[人的位置] = 1
If [可行性分析] = False Then
[人的位置] = 2
[人回该岸] = False '操作不可行
Else
[人回该岸] = True '操作可行
End If
End If
End Function
Public Function [带1狼去对岸]
If [人的位置] = 2 Then
[带1狼去对岸] = False
Else
If [该岸狼数] = 0 Then '该岸无狼
[带1狼去对岸] = False
Else
[人的位置] = 2
[该岸狼数] = [该岸狼数] - 1
[对岸狼数] = [对岸狼数] + 1
If [可行性分析] = False Then
[带1狼去对岸] = False
Else
[带1狼去对岸] = True
End If
End If
End If
End Function
Public Function [带2狼去对岸]
If [人的位置] = 2 Then
[带2狼去对岸] = False
Else
If [该岸狼数] <= 1 Then '该岸狼不够
[带2狼去对岸] = False
Else
[人的位置] = 2
[该岸狼数] = [该岸狼数] - 2
[对岸狼数] = [对岸狼数] + 2
If [可行性分析] = False Then
[带2狼去对岸] = False
Else
[带2狼去对岸] = True
End If
End If
End If
End Function
Public Function [带1狼回该岸]
If [人的位置] = 1 Then
[带1狼回该岸] = False
Else
If [对岸狼数] = 0 Then '对岸无狼
[带1狼回该岸] = False
Else
[人的位置] = 1
[该岸狼数] = [该岸狼数] + 1
[对岸狼数] = [对岸狼数] - 1
If [可行性分析] = False Then
[带1狼回该岸] = False
Else
[带1狼回该岸] = True
End If
End If
End If
End Function
Public Function [带2狼回该岸]
If [人的位置] = 1 Then
[带2狼回该岸] = False
Else
If [对岸狼数] <= 1 Then '对岸狼不够
[带2狼回该岸] = False
Else
[人的位置] = 1
[该岸狼数] = [该岸狼数] + 2
[对岸狼数] = [对岸狼数] - 2
If [可行性分析] = False Then
[带2狼回该岸] = False
Else
[带2狼回该岸] = True
End If
End If
End If
End Function
Public Function [带1羊去对岸]
If [人的位置] = 2 Then
[带1羊去对岸] = False
Else
If [该岸羊数] = 0 Then '该岸无羊
[带1羊去对岸] = False
Else
[人的位置] = 2
[该岸羊数] = [该岸羊数] - 1
[对岸羊数] = [对岸羊数] + 1
If [可行性分析] = False Then
[带1羊去对岸] = False
Else
[带1羊去对岸] = True
End If
End If
End If
End Function
Public Function [带2羊去对岸]
If [人的位置] = 2 Then
[带2羊去对岸] = False
Else
If [该岸羊数] <= 1 Then '该岸羊不够
[带2羊去对岸] = False
Else
[人的位置] = 2
[该岸羊数] = [该岸羊数] - 2
[对岸羊数] = [对岸羊数] + 2
If [可行性分析] = False Then
[带2羊去对岸] = False
Else
[带2羊去对岸] = True
End If
End If
End If
End Function
Public Function [带1羊回该岸]
If [人的位置] = 1 Then
[带1羊回该岸] = False
Else
If [对岸羊数] = 0 Then '对岸无羊
[带1羊回该岸] = False
Else
[人的位置] = 1
[该岸羊数] = [该岸羊数] + 1
[对岸羊数] = [对岸羊数] - 1
If [可行性分析] = False Then
[带1羊回该岸] = False
Else
[带1羊回该岸] = True
End If
End If
End If
End Function
Public Function [带2羊回该岸]
If [人的位置] = 1 Then
[带2羊回该岸] = False
Else
If [对岸羊数] <= 1 Then '对岸羊不够
[带2羊回该岸] = False
Else
[人的位置] = 1
[该岸羊数] = [该岸羊数] + 2
[对岸羊数] = [对岸羊数] - 2
If [可行性分析] = False Then
[带2羊回该岸] = False
Else
[带2羊回该岸] = True
End If
End If
End If
End Function
Public Function [带狼羊去对岸]
If [人的位置] = 2 Then
[带狼羊去对岸] = False
Else
If [该岸羊数] = 0 Or [该岸狼数] = 0 Then
[带狼羊去对岸] = False
Else
[人的位置] = 2
[该岸羊数] = [该岸羊数] - 1
[对岸羊数] = [对岸羊数] + 1
[该岸狼数] = [该岸狼数] - 1
[对岸狼数] = [对岸狼数] + 1
If [可行性分析] = False Then
[带狼羊去对岸] = False
Else
[带狼羊去对岸] = True
End If
End If
End If
End Function
Public Function [带狼羊回该岸]
If [人的位置] = 1 Then
[带狼羊回该岸] = False
Else
If [对岸羊数] = 0 Or [对岸狼数] = 0 Then
[带狼羊回该岸] = False
Else
[人的位置] = 1
[该岸羊数] = [该岸羊数] + 1
[对岸羊数] = [对岸羊数] - 1
[该岸狼数] = [该岸狼数] + 1
[对岸狼数] = [对岸狼数] - 1
If [可行性分析] = False Then
[带狼羊回该岸] = False
Else
[带狼羊回该岸] = True
End If
End If
End If
End Function
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:00

口算：
1；人+2狼过河。2；人返回。3；人+1羊过河。4；人+2狼返回。5；人+2羊过河。6；人返回。7；人+2狼过河。8；人返回。9；人+1狠过河。

老刘1号 · 发表于 2019-3-15 08:10:04

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

回复 2# xczxczxcz

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

523066680 · 发表于 2019-3-18 21:38:30

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

写了，没有经常做题脑子又钝写这些很不划算，本来这些时间打算学学 MilkyTracker 和音频处理的。

=info
Farmer across river problem
523066680/vicyang
2019-03
0. 过对岸时，狼+羊至少要有1个（不做无用功）
1. 返程不应该载羊，因为把羊送过去是首要任务。
2. 对岸羊 > 狼时，不需要返回狼。
3. 对岸数量的历史记录不应该重复（可以消除冗余的过程和结果）。
=cut
my @arr = (1,3,3);
my @brr = (0,0,0);
my $space = 2; # 船的空位，不包括人
my @op;
main([@arr], [@brr], 0, join(",", @brr), \@op);
sub main
{
my ($a, $b, $lv, $bhistory, $op ) = @_;
my $h = 1;
my ( $w_min, $w_max, $s_min, $s_max );
my $rest;
if ( $lv % 2 == 0) {
$w_min = 0;
$w_max = $a->[1] > $space ? $space : $a->[1];
for my $w ( $w_min .. $w_max )
{
$rest = $space - $w;
$s_min = $w == 0 ? 1 : 0; # 确保不会空船渡河
$s_max = $a->[2] > $rest ? $rest : $a->[2];
for my $s ( $s_min .. $s_max )
{
push @op, [$h, $w, $s];
cross( $a, $b, $h, $w, $s, $lv, $bhistory, $op );
pop @op;
}
}
} else {
$s = 0; # 羊：回去是不可能回去的，只有在对岸才能够生活这样子。
$w_min = 0;
$w_max = $b->[2] > $b->[1] ? 0 :
$b->[2] > $space ? $space : $b->[2] ; # 如果对岸羊>狼则狼不必返回
for my $w ( $w_min .. $w_max )
{
push @op, [$h, $w, $s];
cross( $b, $a, $h, $w, $s, $lv, $bhistory, $op );
pop @op;
}
}
}
sub cross
{
my ($a, $b, $h, $w, $s, $lv, $bhistory, $op) = @_;
cross_river($a, $b, [$h,$w,$s]);
my $chk = $lv % 2 == 0 ? check($a, $b) : check($b, $a);
# 过河后的状态
my $curr_a = join(",", @$a);
my $curr_b = join(",", @$b);
if ($chk == 1) {
if ( $lv % 2 == 0 ) {
unless ( $bhistory =~/$curr_b/ ) {
main($a, $b, $lv+1, $bhistory ." ".$curr_b, $op );
}
} else {
unless ( $bhistory =~/$curr_a/ ) {
main($b, $a, $lv+1, $bhistory ." ".$curr_a, $op );
}
}
}
if ($chk == 2) {
my $ta = [@arr];
my $tb = [@brr];
for my $id ( 0 .. $#$op ) {
if ( $id % 2 == 0 ) {
cross_river( $ta, $tb, $op->[$id] );
printf "[%2d] Go %d,%d,%d ", $id+1, @{$op->[$id]};
} else {
cross_river( $tb, $ta, $op->[$id] );
printf "[%2d] Back %d,%d,%d ", $id+1, @{$op->[$id]};
}
printf "A [%d %d %d], B [%d %d %d]\n", @$ta, @$tb;
}
printf "\n";
}
cross_river( $b, $a, [$h,$w,$s] ); # 恢复
}
sub cross_river {
my ($a,$b,$c) = @_;
grep { $a->[$_]-=$c->[$_],
$b->[$_]+=$c->[$_]; } (0,1,2);
}
sub check {
my ($a, $b, $lv) = @_;
return 0 if ( $a->[1] >= $a->[2] and $a->[2] > 0 and $a->[0] == 0 );
return 0 if ( $b->[1] >= $b->[2] and $b->[2] > 0 and $b->[0] == 0 );
return 2 if ( $a->[1] == 0 and $a->[2] == 0 );
return 1;
}

复制代码

33种结果。
往返累计次数少于10的结果有：

[ 1] Go 1,1,0 A [0 2 3], B [1 1 0]
[ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
[ 3] Go 1,2,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5] Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7] Go 1,0,1 A [0 2 0], B [1 1 3]
[ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
[ 9] Go 1,2,0 A [0 0 0], B [1 3 3]
[ 1] Go 1,1,0 A [0 2 3], B [1 1 0]
[ 2] Back 1,0,0 A [1 2 3], B [0 1 0]
[ 3] Go 1,2,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5] Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7] Go 1,1,1 A [0 1 0], B [1 2 3]
[ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
[ 9] Go 1,1,0 A [0 0 0], B [1 3 3]
[ 1] Go 1,2,0 A [0 1 3], B [1 2 0]
[ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
[ 3] Go 1,1,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5] Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7] Go 1,0,1 A [0 2 0], B [1 1 3]
[ 8] Back 1,0,0 A [1 2 0], B [0 1 3]
[ 9] Go 1,2,0 A [0 0 0], B [1 3 3]
[ 1] Go 1,2,0 A [0 1 3], B [1 2 0]
[ 2] Back 1,0,0 A [1 1 3], B [0 2 0]
[ 3] Go 1,1,0 A [0 0 3], B [1 3 0]
[ 4] Back 1,0,0 A [1 0 3], B [0 3 0]
[ 5] Go 1,0,2 A [0 0 1], B [1 3 2]
[ 6] Back 1,2,0 A [1 2 1], B [0 1 2]
[ 7] Go 1,1,1 A [0 1 0], B [1 2 3]
[ 8] Back 1,0,0 A [1 1 0], B [0 2 3]
[ 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] Go 1,4,0 A [0 3 7], B [1 4 0]
[ 2] Back 1,0,0 A [1 3 7], B [0 4 0]
[ 3] Go 1,3,0 A [0 0 7], B [1 7 0]
[ 4] Back 1,0,0 A [1 0 7], B [0 7 0]
[ 5] Go 1,0,4 A [0 0 3], B [1 7 4]
[ 6] Back 1,4,0 A [1 4 3], B [0 3 4]
[ 7] Go 1,1,3 A [0 3 0], B [1 4 7]
[ 8] Back 1,0,0 A [1 3 0], B [0 4 7]
[ 9] Go 1,3,0 A [0 0 0], B [1 7 7]

复制代码

523066680 · 发表于 2019-3-18 21:56:26

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

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

举个栗子，拿前面1,7,7的方案套用到 1,17,17 船载容量为9 的情况：

[ 1] Go 1,9,0 A [0 8 17], B [1 9 0]
[ 2] Back 1,0,0 A [1 8 17], B [0 9 0]
[ 3] Go 1,8,0 A [0 0 17], B [1 17 0]
[ 4] Back 1,0,0 A [1 0 17], B [0 17 0]
[ 5] Go 1,0,9 A [0 0 8], B [1 17 9]
[ 6] Back 1,9,0 A [1 9 8], B [0 8 9]
[ 7] Go 1,1,8 A [0 8 0], B [1 9 17]
[ 8] Back 1,0,0 A [1 8 0], B [0 9 17]
[ 9] Go 1,8,0 A [0 0 0], B [1 17 17]

复制代码

老刘1号 · 发表于 2019-3-19 14:22:41

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

回复 5# 523066680

第二条学习了，
第一条，其实限制没有那么严，因为船舱中可以“常驻”生物（我研究我代码跑出的结果时偶然发现的
假设船舱容量8，狼、羊均17只，
可以如下操作：

拉8狼过，回此时wolf=9,8
拉7狼过，回此时wolf=2,15
拉8羊过，拉8狼回此时wolf=10,7 sheep=9,8
船上放置2狼，每次载3狼3羊过去即可。

复制代码

其实也没必要太纠结这个问题本身，现实意义不大，
主要是练下回溯法，让程序深度优先遍历所有可能路径。
程序跑出来就有，跑不出就没有，不用动脑，岂不美哉。

523066680 · 发表于 2019-3-19 15:06:52

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

回复 6# 老刘1号

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

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

----补充
也发现用这种往返方式，船载量只要达到4，狼/羊数再往上递增都可以处理，变化的只是往返的次数
最少往返次数的规律 (狼 or 羊个数 * 2)-5

[ 1] Go 1,4,0 A [0 13 17], B [1 4 0]
[ 2] Back 1,0,0 A [1 13 17], B [0 4 0]
[ 3] Go 1,3,0 A [0 10 17], B [1 7 0]
[ 4] Back 1,0,0 A [1 10 17], B [0 7 0]
[ 5] Go 1,0,4 A [0 10 13], B [1 7 4]
[ 6] Back 1,4,0 A [1 14 13], B [0 3 4]
[ 7] Go 1,3,1 A [0 11 12], B [1 6 5]
[ 8] Back 1,2,0 A [1 13 12], B [0 4 5]
[ 9] Go 1,3,1 A [0 10 11], B [1 7 6]
[10] Back 1,2,0 A [1 12 11], B [0 5 6]
[11] Go 1,3,1 A [0 9 10], B [1 8 7]
[12] Back 1,2,0 A [1 11 10], B [0 6 7]
[13] Go 1,3,1 A [0 8 9], B [1 9 8]
[14] Back 1,2,0 A [1 10 9], B [0 7 8]
[15] Go 1,3,1 A [0 7 8], B [1 10 9]
[16] Back 1,2,0 A [1 9 8], B [0 8 9]
[17] Go 1,3,1 A [0 6 7], B [1 11 10]
[18] Back 1,2,0 A [1 8 7], B [0 9 10]
[19] Go 1,3,1 A [0 5 6], B [1 12 11]
[20] Back 1,2,0 A [1 7 6], B [0 10 11]
[21] Go 1,3,1 A [0 4 5], B [1 13 12]
[22] Back 1,2,0 A [1 6 5], B [0 11 12]
[23] Go 1,3,1 A [0 3 4], B [1 14 13]
[24] Back 1,2,0 A [1 5 4], B [0 12 13]
[25] Go 1,3,1 A [0 2 3], B [1 15 14]
[26] Back 1,2,0 A [1 4 3], B [0 13 14]
[27] Go 1,1,3 A [0 3 0], B [1 14 17]
[28] Back 1,0,0 A [1 3 0], B [0 14 17]
[29] Go 1,3,0 A [0 0 0], B [1 17 17]

复制代码

老刘1号 · 发表于 2019-3-19 15:44:50

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

回复 7# 523066680

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

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

老刘1号 · 发表于 2019-3-19 15:59:32

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

回复 7# 523066680

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

设狼、羊数目为n，装载量为4
可以

载4狼过，回
载3狼过，回
载4羊过，载4狼回
船上装2狼，每次运送1狼1羊

复制代码

题目的关键点在于让人不在的位置羊>狼
而准确说有3个位置，当岸、对岸，船
当岸和对岸，人有时候在，有时候不在，而船上人永远是在的
所以船可以无视题目条件，来做“周转”

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

更直观的离子

载2狼1羊过，载2狼回
船上装2狼，每次运送1狼1羊

复制代码

523066680 · 发表于 2019-3-19 16:26:36

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

回复 9# 老刘1号

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

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

		自动登录	找回密码
密码			注册

[新手上路]批处理新手入门导读	[视频教程]批处理基础视频教程	[视频教程]VBS基础视频教程	[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动	[批处理精品]CMD命令50条不能说的秘密	[在线下载]第三方命令行工具	[在线帮助]VBScript / JScript 在线参考

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

评分

评分

评分