На моем сайте Old Programmer собраны все материалы по различным темам программирования. Отдельно выделен раздел, посвященный рекурсивному программированию, где можно найти статьи и видеоуроки. Сегодня мы разберем еще одну интересную задачу из архива олимпиадных соревнований.
Олимпиадная задача "Игра в числа"
Условие задачи
Даны два целых числа: N и M, причем M < N. В игре участвуют два соперника — игрок А и игрок В. Они ходят по очереди, начиная с игрока А. За один ход можно назвать любое целое число в диапазоне от 1 до M включительно. Все названные числа суммируются. Побеждает тот игрок, чей ход приводит к тому, что общая сумма становится равной заданному числу N.
Рассмотрим пример: пусть N = 10, а M = 5. Возможная партия: А называет 4, В называет 2, А называет 4. В результате сумма становится 10 на ходе игрока А, поэтому он побеждает.
Обратите внимание: Россия-Венгрия. Очередная невнятная игра.
Необходимо написать программу, которая принимает на вход числа N и M (они задаются в одной строке через пробел). На выходе программа должна вывести все возможные последовательности ходов (числа, которые называли игроки по очереди), в которых побеждает игрок А, начинающий игру. Важное ограничение: из рассмотрения исключаются неправдоподобные варианты, когда игрок имеет возможность выиграть на своем ходе, но сознательно этого не делает. Например, для N=10 и M=5 не должен учитываться вариант А-4, В-2, А-2, В-2, потому что после хода А-2 сумма стала бы 8, а на следующем ходе В-2 сумма стала бы 10, и победил бы В, хотя у А был шанс выиграть раньше.
Примеры работы программы
Пример 1: Входные данные: 8 6
Выходные данные (последовательности ходов):
1 1 6
1 2 5
1 3 4
1 4 3
1 5 2
1 6 1
Пример 2: Входные данные: 6 2
Выходные данные:
1 1 1 1 2
1 1 1 2 1
2 2 2
Решение задачи
Классическое решение подобных задач строится на использовании рекурсии. Алгоритм последовательно моделирует все возможные ходы игроков, начиная с нулевой суммы, и отслеживает, когда сумма достигает значения N. Ключевой момент — проверка на «правдоподобность»: если на каком-то ходе у игрока есть возможность сразу достичь суммы N (то есть разница между N и текущей суммой меньше или равна M), он обязан это сделать, и ветка рекурсии, где он этого не делает, отсекается.
Готовое решение на языке C можно найти в файле chi4000.c. Это наглядный пример того, как рекурсивный подход позволяет элегантно перебрать все возможные состояния игры.
На этом все. Продолжайте развивать навыки рекурсивного мышления. Подписывайтесь на обновления сайта Old Programmer, чтобы не пропустить новые разборы задач и материалы.
Больше интересных статей здесь: Спорт.
Источник статьи: Рекурсия в программировании. Очередная олимпиадная задача.
