Прежде всего следует прочитать все числа треугольника в двумерный массив
@t
:
Perlmy @t; push @t, [split ' '] for <STDIN>;
Оставшаяся часть программы посвящена перебору всевозможных путей
в треугольнике, вычислению сумм вдоль каждого из них, поиску максимальной из
них и выводу результата. Пути кодируются числами $x
от
0
до 2**@t-1
включительно.
Каждое из чисел следует превратить в последовательность числовых пар
$j
, $i
, которые служат индексами
в массиве @t
. Следуя, таким образом, от числа к числу
в треугольнике, добавляем встретившиеся числа к переменной
$sum
(равной нулю в начале обработки очередного числа),
получим сумму вдоль пути. Тут же, если необходимо, обновляем переменную
$max
, предназначенную для наибольшей из сумм:
Perlmy $max=-INFINITY; for my $x(0..2**@t-1) { my $sum=0; my $i=0; for my $j(0..$#t) { $sum+=$t[$j][$i]; $i+=$x % 2; $x=int($x/2); } $max=$sum if $sum>$max; } print "$max\n";
Как и раньше, считываем числа треугольника в массив @t
.
Главной частью рекурсивной реализации является определение процедуры
maxsum
, вычисляющей
.
Она получает в качестве параметров числа
.
Если
или
,
процедура возвращает значение . Если
,
возвращается
.
Теперь, когда все особые случаи обработаны, остаётся общий случай. Вычисляются
при помощи рекурсивных вызовов значения
и
и возвращается значение
.
Итак, определение процедуры maxsum
:
Perlsub maxsum { my ($j, $i)=@_; return -INFINITY if $i<0 or $i>$j; return $t[0][0] unless $j; my $a=maxsum($j-1, $i-1); my $b=maxsum($j-1, $i); return $t[$j][$i]+($a>$b? $a: $b); }
Остаток программы посвящён индуктивному вычислению максимального среди чисел для всевозможных :
Perlmy $max=-INFINITY; for my $i(0..$#t) { my $sum=maxsum($#t, $i); $max=$sum if $sum>$max; } print "$max\n";
Текст рекурсивной программы, использущей мемоизацию, имеет минимальные отличия
от текста просто рекурсивной версии. Одно отличие — объявление двумерного
массива @m
, в котором будут размещаться вычисленные
процедурой maxsum
значения — в ячейку $m[$j][$i]
отправится число, возвращённое при вызове
maxsum($j, $i)
.
Заботу о мемоизации значений
в массиве @m
возложим на процедуру
maxsum
. Для этого перед рекурсивными вызовами вставим
строку
Perlreturn $m[$j][$i] if defined $m[$j][$i];
Строка сработает, если нужное значение уже было ранее вычислено и содержится в массиве. Если так, то выполнение процедуры на этом завершено и до рекурсивных вызовов дело даже не дойдёт.
В противном случае делаем то же самое, что и раньше, но, вычислив , не забываем сохранить его в массиве. Это удобно сделать одновременно с возвратом:
Perlreturn $m[$j][$i]=$t[$j][$i]+($a>$b? $a: $b);
Мы видим, что в обеих рекурсивных версиях программы не обошлось без индуктивных вычислений, правда, очень простых — вычислялся максимум в числовой последовательности . Но всё-таки главным приёмом программирования служила рекурсия. Теперь же нам понадобятся нетривиальные индуктивные вычисления: в качестве элементов последовательности выступят строки треугольника, а в качестве вычисляемого значения — наборы чисел — это максимальные суммы, вычисленные вдоль путей, ведущих из вершины треугольника в -й элемент последней обработанной строки треугольника. По мере чтения строк треугольника набор чисел перевычисляется.
Значениями нашей индуктивной функции являются списки числовых значений
.
Для них заготовим переменную — массив @s
:
Perlmy @s=(0);
В индуктивном цикле прежде всего считывается очередная строка из последовательности строк треугольника:
Perlwhile(<STDIN>) { my @r=split ' '; …
Остаток цикла посвящён перевычислению массива @s
. Это
перевычисление — многоходовый процесс, и было бы нежелательно портить элементы
массива @s
как раз в то время, когда он перевычисляется.
Стандартный выход из положения состоит в том, чтобы завести другой массив для
хранения новых, перевычисленных значений, и когда они все будут готовы,
присвоить этот вспомогательный массив массиву @s
. Но в нашем
случае нет нужды в ещё одном массиве. Все вычисления можно сделать прямо
в массиве @r
.
При перевычислении нужно все элементы массива $r[$_]
увеличить на максимальное из чисел $s[$_-1]
и $s[$_]
. Этот
максимум даётся выражением $s[$s[$_-1]>$s[$_]? $_-1:
$_]
, так что получаем вложенный цикл
Perl$r[$_]+=$s[$s[$_-1]>$s[$_]? $_-1: $_] for 1..$#r-1;
Обратите внимание, что индексы $_
пробегают в цикле значения
от 1
до $#r-1
, так что из
обработки исключаются первый и последний элементы массива. Для них нужно другое
правило перевычисления:
Perl$r[$_]+=$s[$_] for -1, 0;
Индуктивный цикл завершается обещанным присваиванием
Perl@s=@r; }
Присваивание my @s=(0);
в самом начале программы
избавило нас от трудностей во внутренних циклах. Будь массив
@s
пустой, значения $s[0]
и
$s[-1]
оказались бы неопределёнными.
Завершает программу вычисление максимального элемента в массиве
@s
— это и есть ответ:
Perlmy $max=-INFINITY; for(@s) { $max=$_ if $_>$max; } print "$max\n";