Задание 11
ТЕМА 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
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу