Глава 25. Путь с максимальной суммой в числовом треугольнике

Разработка
	Глава 25. Путь с максимальной суммой в числовом треугольнике

Разработка

Метод грубой силы

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

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

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

Perl
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$ , процедура возвращает значение $- \infty$ . Если $i = j = 0$ , возвращается $t_{0, 0}$ . Теперь, когда все особые случаи обработаны, остаётся общий случай. Вычисляются при помощи рекурсивных вызовов значения $a = m_{j - 1, i - 1}$ и $b = m_{j - 1, i}$ и возвращается значение $t_{j, i} + \max (a, b)$ .

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

Perl
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$ :

Perl
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. Для этого перед рекурсивными вызовами вставим строку

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

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

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

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

Индуктивная версия

Мы видим, что в обеих рекурсивных версиях программы не обошлось без индуктивных вычислений, правда, очень простых — вычислялся максимум в числовой последовательности $〈m_{n, 0}, \dots, m_{n, n}〉$ . Но всё-таки главным приёмом программирования служила рекурсия. Теперь же нам понадобятся нетривиальные индуктивные вычисления: в качестве элементов последовательности выступят строки треугольника, а в качестве вычисляемого значения — наборы чисел $s_{i}$ — это максимальные суммы, вычисленные вдоль путей, ведущих из вершины треугольника в $i$ -й элемент последней обработанной строки треугольника. По мере чтения строк треугольника набор чисел $s_{i}$ перевычисляется.

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

Perl
my @s=(0);

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

Perl
while(<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 — это и есть ответ:

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


Идеи реализации		Готовая программа