Проект Эйлера (18 задача) познакомит Вас с динамическим программированием (разбиение решения сложной задачи на более простые подзадачи)
Узнать больше в телеграм-канале: ProjectEuler++
Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.
То есть, 3 + 7 + 4 + 9 = 23.
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
Примечание: Так как в данном треугольнике всего 16384 возможных маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов. Однако похожая Задача 67 с треугольником, состоящим из сотни строк, не решается перебором (brute force) и требует более умного подхода! ;o)
Можно конечно просто двигаться сверху пирамиды вниз и на каждой развилке сворачивать на большее число. Проследим получившийся путь:
Однако остановимся на этом и подумаем, нет ли лучшего пути.
Что будет, если от 65 пойти не к большему (95), а к меньшему (64) числу:
Уже на начальном участке видно, что такой подход (на каждой развилке идти на большее число) в итоге не гарантирует максимальную длину пути.
Неужели придется перебирать все варианты пути (16384 маршрута) и сравнивать их суммы между собой? Конечно, такой подход вернет правильный результат, однако, считаться будет долго.
Решением будет разбитие задачи на две более легкие:
Возьмем для примера крайнее левое число из предпоследнего ряда – 64. От него можно пойти либо на 4, либо на 62. Таким образом максимальная сумма пути для этой развилки:
Пройдем дальше по ряду и запишем получившиеся данные в следующую ячейку.
Пройдем весь ряд до конца:
…и заменим значения в нем таким же образом:
После этого переходим на ряд выше и заполняем его:
Число 91 теперь также будет выбирать путь к максимальному числу. Однако выбирать оно будет не между числами (63, 66), а между ранее посчитанными максимальными путями для развилок (126, 164).
В итоге необходимо просто пройти пирамиду сверху вниз и на каждой развилке посчитать сумму с максимальным числом из нижнего ряда. За один проход ответ будет найден и записан вместо вершины (75).
Числа пирамиды сохранены в двумерный массив (смотрите выше). При этом ширина рядов массива выбрана на одно число больше, чем ширина максимальной (нижней) строки пирамиды.
Это сделано, потому что ряды чисел пирамиды – разной длины. Однако, за счет того, что при инициализации массива ячейки, не занятые числами будут заполнены нулями, это позволит останавливать прохождение ряда чисел при встрече с нулем.
Конструкция:
…будет работать до тех пор, пока значение в ячейке массива arr[row][indx] не нулевое.
Тернарная операция:
… прибавляет к значению ячейки массива arr[row][indx] максимальное из двух смежных ячеек нижестоящего ряда и может быть записана иначе:
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
