Разработка

Прежде всего следует прочитать все числа треугольника в двумерный массив @t:

my @t;
push @t, [split ' '] for <STDIN>;

Оставшаяся часть программы посвящена перебору всевозможных путей в треугольнике, вычислению сумм вдоль каждого из них, поиску максимальной из них и выводу результата. Пути кодируются числами $x от 0 до 2**@t-1 включительно. Каждое из чисел следует превратить в последовательность числовых пар $j, $i, которые служат индексами в массиве @t. Следуя, таким образом, от числа к числу в треугольнике, добавляем встретившиеся числа к переменной $sum (равной нулю в начале обработки очередного числа), получим сумму вдоль пути. Тут же, если необходимо, обновляем переменную $max, предназначенную для наибольшей из сумм:

my $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, вычисляющей m j , i . Она получает в качестве параметров числа j i . Если i < 0 или i > n , процедура возвращает значение . Если i = j = 0 , возвращается t 0 , 0 . Теперь, когда все особые случаи обработаны, остаётся общий случай. Вычисляются при помощи рекурсивных вызовов значения a = m j 1 , i 1 и b = m j 1 , i и возвращается значение t j , i + max a b .

Итак, определение процедуры maxsum:

sub 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);
}

Остаток программы посвящён индуктивному вычислению максимального среди чисел m n , i для всевозможных i:

my $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 j , i в массиве @m возложим на процедуру maxsum. Для этого перед рекурсивными вызовами вставим строку

return $m[$j][$i] if defined $m[$j][$i];

Строка сработает, если нужное значение уже было ранее вычислено и содержится в массиве. Если так, то выполнение процедуры на этом завершено и до рекурсивных вызовов дело даже не дойдёт.

В противном случае делаем то же самое, что и раньше, но, вычислив m j , i , не забываем сохранить его в массиве. Это удобно сделать одновременно с возвратом:

return $m[$j][$i]=$t[$j][$i]+($a>$b? $a: $b);

Мы видим, что в обеих рекурсивных версиях программы не обошлось без индуктивных вычислений, правда, очень простых — вычислялся максимум в числовой последовательности m n , 0 m n , n . Но всё-таки главным приёмом программирования служила рекурсия. Теперь же нам понадобятся нетривиальные индуктивные вычисления: в качестве элементов последовательности выступят строки треугольника, а в качестве вычисляемого значения — наборы чисел s i — это максимальные суммы, вычисленные вдоль путей, ведущих из вершины треугольника в i-й элемент последней обработанной строки треугольника. По мере чтения строк треугольника набор чисел s i перевычисляется.

Значениями нашей индуктивной функции являются списки числовых значений s i . Для них заготовим переменную — массив @s:

my @s=(0);

В индуктивном цикле прежде всего считывается очередная строка из последовательности строк треугольника:

while(<STDIN>)
{
	my @r=split ' ';
	

Остаток цикла посвящён перевычислению массива @s. Это перевычисление — многоходовый процесс, и было бы нежелательно портить элементы массива @s как раз в то время, когда он перевычисляется. Стандартный выход из положения состоит в том, чтобы завести другой массив для хранения новых, перевычисленных значений, и когда они все будут готовы, присвоить этот вспомогательный массив массиву @s. Но в нашем случае нет нужды в ещё одном массиве. Все вычисления можно сделать прямо в массиве @r.

При перевычислении нужно все элементы массива $r[$_] увеличить на максимальное из чисел $s[$_-1] и $s[$_]. Этот максимум даётся выражением $s[$s[$_-1]>$s[$_]? $_-1: $_], так что получаем вложенный цикл

	$r[$_]+=$s[$s[$_-1]>$s[$_]? $_-1: $_] for 1..$#r-1;

Обратите внимание, что индексы $_ пробегают в цикле значения от 1 до $#r-1, так что из обработки исключаются первый и последний элементы массива. Для них нужно другое правило перевычисления:

	$r[$_]+=$s[$_] for -1, 0;

Индуктивный цикл завершается обещанным присваиванием

	@s=@r;
}

Присваивание my @s=(0); в самом начале программы избавило нас от трудностей во внутренних циклах. Будь массив @s пустой, значения $s[0] и $s[-1] оказались бы неопределёнными.

Завершает программу вычисление максимального элемента в массиве @s — это и есть ответ:

my $max=-INFINITY;
for(@s)
{
	$max=$_ if $_>$max;
}
print "$max\n";

Информатика-54© А. Н. Швец