Эту задачу мы позаимствовали с сайта Project Euler (задачи № 18 и № 67). Дан числовой треугольник. Мысленно пройдёмся по числам в треугольнике, начиная с вершины, к какому-нибудь числу из нижнего ряда, суммируя числа, встречающиеся на пути. Разрешается шагать или к левому или к правому соседнему числу, расположенному одним этажом ниже. Требуется найти наибольшую сумму (среди всех таких путей). Например, для треугольника на рисунке максимальная сумма равна , а соответствующий путь выделен красным:
Треугольник с числами программа 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