Chinaunix

标题: 请教欧拉计划第18题 [打印本页]

---

作者: sequencing    时间: 2012-06-11 10:57
标题: 请教欧拉计划第18题

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

---

作者: zhlong8    时间: 2012-06-11 13:49


回复 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    时间: 2012-06-11 14:14
回复 2# zhlong8

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

复制代码

---

作者: sequencing    时间: 2012-06-11 17:12

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

use 5.010;

多谢版主！

---

作者: slayer_axe    时间: 2012-06-12 10:50
版主方法不对，以这个例子为例：
   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    时间: 2012-06-12 11:20
我这种办法还是不行，全部遍历了一次，数据量大后，会无法处理

---

作者: zhlong8    时间: 2012-06-12 11:39

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

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

---

作者: slayer_axe    时间: 2012-06-12 12:00
我弄错了，抱歉，我把问题搞复杂了。

---

作者: dgtnk    时间: 2012-06-13 08:56


回复 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    时间: 2012-06-14 19:30
受到启发。
应该从最下面开始算。

   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
然后一层一层往上走

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2