Применил алгоритм, не просто сравнивающий два числа, но и "заглядывающий" на шаг вперед.
Условия задачи
Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.
Примечание: Так как в данном треугольнике всего 16384 возможных маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов. Однако похожая Задача 67 с треугольником, состоящим из сотни строк, не решается перебором (brute force) и требует более умного подхода! ;o)
Описание работы программы
Алгоритм программы
Если идти от вершины треугольника вниз, то на каждом уровне будет развилка, на которой нужно переделить дальнейшее движение.
Идти к 95 или к 64? Вроде бы логично, что путь должен пролегать через наибольшее, т.е. через 95:
(75 + 95) > (75 + 64)
Но каждый выбор ограничивает следующие варианты. Так после 95 можно пойти только на 17 и на 47. Но вот если бы был выбран путь не через 95, а через 64, то от 64 можно пройти к 47 и 82.
(75 + 95 + 47) < (75 + 64 + 82)
Т.е. «правильный» выбор на развилке был не 95, а 64 т.к. необходимо учитывать путь хотя бы на шаг вперёд.
Вот на таком алгоритме строится работа программы.
Работа программы
Для хранения чисел пирамиды создал несколько массивов.
В переменные num1, num2 будут сохраняться 2 числа, которые в данный момент являются развилкой и из которых нужно выбрать одно, по которому пойдёт путь.
Выбранное на развилке число будет сохраняться в переменную max_num и прибавляться к sum_num для подсчета суммы пути.
indx - это индекс в массиве первого числа на развилке, от него считаются все остальные индексы.
Так indx = 3, к примеру, будет означать, что развилка идёт на числах
массивN[3], массивN[4]
и от них путь может пойти на числа
массивN+1[3], массивN+1[4], массивN+1[5]
Работа функции get_path()
Функция get_path() работает с данными через указатели и определяет путь по которому пойдет маршрут. Алгоритм ее работы описан выше по тексту и в комментариях к коду. Надеюсь все понятно.
Ответ на задачу
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера 18 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))