Проект Эйлера (15 задача) – на первый взгляд очень простая, однако поиск действительно эффективного алгоритма заставил поломать голову
Узнать больше в телеграм-канале: ProjectEuler++
Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.
Сколько существует таких маршрутов в сетке 20×20?
В программе мы посчитаем количество вариантов попасть в каждый узел сетки. В итоге мы получим количество маршрутов от верхнего левого до нижнего правого угла сетки.
Для понятного примера возьмем сетку с ячейками 2 x 2 и преобразуем ее в граф с вершинами в узлах сетки 3 x 3. Для понятности все нарисовал (рисунок 1).
Рисунок 1: узел a (левый верхний угол сетки) – это начало движения, узел k (правый нижний угол) – конец.
В итоге можно вычислить количество маршрутов до точки как сумму маршрутов до точки сверху и точки слева.
Рисунок 8: чтобы автоматизировать расчеты нужно заполнить начальные данные. Потому первый ряд – точки a b c заполнил единицами (1 возможный маршрут). Также добавим дополнительный (нулевой) столбик слева от первого столбца – a d g и заполнил его нулями (туда нельзя попасть).
Это позволяет по одной формуле вычислять все остальные точки, например, точка d вычисляется как 0 + 1 (рисунок 8).
Представляем сетку 20 x 20 клеток как граф 21 x 21 вершин, добавим к нему столбик с нулями слева и получится граф 21 x 22.
Можно создать двумерный массив [21][22] для хранения вершин графа. Однако для решения задачи вполне достаточно одного ряда узлов – массива длиной [22]. В него последовательно будут перезаписываться данные всех рядов.
Сначала зададим начальные данные. Левый верхний узел имеет координату в массиве [1] и попасть в него можно только единственным путем.
Поскольку массив в остальных координатах заполнен нулями, потому первый ряд по формуле заполнится единицами.
Это абсолютно верно, потому что в него можно попасть единственным путем – слева. Напомню, что левый столбик с координатой [0] добавлен как вспомогательный. Его значение нулевое, потому что попасть туда нельзя.
На второй итерации цикла for() будет вычисляться второй ряд. При этом данные первого ряда в массиве будут использоваться и перезаписываться данными второго ряда. Потом третий и так далее.
В итоге, если печатать данные массива одновременно с их вычислении, то получится следующая картина:
При этом самая последняя ячейка массива, самой последней итерации вычисления ряда в итоге будет содержать искомый ответ.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
В итоге ответ на 15 задачу проекта Эйлера составил 137846528820, программа считает ответ практически мгновенно.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
