ТЕМА 11

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

Пример 1

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n + 2 при n ≤ 3;

F(n) = F(n − 2) * F(n − 3) при n> 3.

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

Решение

Последовательно рассчитаем значения функции при n =1, 2, 3, 4, 5, 6, 7. Необходимо учитывать, что при n ≤ 3 функция находится как F(n) = n + 2. При n > 3 функция определяется как F(n) = F(n − 2) * F(n − 3)

F(1) = 3

F(2) = 4

F(3) = 5

F(4) = F(2) * F(1) = 4*3 = 12

F(5) = F(3) * F(2) = 5*4 = 20

F(6) = F(4) * F(3) = 12*5 = 60

F(7) = F(5) * F(4) = 20*12 = 240.

Ответ: 240

Пример 2

Алгоритм вычисления значения функции F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 2

F(n) = 3 * G(n–1) + 2 * n, при n >1

G(1) = 3

G(n) = 2*F(n–1) + 3 * n, при n >1

Чему равно значение функции F(4) - G(4)? В ответе запишите только натуральное число.

Решение

Определим значения функций при n = 2, 3, 4, 5:

F(2) = 3*G(1) + 2*2 = 13

G(2) = 2*F(1) + 3*2 = 10

F(3) = 3*G(2) + 2*3 = 36

G(3) = 2*F(2) + 3*3 = 35

F(4) = 3*G(3) + 2*4 = 113

G(4) = 2*F(3) + 3*4 = 84

Следовательно F(4) - G(4) = 113 – 84 = 29

Ответ: 29

Пример 3

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

В качестве ответа укажите последовательность цифр, которая будет напечатана на экране в результате вызова процедуры F(6). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение

При вызове F(6) условие n > 0 истинно, значит, выполняются команды условного оператора.

Происходит вызов F(6 div 2) = F(3), далее выводится число 6 и вызывается

F(6 - 3) = F(3).

Обозначим это следующим образом: F(6)= F(3) 6 F(3)

При вызове F(3) условие n > 0 истинно, значит происходит вызов F(3 div 2) = F(1), далее выводится число 3 и вызывается F(3-3) = F(0), т.е. F(3) = F(1) 3 F(0)

При n <= 0 процедура ничего на экран не выводит.

При вызове F(1) условие n > 0 истинно, значит происходит вызов F(1 div 2) = F(0), далее выводится число 1 и вызывается F(1-3) = F(-2), т.е. F(1) = F(0) 1 F(-2).

Можно нарисовать дерево вызова процедур:

Следуя порядку вызова процедур, получим комбинацию цифр на экране: 13613

Ответ: 13613

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• ссылка на видеоурок по теме: смотреть

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу