Несложная задача с точки зрения программирования, но вот сам алгоритм заставил поломать голову.
Условия задачи
Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.
Сколько существует таких маршрутов в сетке 20×20?
Описание алгоритма решения задачи
Общая задумка алгоритма - посчитать количество вариантов попасть в каждый узел сетки.
Для примера преобразую сетку с ячейками 2 x 2 в граф с вершинами в узлах сетки 3 x 3. Для понятности все нарисовал (рисунок 1).
Рисунок 1: узел a (левый верхний угол сетки) - начало движения, узел k (правый нижний угол) - конец.
Рисунок 2: при любом маршруте в узел a можно попасть только одним способом, т.к. отсюда по условию нужно начинать, в узлы b и c также можно попасть только одним маршрутом (слева направо).
Рисунок 3: в узлы d и g можно попасть также одним способом (сверху вниз)
Рисунок 4 поясняет суть алгоритма.
Во всех остальные точки кроме крайне левых и верхних можно попасть как сверху так и слева.
Попасть в точку e можно попасть из точки b (сверху) и из точки d (слева). При этом ранее посчитано, что в точку a можно попасть одним маршрутом, и в b - одним. Следовательно, сложив маршруты до них (1 + 1) получим 2 маршрута до точки e.
Рисунок 5: точка b (1 маршрут) + точка e (2 маршрута) => до точки f можно добраться 3 маршрутами.
Ход рассуждений дальше идет так же и на рисунке 7 видно, что до точки k (правый нижний угол) можно добраться 6 маршрутами, как и было в условиях задачи.
Таким образом можно вычислить количество маршрутов до точки как сумму маршрутов до точки сверху и точки слева.
Сама программа
Рисунок 8: чтобы автоматизировать расчеты нужно заполнить начальные данные.
- Первый ряд - точки a b c заполнил единицами (1 возможный маршрут).
- Добавил дополнительный (нулевой) столбик слева от первого столбца - a d g и заполнил его нулями.
Это позволяет по одной формуле вычислять все остальные точки, например, точка d вычисляется как 0 + 1 (рисунок 8).
Сетка 20 x 20 даст 21 x 21 вершину, добавим столбик слева и получится 21 x 22.
unsigned long long prev[22] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
unsigned long long next[22] = {0};
Заполняю первый ряд единицами, следующий - нулями.
num = prev[column] + next[column-1];
next[column] = num;
Вычисляю вершину как сумму маршрутов до вершины сверху и вершины слева.
Ответ на задачу:
Считает почти мгновенно.
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера 15 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))