Идеи реализации

Нетерпеливые люди конечно же захотят организовать перебор всех возможных путей, ведущих от вершины треугольника к числам в нижнем ряду. Прежде чем программировать такой перебор, давайте подсчитаем пути. Каждый путь, дошедший до k-й строки треугольника, можно продолжить до k + 1 -й строки ровно двумя способами: шагнув или влево, или вправо. Так что с возрастанием количества строк число путей растёт в геометрической прогрессии, увеличиваясь с каждой новой строкой в два раза. Для треугольника с n строками потребуется n 1 шаг, поэтому число возможных путей равно 2 n 1 . После пары десятков строк количество вариантов достигнет десятков миллионов, и тут метод полного перебора (метод грубой силы) утратит всю свою брутальную привлекательность.

Всё же разберём этот метод, поскольку он по-своему интересен.

Если каждый шаг вниз и влево кодировать нулём, а вниз и вправо — единицей, путь будет кодироваться последовательностью нулей и единиц. Такие последовательности, как мы знаем, находятся во взаимно-однозначном соответствии с целыми неотрицательными числами (одним из возможных соответствий является запись числа в двоичной системе). Поэтому перебор путей в треугольнике c n строками — это в сущности перебор не более чем n 1 -значных двоичных чисел, то есть чисел в диапазоне 0 2 n 1 . Таким образом, следует перебирать целые неотрицательные числа из указанного диапазона. Каждое число разбирается на двоичные цифры (это удобно делать начиная с младших цифр). Пользуясь последовательностью цифр как маршрутом в треугольнике, суммируем встречающиеся числа. Для получившейся последовательности сумм индуктивно находим максимум.

Пронумеруем строки треугольника индексами j, а числа в каждой строке — индексами i, 0 j n , 0 i j . Обозначим число, стоящее в треугольнике в j-й строке и на i-м месте как t j , i . Заметим, что в типичном случае маршрут может придти к числу t j , i из двух чисел, расположенных на предыдущей строке: t j 1 , i 1 и t j 1 , i . Исключение составляют числа, стоящие на правой и левой сторонах треугольника, соответственно t j , 0 (в него ведёт единственный путь из t j 1 , 0 ) и t j , j (из t j 1 , j 1 ).

Разберём по отдельности все три случая. Введём обозначение m j , i для максимальной суммы среди всех путей, ведущих к числу t j , i .

Эти выражения означают, что вычисление m j , i сводится к вычислению значений m j 1 , i 1 и m j 1 , i (или в особых случаях одного из них). Напрашивается рекурсивное решение, в котором вычислению m j , i посвящена отдельная процедура. Ответом в задаче будет максимальное из чисел m n , i (n — номер последней строки треугольника, 0 i n ).

Чтобы не разбирать отдельно особые случаи (когда элемент m j , i находится на левой или правой границе треугольника и не имеет левого или правого верхнего соседа), положим m j , i = , если i < 0 или i > j . Тем самым мы сделаем те пути, которые пытаются выйти за пределы треугольника, абсолютно непривлекательными с точки зрения вычисляемой вдоль них суммы. Они заведомо не выдержат конкуренции с путями, поворачивающими в другую сторону, что нам, собственно, и нужно.

Рекурсивное решение имеет свои недостатки. Во-первых, глубина рекурсивных вызовов достигает числа строк в треугольнике, а Perl, как мы знаем, нервно относится к глубокой рекурсии. Второй недостаток, гораздо более существенный, связан с тем, что рекурсивная процедура вызывается многократно для вычисления m j , i для одних и тех же j, i. Например, для треугольника на рисунке мы заставили процедуру выводить на экран числа j i , для которых она вызывается. Получилась такая последовательность вызовов: 3 0 , 2 0 , 1 0 , 0 0 , 3 1 , 2 0 , 1 0 , 0 0 , 2 1 , 1 0 , 0 0 , 1 1 , 0 0 , 3 2 , 2 1 , 1 0 , 0 0 , 1 1 , 0 0 , 2 2 , 1 1 , 0 0 , 3 3 , 2 2 , 1 1 , 0 0 . Видно, что для каждой пары процедура вызывается в среднем по 2,6 раза. Аналогичный анализ для треугольника с пятнадцатью строками показывает, что для каждой пары процедура вызывается в среднем примерно 546 раз. Количество избыточных повторных вызовов катастрофически растёт с увеличением размеров треугольника.

Тут нам на помощь приходит мемоизация. Будем хранить в памяти, помимо самого треугольника t j , i , ещё и таблицу m j , i . При вызове процедуры с параметрами j i ищем первым делом число m j , i в таблице, и, если находим, тут же возвращаем его. И уж если ячейка таблицы пока ещё не заполнена, только в этом случае вычисляем её, прибегая к рекурсивным вызовам, а вычислив, возвращаем.

Все предыдущие решения имеют ещё один недостаток, помимо уже упомянутых. В каждом из них необходимо перед началом вычислений держать в памяти весь треугольник t j , i (а в решении с мемоизацией ещё и m j , i ).

Между тем имеется быстрое решение, лишённое и этого недостатка. Оно использует идею индуктивного вычисления. Элементами последовательности служат строки треугольника, так что, обработав очередную строку, уже нет нужды возвращаться к ней вновь, а значит, не нужно держать в памяти весь треугольник.

Та функция, вычислению которой посвящена программа, не является индуктивной, однако можно построить индуктивное расширение. Это функция, вычисляющая таблицу s i . Так мы обозначим максимальную из сумм вдоль всевозможных путей, ведущих из вершины треугольника к i -му числу в его последней строке, 0 i n . Ясно, что искомая функция вычисляется, если известны значения s i , как наибольшее из них: f ω = max 0 i n s i ω .

Убедиться в индуктивности функции s i позволяют формулы перевычисления. Пусть r i  — очередной ряд чисел из треугольника. Тогда s i ω r i = r i + s i ω при i = 0 , max s i 1 ω s i ω при 0 < i < n , s i 1 ω при i = n (здесь n — количество элементов в новой строке треугольника, и, заодно, номер этой строки).

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