Ниже записаны две рекурсивные процедуры, F и G:
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
procedure G(n: integer);
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F (11)?
Паскаль, встретив команду F(11), вызывает процедуру F и передает ей параметр n = 11:
в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1
процедура G печатает звездочку и, в случае выполнения условия n > 1, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(7)
в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1
процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(3)
в случае выполнения условия n > 0 выполняется следующая строка: G(n — 1), вызывающая процедуру G после уменьшения n на 1
процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(-1)
получив значение -1 и убедившись, что условие не выполнилось, Паскаль завершает выполнение программы.
А нам остается подсчитать, сколько раз печаталась звездочка. В нашем случае это произошло ровно 3 раз(а)
Итого, правильный ответ: 3
Внимание! Для прокрутки условия на анимации необходимо по нему произвести щелчок левой кнопкой мыши и нажать кнопку "ВНИЗ" или "ВВЕРХ"
Интерактивный тренажер 11 ЕГЭ ДЕМО 2015
на "Рекурсивные алгоритмы"
Если уловие задания видно не полностью, щелкните по нему курсором мыши и нажмите клавишу «вниз» или «вверх»
Примеры заданий и их решений, генерируемых интерактивным тренажером по задачам11 ЕГЭ 2015
Рекурсивные алгоритмы.
Задание №1. Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n = 5 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 5
при n = 5
S(n) = n + S(n+1) + S(n+3)
Прокручиваем цикл сшагом -1 начиная от значения меньшего 5
S(4) = 4 + S(5) + S(7) = 4 + 5 + 7 = 16
S(3) = 3 + S(4)+S(6) = 3 + 16 + 6 = 25
S(2) = 2 + S(3) +S(5) = 2 + 25 + 5 = 32
S(1) = 1 + S(2) + S(4) = 1 + 32 + 16 = 49
таким образом правильный ответ = 49
Воспользуемся данным методом и попробуем решить следующую задачу, не тратя время на комментарии
Задача 2
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n =6
Записываем прокрутку в общем виде
S(5) = 5 + S(7) + S(15)
S(4) = 4 + S(6) + S(12)
S(3) = 3 + S(5) + S(9)
S(2) = 2 + S(4) + S(6)
S(1) = 1 + S(3) + S(3)
из последнего уравнения видим, что нам нужны третье и пятое уравнение, поэтому окончательно получаем:
S(5) = 5 + S(7) + S(15) = 5+7+15 = 27
S(3) = 3 + S(5) + S(9) = 3 + 27 + 9 = 39
S(1) = 1 + S(3) + S(3) = 1 + 39 + 39 = 79
Задание №3 Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
РЕШЕНИЕ:
F(0) = 1, F(1) = 1
1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 — 1) * F(2 — 2) = 1
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 — 1) * F(3 — 2) = 1
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 — 1) * F(4 — 2) = 1
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 — 1) * F(5 — 2) = 1
5) используя заданную рекуррентную формулу, находим, что F(6) = F(6 — 1) * F(6 — 2) = 1
6) используя заданную рекуррентную формулу, находим, что F(7) = F(7 — 1) * F(7 — 2) = 1
7) используя заданную рекуррентную формулу, находим, что F(8) = F(8 — 1) * F(8 — 2) = 1
8) используя заданную рекуррентную формулу, находим, что F(9) = F(9 — 1) * F(9 — 2) = 1
9) используя заданную рекуррентную формулу, находим, что F(10) = F(10 — 1) * F(10 — 2) = 1
10) используя заданную рекуррентную формулу, находим, что F(11) = F(11 — 1) * F(11 — 2) = 1
11) используя заданную рекуррентную формулу, находим, что F(12) = F(12 — 1) * F(12 — 2) = 1
12) используя заданную рекуррентную формулу, находим, что F(13) = F(13 — 1) * F(13 — 2) = 1
13) используя заданную рекуррентную формулу, находим, что F(14) = F(14 — 1) * F(14 — 2) = 1
Ответ: 1
Задание №4. Дан рекурсивный алгоритм:
Чему равно значение функции F(5)? В ответе запишите только натуральное число.
РЕШЕНИЕ:
1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 — 1) * F(2 — 2) + 5 = 6
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 — 1) * F(3 — 2) + 5 = 11
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 — 1) * F(4 — 2) + 5 = 71
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 — 1) * F(5 — 2) + 5 = 786
Ответ: 786
Задание №6. Дан рекурсивный алгоритм:
procedure F(n: integer);begin writeln(n);
if n = 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 6
при n 0 then begin
writeln(‘*’);
F(n-5);
F(n div 2);
F(n div 2);
end
end;
Сколько символов звездочка будет напечатано на экране при выполнении вызова F(8)?
РЕШЕНИЕ:
S(0) = 1
S(1) = 2 + S(1-2) + 2*S(1 div 2) = 2 + 1 + 2 = 5
S(2) = 2 + S(2-2) + 2*S(2 div 2) = 2 + 1 + 10 = 13
S(3) = 2 + S(3-2) + 2*S(3 div 2) = 2 + 1 + 10 = 13
S(4) = 2 + S(4-2) + 2*S(4 div 2) = 2 + 1 + 26 = 29
S(5) = 2 + S(5-2) + 2*S(5 div 2) = 2 + 1 + 26 = 29
S(6) = 2 + S(6-2) + 2*S(6 div 2) = 2 + 5 + 26 = 33
S(7) = 2 + S(7-2) + 2*S(7 div 2) = 2 + 13 + 26 = 41
S(8) = 2 + S(8-2) + 2*S(8 div 2) = 2 + 13 + 58 = 73
Таким образом правильный ответ = 73
Задание №8. Дан рекурсивный алгоритм:
procedure F(n: integer);
begin writeln(‘*’);
if n > 0 then begin
writeln(‘*’);
F(n-8);
F(n div 2);
end
end;
Сколько символов звездочка будет напечатано на экране при выполнении вызова F(6)?
РЕШЕНИЕ:
S(0) = 1
S(1) = 2 + S(1-2)+S(1 div 2) = 2 + 1 + 1 = 4
S(2) = 2 + S(2-2)+S(2 div 2) = 2 + 1 + 4 = 7
S(3) = 2 + S(3-2)+S(3 div 2) = 2 + 1 + 4 = 7
S(4) = 2 + S(4-2)+S(4 div 2) = 2 + 1 + 7 = 10
S(5) = 2 + S(5-2)+S(5 div 2) = 2 + 1 + 7 = 10
S(6) = 2 + S(6-2)+S(6 div 2) = 2 + 1 + 7 = 10
Таким образом правильный ответ = 10
Задание №9. Алгоритм вычисления значения функции F(n), где n – натуральн ое число, задан следующими соотношениями:
F(0) = 1,
F(1) = 1
F(n) = F(n–1) * F(n — 2) + 5, при n > 1
Чему равно значение функции F(7)? В ответе запишите только натуральное число.
РЕШЕНИЕ:
F(0) = 1,
F(1) = 1
F(2) = F(2 — 1) * F(2 — 2) + 5 = 6
F(3) = F(3 — 1) * F(3 — 2) + 5 = 11
F(4) = F(4 — 1) * F(4 — 2) + 5 = 71
F(5) = F(5 — 1) * F(5 — 2) + 5 = 786
F(6) = F(6 — 1) * F(6 — 2) + 5 = 55811
F(7) = F(7 — 1) * F(7 — 2) + 5 = 43867451
Ответ: 43867451
Задание №10. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
procedure F(n: integer);
F(1) = 1;
G(1) = 1;
F(n) = 8*F(n–1) – 8*G(n–1);
G(n) = F(n–1) + 3*G(n–1), при n >=2
Чему равно значение величины F(5) — G(5)? В ответе запишите только целое число.
РЕШЕНИЕ:
F(1) = 1 : G(1) = 1
F(2) = 8*F(1) — 8*G(1) = 0 : G(2) = F(1) + 3*G(1) = 4
F(3) = 8*F(2) — 8*G(2) = -32 : G(3) = F(2) + 3*G(2) = 12
F(4) = 8*F(3) — 8*G(3) = -352 : G(4) = F(3) + 3*G(3) = 4
F(5) = 8*F(4) — 8*G(4) = -2848 : G(5) = F(4) + 3*G(4) = -340
F[5] — G[5] = -2508
Таким образом правильный ответ = -2508
© Северобайкальск, Russia
Александр Козлов, 2017
лабораторные работы и задачи по программированию и информатике, егэ по информатике
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Паскаль:
procedure F(n: integer); begin if n > 0 then begin write(n); F(n — 3); F(n div 3) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
-
Рассмотрим алгоритм:
Результат: 9631231
Ниже на языке программирования записаны две рекурсивные функции (процедуры): F и G.
procedure F(n:integer); forward; procedure G(n:integer); forward; procedure F (n:integer); begin writeln(‘*’); if n mod 5 = 0 then G(n — 5) else F (n — 3); end; procedure G(n:integer); begin if n > 0 then F (n — 1); end;
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(27)?
-
Разберем алгоритм кода процедуры:
Результат: 9
Ниже на языке программирования записан рекурсивный алгоритм F:
procedure F(n: integer); begin if n > 0 then begin F(n div 4); write(n); F(n — 1); end end;
В качестве ответа укажите последовательность цифр, которая будет напечатана на экране в результате вызова F(5).
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
| Бейсик | Python |
|---|---|
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Первым действием процедура F(1) выведет число 1. Далее процедура F(1) вызовет процедуру F(n + 1), в результате выполнения которой на экране появится число n + 1 = 2. Процедура F(2) вызовет процедуру F(3), которая выведет на экран число 3 и вызовет процедуру F(4), которая выведет на экран число 4 и вызовет F(5), которая выведет на экран число 5.
После этого управление вернётся к процедуре F(4), которая начнёт выполнять следующий шаг своего алгоритма, т. е. обратиться к процедуре F(n + 3) = F(7). Процедура F(7) выведет на экран число 7. Далее управление вернётся к процедуре F(3). Рассуждая аналогично приходим к выводу, что процедура F(3) дополнительно выведет на экран число 6, процедура F(2) — 5.
Последним действием процедуры F(1) будет вызов процедуры F(n + 3) = F(4), которая выведет на экран числа
Таким образом, на экране будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма равна 49.