Россия, Москва
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Была в сети 15.06.2018 17:26
Федотова Галина Владимировна
преподаватель информатики и информационных технологий
61 год
20 368
1 165 
Местоположение
Специализация
Методика решения задач на определение результата рекурсивного алгоритма
Категория:
Информатика
16.10.2016 17:18
Просмотр содержимого документа
«Методика решения задач на определение результата рекурсивного алгоритма»
Рекурсивные алгоритмы. Решение задач ЕГЭ
В программировании рекурсивным, называется алгоритм, который вызывает сам себя.
Примеры рекурсивных алгоритмов:
Решение задач 1 типа
Задача 1.1
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 1), при n 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
Решение:
F(5) = F(4) * 6
F(4) = F(3) * 5
F(3) = F(2) * 4
F(2) = F(1) * 3 = 1 * 3 = 3
F(3) = 3 * 4 = 12
F(4) = 12 * 5 = 60
F(5) = 60 * 6 = 360
Ответ: 360
Задача 1.2
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1 (1)
F(n) = F(n-2)*(n-1), при n 2 (2)
Чему равно значение функции F(7)? В ответе запишите только целое число.
Решение:
F(7) = F(5) * 6
F(5) = F(3) * 4
F(3) = F(1) * 2 = 1 * 2 = 2
Далее подставляем значение F(3) и получаем значение F(5):
F(5) = F(3) * 4 = 2 * 4 = 8
Далее подставляем значение F(5) и получаем значение F(7):
F(7) = F(5) * 6 = 8 * 6 = 48
Ответ: 48.
Решение задач 2 типа
Задача 2.1
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n 0 then begin
F(n-3);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
Решение:
Сначала составим рекуррентную формулу, обозначив количество звездочек F(n).
Из программы видно, что
при nF(n) = 1 (1)
при n0, F(n) = 1 + F(n-3) + F(n div 2) (2)
n div 2 – это целочисленное деление n на 2
Далее делаем расчеты по формулам:
Так как 70, то расчет делаем по формуле (2), подставляя n=7
F(7) = 1 + F(7-3) + F(7 div 2) = 1 + F(4) + F(3)
Нам пока неизвестны F(4) и F(3). Запишем формулы для нахождения их значений.
Так как 40 и 30, то расчетs делаем по формуле (2), подставляя n=4 и n=3, соответственно
F(4) = 1 + F(4-3) + F(4 div 2) = 1 + F(1) + F(2)
F(3) = 1 + F(3-3) + F(3 div 2) = 1 + F(0) + F(1)
F(0) = 1 по формуле (1), а F(1) и F(2) найдем по формуле (2)
F(2) = 1 + F(2-3) + F(2 div 2) = 1 + F(-1) + F(1)
F(1) = 1 + F(1-3) + F(1 div 2) = 1 + F(-2) + F(0)
F(-2) = 1, F(-1) = 1 и F(0) = 1 по формуле (1)
Теперь, подставив значения F(-2) и F(0) получим F(1)
F(1) = 1 + 1 + 1 = 3
Далее значения F(1) и F(-1) подставим в формулу F(2):
F(2) = 1 + 1 + 3 = 5
Далее аналогично получаем значения F(3) и F(4):
F(4) = 1 + F(1) + F(2) = 1 + 3 + 5 = 9
F(3) = 1 + F(0) + F(1) = 1 + 1 + 3 = 5
Далее подставим F(3) и F(4) в формулу F(7):
F(7) = 1 + F(4) + F(3) = 1 + 9 + 5 = 15
Ответ: 15.
Задача 2.2
Задан рекурсивный алгоритм:
procedure F(n: integer);
begin
if n 2 then begin
writeln('*');
F(n-2);
F(n-1);
F(n div 2);
end;
writeln('*');
end;
Сколько символов «*» будет напечатано при вызове F(6)?
Решение:
Сначала составим рекуррентную формулу, обозначив количество звездочек F(n).
Из программы видно, что
при n
при n2, F(n) = 1 + F(n-2) + F(n div 2) + 1
Используя рекуррентные соотношения, получим:
F(6) = 1+F(4)+F(5)+F(3)+1
F(5) = 1+F(3)+F(4)+F(2)+1
F(4) = 1+F(2)+F(3)+F(2)+1
F(3) = 1+F(1)+F(2)+F(1)+1 = 1+1+1+1+1 = 5
Далее будем подставлять полученные значения F(n) в заданные соотношения:
F(4) = 1+1+5+1+1 = 9
F(5) = 1+5+9+1+1 = 17
F(6) = 1+9+17+5+1 = 33
Ответ: 33.
Решение задач 3 типа
Задача 3.1
Задан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
Решение:
Сначала составим рекуррентную формулу, обозначив сумму чисел S(n).
Из программы видно, что
при n=6, S(n) = n
при n
Используя рекуррентные соотношения, получим:
S(2) = 2+S(4)+S(6)
S(4) = 4+S(6)+S(12) = 4 + 6 + 12 = 22
Далее будем подставлять полученные значения S(n) в заданные соотношения:
S(2) = 2 + 22 + 6 = 30
Ответ: 30
Задача 3.2
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n
writeln(n);
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
Решение:
Сначала составим рекуррентную формулу, обозначив сумму чисел S(n).
Из программы видно, что
при n=6, S(n) = n (1)
при n
Используя рекуррентные соотношения, получим:
S(2) = 2*2 + S(4) + S(6)
S(4) = 2*4 + S(6) + S(12)
По формуле (1) видно, что значения S(6) = 6, S(12) = 12
S(4) = 8 + 6 + 12 = 26
Далее найдем значение S(2):
S(2) = 4 + 26 + 6 = 36
Ответ: 36.
Решение задач 4 типа
Задача 4.1
Задан рекурсивный алгоритм:
function F(n: integer): integer;
begin
if n 2 then
F := F(n - 1) + F(n - 2)
else
F := n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?
Решение:
Сначала составим рекуррентную формулу.
Из программы видно, что
при n2, F(n) = F(n-1) + F(n-2) (1)
при nF(n) = n (2)
Так как 52, то используем соотношение (1)
F(5) = F(5-1) + F(5-2) = F(4) + F(3)
Далее, используя соотношение (1) получим:
F(4) = F(4-1) + F(4-2) = F(3) + F(2)
F(3) = F(3-1) + F(3-2) = F(2) + F(1)
Далее, используя соотношение (2) получим:
F(2) = 2, F(1) = 1
Подставив значения F(2) и F(1), получим:
F(3) = F(2) + F(1) = 2 + 1 = 3
F(4) = F(3) + F(2) = 3 + 2 = 5
F(5) = F(4) + F(3) = 5 + 3 = 8
Ответ: 8.
Задача 4.1
Дан рекурсивный алгоритм:
function F(n: integer): integer;
begin
if n 1 then
F:= 2*n + F(n-3) + F(n-2)
else
F:= n + 5;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?
Решение:
Сначала составим рекуррентную формулу.
Из программы видно, что
при n1, F(n) = 2*n + F(n-3) + F(n-2) (1)
при nF(n) = n + 5 (2)
Так как 61, то используем соотношение (1)
F(6) = 2*6 + F(3) + F(4)
Так как 41, то используем соотношение (1)
F(4) = 2*4 + F(1) + F(2)
Так как 1=1, то используем соотношение (2) и получаем F(1) = 1 + 5 = 6
Тогда F(4) = 8 + 6 + F(2)
Так как 21, то используем соотношение (1)
F(2) = 2*2 + F(-1) + F(0)
Так как -1
F(0) = 0 + 5 = 5
F(-1) = -1 + 5 = 4
Подставляем эти значения в соотношение для F(2) и получаем:
F(2) = 4 + 4 + 5 = 13
F(4) = 8 + 6 + 13 = 27
Далее находим значение F(3):
Так как 31, то используем соотношение (1)
F(3) = 2*3 + F(0) + F(1) = 6 + 5 + 6 = 17
Далее полученные значения F(3) и F(4) подставляем в соотношение F(6) и получаем:
F(6) = 2*6 + F(3) + F(4) = 12 + 17 + 27 = 56
Ответ: 56
Задачи взяты с сайта К.Полякова http://kpolyakov.spb.ru (Задачи для тренировки)
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
Полезное для учителя
Реализация образовательных программ осуществляется с применением исключительно электронного обучения и ДОТ
