Problem18
30分プログラム、その284。Problem18 via Project Euler。
以下の三角形の頂点から下まで移動するとき、その数値の合計の最大値は23になる。
3 7 5 2 4 6 8 5 9 3この例では 3 + 7 + 4 + 9 = 23
以下の三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。
75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 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注: ここではたかだか 16384 通りのルートしかないので、すべてのパターンを試すこともできる。Problem 67 は同じ問題だが100行あるので、総当りでは解けない。もっと賢い方法が必要である。
言外に「総当りはダメだよ」と書いてある気がするけど、とりあえず総当りで。賢いアルゴリズムを探す前に答えを出しておくのも重要ですよ、うん。
使い方
$ time perl problem18.pl 1074 perl problem18.pl 0.63s user 0.03s system 91% cpu 0.720 total
ソースコード
#! /usr/bin/perl # -*- mode:perl; coding:utf-8 -*- # # problem18.pl - # # Copyright(C) 2008 by mzp # Author: MIZUNO Hiroki / mzpppp at gmail dot com # http://howdyworld.org # # Timestamp: 2008/04/11 08:28:58 # # This program is free software; you can redistribute it and/or # modify it under MIT Lincence. # use strict; use warnings; my @small = ( [qw(3)], [qw(7 5)], [qw(2 4 6)], [qw(8 5 9 3)]); my @large = ( [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)]); sub left($){ $_[0]; } sub right($){ $_[0]+1; } sub max($$@){ my ($x,$y,@pyramid) = @_; if(@pyramid <= $y){ 0; }else{ my $left = $pyramid[$y][$x] + &max(left($x),$y+1,@pyramid); my $right = $pyramid[$y][$x] + &max(right($x),$y+1,@pyramid); $left > $right ? $left : $right; } } print max(0,0,@large),"\n";
