[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖
本帖最后由 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

评分人数

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

评分人数

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]
复制代码

TOP

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

回复 9# 老刘1号

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

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

TOP

返回列表