请教欧拉计划第18题

sequencing

欧拉计划第18题(http://projecteuler.net/problem=18)

zhlong8

回复 1# sequencing

use 5.010;
use strict;
use warnings;
use List::Util 'max';
use Data::Dumper;

my @data = (
[qw(75)],
[qw(95 64)],
[qw(17 47 82)],
[qw(18 35 87 10)],
[qw(20 04 82 47 65)],
[qw(19 01 23 75 03 34)],
[qw(88 02 77 73 07 63 67)],
[qw(99 65 04 28 06 16 70 92)],
[qw(41 41 26 56 83 40 80 70 33)],
[qw(41 48 72 33 47 32 37 16 94 29)],
[qw(53 71 44 65 25 43 91 52 97 51 14)],
[qw(70 11 33 28 77 73 17 78 39 68 17 57)],
[qw(91 71 52 38 17 14 91 43 58 50 27 29 48)],
[qw(63 66 04 68 89 53 67 30 73 16 69 87 40 31)],
[qw(04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)],
);


my $pre = shift @data;

for my $line (@data) {
    my @max;
    for my $idx (0 .. @$line-1) {
        my($v1, $v2) = @$pre[$idx-1, $idx];
        $v1 = 0 if $idx == 0;
        $v2 = 0 if $idx == @$line-1;
        push @max, $line->[$idx] + max($v1, $v2);
    }
    $pre = \@max;
    say Dumper $pre;
}


思路是从第一行开始计算每个位置能达到的最大值。

hitsubunnu

回复 2# zhlong8

1. @$line-1   ->    $#$line

复制代码

sequencing

zhlong8 发表于 2012-06-11 13:49
回复 1# sequencing

use 5.010;

多谢版主！

slayer_axe

版主方法不对，以这个例子为例：
   3
  7 4
2 4 6
8 5 9 3

用版主的方法可以计算得到3+7+4+9 = 23，如果将左下角的8换成99，这种方法就得不出正确结论了。
我的办法是假定最后一个元素是$data[$n][$i],那么就有sum[$n][$i] = max($data[$n][$i] +sum[$n-1][$i],$data[$n][$i]+sum[$n-1][$i-1],代码如下：

1. #!/usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. use 5.010;
   
6. 
   
7. my @data = (
   
8. [qw(75)],
   
9. [qw(95 64)],
   
10. [qw(17 47 82)],
    
11. [qw(18 35 87 10)],
    
12. [qw(20 04 82 47 65)],
    
13. [qw(19 01 23 75 03 34)],
    
14. [qw(88 02 77 73 07 63 67)],
    
15. [qw(99 65 04 28 06 16 70 92)],
    
16. [qw(41 41 26 56 83 40 80 70 33)],
    
17. [qw(41 48 72 33 47 32 37 16 94 29)],
    
18. [qw(53 71 44 65 25 43 91 52 97 51 14)],
    
19. [qw(70 11 33 28 77 73 17 78 39 68 17 57)],
    
20. [qw(91 71 52 38 17 14 91 43 58 50 27 29 48)],
    
21. [qw(63 66 04 68 89 53 67 30 73 16 69 87 40 31)],
    
22. [qw(04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)],
    
23. );
    
24. 
    
25. sub max{
    
26. 
    
27.         my ($x,$y) = @_;
    
28.         if($x>$y){
    
29.                 return $x;
    
30.         }else{
    
31.                 return $y;
    
32.         }
    
33. }
    
34. 
    
35. sub sum{
    
36. 
    
37.         my ($row,$column) = @_;
    
38.         my ($sum1,$sum2);
    
39.         if(0>$column){
    
40.                 say 'stop';
    
41.                 return 0;
    
42.         }elsif($column>$row){
    
43.                 say 'stop';
    
44.                 return 0;
    
45.         }
    
46.         if(0==$row){
    
47.                 say 'error';
    
48.                 return undef;
    
49.         }elsif(1==$row){
    
50.                 $sum1 = $data[0][0]+$data[1][0];
    
51.                 $sum2 = $data[0][0]+$data[1][1];
    
52.                 say "row\t$row\tcolumn\t$column\t",$data[$row][$column];
    
53.                 return max($sum1,$sum2);
    
54.         }else{
    
55.                 $sum1 = sum($row-1,$column)+$data[$row][$column];
    
56.                 $sum2 = sum($row-1,$column-1)+$data[$row][$column];
    
57.                 say "row\t$row\tcolumn\t$column\t",$data[$row][$column];
    
58.                 return max($sum1,$sum2);
    
59.         }
    
60. 
    
61. }
    
62. 
    
63. my @sums;
    
64. for(0..14){
    
65. 
    
66.         push @sums,sum(14,$_);
    
67.         say $sums[-1];
    
68. 
    
69. }
    
70. 
    
71. 
    
72. say join "\n",@sums;
    

复制代码

slayer_axe

我这种办法还是不行，全部遍历了一次，数据量大后，会无法处理

zhlong8

slayer_axe 发表于 2012-06-12 11:20
我这种办法还是不行，全部遍历了一次，数据量大后，会无法处理

你的方法就是历遍啊是 O(N!)   没有归约掉不可能的路径。另外99怎么不对了

slayer_axe

我弄错了，抱歉，我把问题搞复杂了。

dgtnk

回复 1# sequencing


    另一种思路 从下到上

1. #!/usr/bin/perl -w
   
2. use strict;
   
3. use 5.010;
   
4. use List::Util 'max';
   
5. 
   
6. 
   
7. my @array;
   
8. my $index = 0;
   
9. 
   
10. while (<DATA>) {
    
11.         my @temp = split;
    
12.         $array[$index] = \@temp;
    
13.         $index ++;
    
14. }
    
15. 
    
16. for  (my $i = $#array; $i > 0; $i --) {
    
17.         for (my $j = 0; $j < @{$array[$i - 1]}; $j ++) {
    
18.                 $array[$i - 1][$j] += max($array[$i][$j], $array[$i][$j + 1]);
    
19.         }
    
20. }
    
21. 
    
22. say $array[0][0];
    
23. 
    
24. __DATA__
    
25. 75
    
26. 95 64
    
27. 17 47 82
    
28. 18 35 87 10
    
29. 20 04 82 47 65
    
30. 19 01 23 75 03 34
    
31. 88 02 77 73 07 63 67
    
32. 99 65 04 28 06 16 70 92
    
33. 41 41 26 56 83 40 80 70 33
    
34. 41 48 72 33 47 32 37 16 94 29
    
35. 53 71 44 65 25 43 91 52 97 51 14
    
36. 70 11 33 28 77 73 17 78 39 68 17 57
    
37. 91 71 52 38 17 14 91 43 58 50 27 29 48
    
38. 63 66 04 68 89 53 67 30 73 16 69 87 40 31
    
39. 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

复制代码

justqb

受到启发。
应该从最下面开始算。

   63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

倒数第二行 第一个 63 可以和倒数第一行第一个 和第二个结合 ，那么取最大的 ，以此类推。
倒数第二行就变成了
63+62 66+98 04+98 68+27 89+23 53+70 67+98 30+98 73+93 16+93 69+53 87+60 40+60 31+23
然后一层一层往上走