Схема "Перенести часть условий в проверку"
Back Home Up Next

Бывает, что в исходной задаче A рекурсия в явном виде сразу не обнаруживается или достаточно сложна для алгоритмической реализации. Однако удаление части условий из A приводит к новой вспомогательной задаче B, рекурсивный алгоритм решения которой строится без особых затруднений. В этом случае чтобы узнать, является ли полученный для B ответ (ответы) решением задачи A, необходимо проверить, выполняются ли для него ранее удаленные условия или нет. Если решение задачи сводится к вычислению значения истинности некоторого предиката, непосредственно построенного из конъюнкции условий задачи на наборах входных данных, то описанная схема допускает возможность проверки выполнимости удаляемых условий как до использования рекурсивного алгоритма решения вспомогательной задачи, так и после этого. Заметим, что опорная схема “Перенести …” может рассматриваться как конкретная разновидность схемы “Обобщить”. Дело в том, что, перенося одно или несколько условий исходной задачи A в проверку, то есть, фактически временно отбрасывая их, мы получаем новую задачу B, являющуюся естественных обобщением A. Впрочем, иногда схему “Перенести …” удобно интерпретировать как разновидность схемы “Переформулировать”. Рассмотрим пример.

В гостях было n человек. Каждый из них пришел со своей шляпой, но ушел с какой-либо чужой шляпой. Подсчитаем, сколькими способами это могло произойти.

Если в исходной комбинаторной задаче A отбросить условие “чужой”, то есть заменить в формулировке A фразу “ушел с какой-либо чужой шляпой” на фразу “ушел с какой-либо шляпой”, то вновь полученная задача B решается очевидным образом и ответом для неё будет число n!. Однако из этого ответа ничего путного для решения исходной задачи A непосредственно извлечь не удается. Но решать B можно по разному. Например, способом полного перебора. То есть сгенерировать список всех возможных случаев ухода гостей (при небольших значениях n), а далее, возвращаясь к A, удалить из полученного списка те случаи, которые соответствуют событию “Хотя бы один гость ушел в своей шляпе”. Все оставшиеся случаи и только они соответствуют событию “Каждый гость ушел в чужой шляпе” а, следовательно, их количество и есть решение задачи A.

Пусть гости и соответствующие им шляпы пронумерованы натуральными числами от 1 до n. Тогда всякой перестановке (i1, i2,…, in) этих чисел соответствует уход гостей, при котором человеку с номером k досталась шляпа ik (k=1, 2, …, n). Описанный выше алгоритм реализуется двумя функциями: permut(n) и hats(n). Рекурсивная функция permut(n) методом вертикальной прогонки, суть которой описана в Приложении 3, генерирует и возвращает матрицу M размера n!´n всех перестановок из элементов множества {1, 2, …, n}. Элементы каждой строки M образуют одну из таких перестановок. Далее, головная функция hats(n), последовательно сканируя столбцы транспонированной к M матрицы, подсчитывает количество перестановок, соответствующих событию “Каждый гость ушел в чужой шляпе”, то есть непосредственно решает исходную задачу.

Контрольные примеры. Результаты вычислений для n = 1..9 приведены ниже:

n

1

2

3

4

5

6

7

8

9

hats(n)

0

1

2

9

44

265

1854

14833

133496

Замечание. При n³10 простой и ясный метод полного перебора становится неэффективным. И при необходимости решать так называемую общую задачу о смещении, то есть подсчете количества перестановок (i1, i2,…, in) из n элементов {1, 2, …, n}, для которых ik ¹ k при всех k (k=1, 2, …, n), приходится поступать иначе. Например, пользуясь общим комбинаторным методом включения и исключения [Ви, с.25-27, 69], установить справедливость конечной формулы

а вычисления по ней реализовать с помощью функций:

Здесь при обращении к рекурсивной функции num1() передаются параметры: количество элементов n, начальное значение искомой суммы sum(0) и номер суммируемого члена k(0). Более эффективно эти вычисления реализуются функциями:

Здесь при обращении к рекурсивной функции num2() первые три параметра имеют тот же самый смысл, что и в num1(), а последний параметр равен значению начального члена формируемой суммы (n!).

Контрольные примеры:

hats1(40)® 300158458444475693321518926221316715906770469041,

hats2(40)® 300158458444475693321518926221316715906770469041.

Home Содержание Схемы ООД Доска объявлений Поиск