Конвейер
Back Home Up Next

адача 8. Дана последовательность a с элементами из множества {0,1}. Проводятся следующие действия. Если a имеет вид 1,0,1,… , то она укорачивается на первые три элемента. В противном случае начальный элемент последовательности переносится в её конец. Указанные действия повторяются до тех пор, пока имеется возможность укоротить текущую последовательность. Требуется составить рекурсивную программу, имитирующую эти действия и возвращающую по исходной последовательности a результирующую последовательность b или сообщение, что b - пустое множество.

Решение. Удаление из a первых трех элементов и перемещение начального элемента в конец a назовем соответственно d-операцией и m-операцией. В постановке задачи фактически уже описана основная идея рекурсивного алгоритма её решения. После совершения и d-операции, и m-операции мы снова должны решать исходную задачу для вновь полученной последовательности. В этом и состоит суть декомпозиции. Уточнений требует лишь правило завершения вычислений, то есть выделение рекурсивной базы. Ясно, что к базе следует отнести все последовательности длины 1 и 2, а также пустую последовательность. Но этим база не будет исчерпана. В неё должна входить, например, последовательность 1, 1, 1, 0, 0, 0. Как же описать всю базу? Проще всего это сделать динамически. Если в процессе требуемых в постановке задачи преобразований последовательности a длины n (n³ 3) n раз подряд была выполнена m-операция (без d-операций), то мы снова получим a . Это означает, что дальнейшие преобразования a будут совершаться по циклу, укоротить эту последовательность уже нельзя, и мы должны отнести её к базе.

Именно эти идеи и реализуются рекурсивной функцией jus(a ,k). Начальное значение вспомогательного параметра k равно нулю и увеличивается на единицу при каждой m-операции. При совершении каждой d-операции значение k снова становится равным нулю. Этим обеспечивается механизм отслеживания элементов базы - последовательностей длины n, для которых подряд n раз совершалась m-операция.

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

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