Проект Эйлера

[wcl.AleX]

Как можно решить эту задачу, кроме простого перебора?
http://euler.jakumo.org/problems/view/18.html
Найдите максимальную сумму пути с вершины треугольника до его основания.
Начиная в вершине треугольника (пример ниже) и перемещаясь на смежные числа ниже, максимальная сумма до основания составляет 23.

3
7 4
2 4 6
8 5 9 3
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Примечание: Так как в данном треугольнике всего 16384 маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.

[kp9r4d]

Динамическое программирование.

[glukmaker]

Ну зачем же перебирать все маршруты? Некоторое подобие волнового алгоритма. Идем снизу верх.
Начинаем с предпоследней строчки, для каждого элемента сохраняем его сумму с максимальным нижним смежным и запоминаем направление. Ну и так до самого верха.

Кол-во иттераций при этом будет пропорционально кол-ву элементов, а не кол-ву маршрутов.

-- 27.07.2014, 22:20 --

wcl.AleX в сообщении #890401 писал(а):

Найдите максимальную сумму пути от вершины до основания следующего треугольника:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Примечание: Так как в данном треугольнике всего 16384 маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.

Если нам нужна только сумма, то еще проще.
Берем предпоследнюю строку.
Например там стоит 63, а смежные числа с последней строки 04 и 62. Что больше? 62
Потому меняем 63 на 63+62
Далее следующий элемент 66, смежные нижней строки 62 и 98
значит заменяем 66 на 66+98 и так далее, когда дойдем до самого верха - там будет искомая сумма

[Skeptic]

Оба направления счёта: вниз или вверх, равноценны.

[Skeptic]

wcl.AleX в сообщении #890401 писал(а):

Как можно решить эту задачу, кроме простого перебора?
http://euler.jakumo.org/problems/view/18.html
Найдите максимальную сумму пути с вершины треугольника до его основания.
Начиная в вершине треугольника (пример ниже) и перемещаясь на смежные числа ниже, максимальная сумма до основания составляет 23.

3
7 4
2 4 6
8 5 9 3

На сайте по ссылке другая задача: каждое число в строке имеет только два смежных в следущей.

[glukmaker]

Skeptic в сообщении #890812 писал(а):

Оба направления счёта: вниз или вверх, равноценны.

да, чтобы получить правильный ответ особой разницы нет откуда начинать считать, но снизу удобнее, ибо там нет дополнительных проблем.

Если представить треугольник в виде массива A, где верхний элемент A[1,1], нижний левый A[k,1], нижний правый A[k,k], то весь расчет на Delphi, будет выглядеть так:

for i:=k-1 downto 1 do for j:=1 to i do A[i,j]:=A[i,j]+max(A[i+1,j],A[i+1,J+1];

После чего из A[1,1] берем результат...

Если идти сверху вниз, то там понадобятся либо дополнительные проверки, либо дополнительное место для хранения промежуточных данных.

[arseniiv]

Skeptic в сообщении #890846 писал(а):

На сайте по ссылке другая задача: каждое число в строке имеет только два смежных в следущей.

Та же, просто тут код съехал.

-- Чт сен 18, 2014 21:10:17 --

В OEIS, если не ошибаюсь, такие треугольники только так и пишутся в комментариях, и все всё понимают — это распространённая форма записи.