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

Постановка задачи
Идеи реализации
Метод грубой силы
Рекурсивное решение
Рекурсия с мемоизацией
Индуктивное решение
Разработка
Метод грубой силы
Рекурсивная версия
Рекурсивная версия с мемоизацией
Индуктивная версия
Готовая программа
Метод грубой силы
Рекурсивная версия
Рекурсивная версия с мемоизацией
Индуктивная версия

Эту задачу мы позаимствовали с сайта Project Euler (задачи № 18 и № 67). Дан числовой треугольник. Мысленно пройдёмся по числам в треугольнике, начиная с вершины, к какому-нибудь числу из нижнего ряда, суммируя числа, встречающиеся на пути. Разрешается шагать или к левому или к правому соседнему числу, расположенному одним этажом ниже. Требуется найти наибольшую сумму (среди всех таких путей). Например, для треугольника на рисунке максимальная сумма равна 23, а соответствующий путь выделен красным: 3 7 4 2 4 6 8 5 9 3

Треугольник с числами программа maxpathsum.pl считывает со стандартного ввода:

% ./maxpathsum.pl 3 7 4 2 4 6 8 5 9 3 ␄ 23

Конечно, отлаживать программу, каждый раз вводя все эти числа, невозможно. Предлагаем файлы с уже готовыми треугольниками (4, 15, 100 строк), из которых можно перенаправить стандартный ввод:

% ./maxpathsum.pl <maxpathsum-4.txt 23 % ./maxpathsum.pl <maxpathsum-15.txt 1074 % ./maxpathsum.pl <maxpathsum-100.txt 7273

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