|
|||
F(n) = 1 при n ≤2; F(n) = F(n -1) + 2 × F(n -2) при n> 2.Стр 1 из 2Следующая ⇒ Задание 16 часть 1
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n + 1 при n ≤ 2;
F(n) = 2 · F(n − 1) + F(n − 2) при n > 2.
Чему равно значение функции F(4)? В ответе запишите только натуральное число. Решение Рекурсия - это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта. Для того, чтобы задать рекурсию, необходимо описать: - условие остановки рекурсии (базовый случай); - рекуррентную формулу. В программировании если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия - основной прием программирования). Классическим примером рекурсивного алгоритма является описание вычисления факториала: где F(n-1)=(n-1)! В нашем случае последовательно находим:
F(1) = 2; F(2) =3; F(3) = 6 + 2 = 8; F(4) = 16 + 3 = 19;
Таким образом, ответ F(4) = 19.
Еще примеры подобных заданий Пример 1. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими рекуррентными соотношениями: F(n) = 1 при n = 1; F(n) = F(n − 1) · n при n ≥ 2. Чему равно значение функции F(6)? В ответе запишите только натуральное число. Решение: Последовательно найдём значения функции от базового случая F(1) до искомого значения F(6): F(1) = 1 F(2) = 2 F(3) = 6 F(4) = 24 F(5) = 120 F(6) = 720 Ответ: 720 Пример 2. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n ≤ 2; F(n) = F(n -1) + 2 × F(n -2) при n> 2.
|
|||
|