Содержание

Главная >> Информатика 11 класс. Босова

§ 9. Структурное программирование

9.3. Рекурсивные алгоритмы

Число, меньшее 20, при заданных начальных условиях и системе команд исполнителя Плюс получить невозможно. Следовательно, при n < 20 К(n) = 0.

Для начального числа 20 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды. Можем записать: К(n) = 1 при n = 20.

Любое число n > 20 может быть получено из чисел n - 1, n - 2 и n - 4 одной из трёх команд, входящих в систему команд исполнителя — «прибавь 1», «прибавь 2» и «прибавь 4» соответственно. При этом каждая программа получения из исходного числа чисел n-1, n-2 и n-4 удлинится на одну команду и будет приводить к числу n. Следовательно, К(n) = К(n - 1) + К(n - 2) + К(n - 4).

Запишем все соотношения, определяющие функцию К(п):

К(n) = 0 при n < 20;

К(n) = 1 при n = 20;

К(n) = К(n - 1) + К(n - 2) + К(n - 4) при n > 20.

Заполним по этой формуле таблицу для всех значений л от 20 до 30:

Итак, существует 169 различных программ, с помощью которых исполнитель Плюс может преобразовать число 20 в 30.

Любой объект, который частично определяется через самого себя, называется рекурсивным. Нас окружает множество рекурсивных объектов. Приведём примеры только некоторых из них.

1. Матрёшка — русская деревянная игрушка в виде расписной куклы, внутри которой находятся подобные ей куклы меньшего размера.

2. Два зеркала, поставленные друг напротив друга, — в них образуются два коридора из затухающих отражений. Это, например, можно наблюдать в спальном железнодорожном вагоне.

<<< К началу