ЕГЭ информатика 16 задание разбор

ЕГЭ информатика 16 задание разбор

16-е задание: «Вычисление рекуррентных выражений» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 9 минут.

Проверяемые элементы содержания: Вычисление рекуррентных выражений

"Для успешного выполнения этого задания следует аккуратно произвести трассировку предложенной рекурсивной функции"

Типичные ошибки и рекомендации по их предотвращению:

"Крайне важно отслеживать правильность возврата выполнения программы в нужную точку для каждого рекурсивного вызова"

Объяснение темы «Рекурсивные процедуры и функции»

Для начала, разберем некоторые определения.

    Процедура (функция)– это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.

var x,y:integer; < заголовок процедуры с формальными переменными x и y:>procedure Sum(x,y:integer); begin . end; // основная программа begin . end.

var x,y:integer; < заголовок функции с формальными переменными x и y:>function Sum(x,y:integer): integer; begin . end; // основная программа begin . end.

< заголовок процедуры с формальными переменными x и y:>procedure Sum(x,y:integer); begin . end; // основная программа begin Sum(100,200) end.

< заголовок функции с формальными переменными x и y:>function Sum(x,y:integer): integer; begin . end; // основная программа begin write (Sum(100,200)) end.

var x,y:integer; procedure Sum(x,y:integer); begin //3. Выводим сумму двух запрошенных чисел write(x+y); end; begin // 1. запрашиваем два числа readln(x,y); // 2. передаем запрошенные числа в процедуру Sum(x,y) end.

Подробное описание работы с процедурами можно найти, перейдя по ссылке.

procedure row(n:integer); begin if n >=1 then begin write (n, ' '); row(n-1) end; end; begin row(10); end.

Для использования рекурсии, необходимо задать:

    условие остановки рекурсии (обычно, в виде условного оператора):

if n >=1 then begin

Подробное описание работы с рекурсивными процедурами и функциями в Паскале можно найти здесь.

Решение заданий 16 ЕГЭ по информатике

Решение по рекуррентной формуле

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

Чему равна сумма цифр значения F(18)?

✍ Решение:

function F(n: integer): integer; forward; function G(n: integer): integer; forward; function F(n: integer): integer; begin if n = 1 then F := 1 else if n >= 2 then F := F(n - 1) + 3 * G(n - 1) end; function G(n: integer): integer; begin if n = 1 then G := 1 else if n >= 2 then G := F(n - 1) - 2 * G(n - 1) end; begin var res := F(18); var s := 0; while res > 0 do begin s := s + (res mod 10); res := res div 10; end; print(s) end.

def F( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)+3*G(n-1) def G( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)-2*G(n-1) res = F(18) s = 0 while res > 0: s += res%10 res = res // 10 print(s)

Результат: 46

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

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

✍ Решение:

function F(n: integer): integer; begin if n = 1 then F := 1 else if n > 1 then F := F(n - 1) * (n + 2) end; begin print(F(5)) end.

def F( n ): if n == 1: return 1 elif (n > 1): return F(n-1)*(n+2) print (F(5))

✎ Решение методом с конца к началу:

  • Из условия задания мы имеем рекуррентную формулу: F(n–1) * (n + 2) и условие остановки рекурсии: n > 1.
  • Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 5:
  • Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(1) (при котором «сработает» остановка рекурсии). Получим:
  • На F(2) необходимо остановиться, так как действует условие остановки рекурсии: формула работает для n > 1. Также учтем, что по условию F(1) = 1.
  • Теперь с конца к началу перепишем все получившиеся сомножители и перемножим их:

Результат: 840

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

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

✍ Решение:

  • Из условия задания мы имеем рекуррентную формулу: 2 * F(n–1) + F(n-2) и условие остановки рекурсии: n > 1.
  • Из заданной рекуррентной формулы видим, что функция зависит от предыдущей функции (F(n–1)) и от пред-предыдущей функции (F(n-2)).
  • Так как первые два значения заданы (F(0) = 1, F(1) = 1), то можно построить таблицу последующих значений, двигаясь к числу 6: n0123456F(n) 2*F(n – 1)+F(n — 2)112*1+1 =32*3+1 =72*7+3 =172*17+7 =412*41+17 =99
  • Таким образом, получаем, что при вызове функции F(6) результатом будет число 99

✎ Решение 2. Метод решения с конца к началу:

  • Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 6:
  • Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(2) (F(1) и F(0) известны из условия задачи). Получим:
  • Теперь с конца к началу перепишем все получившиеся значения функций:

Результат: 99

Решение данного задания 16 также можно посмотреть в видеоуроке:

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

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

  • Решим задание с вызова функций F(5) и G(5). Будем получать формулы последовательно для F(5), F(4), …, F(1), G(5), G(4), …, G(1). Дойдя до известных значений F(1) = 1 и G(1) = 1, подставим их в полученные формулы:
  • Итого:

Ответ: -2

Что вернет функция. Сколько символов «звездочка». Какова сумма чисел

16_9: ЕГЭ по информатике 2020 задание 1 (Самылкина Н.Н., Синицкая И.В., Соболева В.В., «Тематические тренировочные задания»):

Что вернет функция F, если ее вызвать с аргументом 6?

function f(a:word):longword; begin if a>0 then f := f(a-1)*a; else f:=1; end;

FUNCTION F(a) IF a > 0 THEN F = F(a - 1) * a ELSE F = 1; END IF END FUNCTION

def F(a): if a > 0: return F(a - 1) * a else: return 1

int F(int a); int F(int a)

    Рассмотрим алгоритм функции:

Ответ: 720

16_3: ЕГЭ по информатике 2017 задание 16 (11) ФИПИ вариант 2 (Крылов С.С., Чуркина Т.Е.):

Ниже записаны две рекурсивные функции (процедуры): F и G. Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(18)?

procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin write('*'); if n > 10 then F(n - 2) else G(n); end; procedure G(n: integer); begin write('**'); if n > 0 then F(n - 3); end;

DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) PRINT "*" IF n > 10 THEN F(n - 2) ELSE G(n) END IF END SUB SUB G(n) PRINT "**" IF n > 0 THEN F(n - 3) END IF END SUB

def F(n): print("*") if n > 10: F(n - 2) else: G(n) def G(n): print("**") if n > 0: F(n - 3)

✍ Решение:

  • Для удобства восприятия задания, выпишем рекуррентные формулы и условия остановки рекурсии для двух процедур:

Результат: 19

Результат: 19

Пошаговое решение данного 16 задания ЕГЭ по информатике доступно в видеоуроке:

16_12: Решение задания 16 (Поляков К., вариант 31):

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?

procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n div 2); F(n div 2); end end;

DECLARE SUB F(n) SUB F(n) PRINT '*' IF n > 0 THEN F(n - 2) F(n \ 2) F(n \ 2) END IF END SUB

def F(n): print('*') if n > 0: F(n-2) F(n // 2) F(n // 2)

  • В начале каждого вызова независимо от условия на экран выводится «звездочка». Кроме того, если условие n > 0 истинно, то функция вызывается еще три раза с разными аргументами. Таким образом, каждая функция выводит на экран либо одну звездочку (если условие ложно), либо 4 звездочки если условие истинно.
  • Схематично рассмотрим вызов каждой функции, начиная с функции F(5). Дойдя до F(0), для которой условие будет ложно, будем подставлять полученное количество «звездочек», двигаясь опять к F(5):

Ответ: 34

16_4: ЕГЭ по информатике «Типовые экзаменационные варианты» 2019, ФИПИ, ВАРИАНТ 10 (Крылов С.С., Чуркина Т.Е.):

Ниже записаны две рекурсивные функции (процедуры): F и G. Какова сумма чисел, напечатанных на экране при выполнении вызова F(17)?

procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin writeln(n); if n mod 2 =0 then F(n div 2) else G((n - 1) div 2); end; procedure G(n: integer); begin writeln (n); if n > 0 then F(n); end;

DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) PRINT n IF n MOD 2 = 0 THEN F(n \ 2) ELSE G ( (n - 1) \ 2) END IF END SUB SUB G(n) PRINT n IF n > 0 THEN F(n) END IF END SUB

def F(n): print(n) if n % 2 == 0: F(n // 2) else: G((n - 1) // 2) def G(n): print(n) if n > 0: F(n)

✍ Решение:

  • Для удобства восприятия задания, выпишем рекуррентные формулы и условия остановки рекурсии для двух процедур:
  • Выпишем последовательность вызовов процедур, начиная с указанного в задании F(17).
  • Обратим внимание, что независимо от условия как процедура F выводит на экран n, так и процедура G выводит n.
  • Сумма:

Результат: 40

16_5, Источник: Поляков К, ВАРИАНТ 77

Ниже записаны две рекурсивные функции (процедуры): F и G. Чему будет равно значение, вычисленное при выполнении вызова F(6)?

function F(n: integer):integer; forward; function G(n: integer):integer; forward; function F(n:integer):integer; begin if (n > 2) then F:= F(n - 1) + G(n - 2) else F:= n; end; function G(n:integer):integer; begin if (n > 2)then G:= G(n - 1) + F(n -2) else G:= n+1; end;

FUNCTION F(n) IF n > 2 THEN F = F(n - 1) + G(n - 2) ELSE F = n; END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n - 1) + F(n -2) ELSE G = n+1; END IF END FUNCTION

def F(n): if n > 2: return F(n - 1) + G(n - 2) else: return n def G(n): if n > 2: return G(n - 1) + F(n - 2) else: return n+1

✍ Решение:

Предлагаем посмотреть видеоразбор данного решения:

Все числа, которые будут напечатаны на экране, в том же порядке

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

procedure F(n: integer); begin if n > 0 then begin write(n); F(n - 3); F(n div 3) end end;

SUB F(n) IF n > 0 THEN PRINT n F(n - 3) F(n \ 3) END IF END SUB

def F(n): if n > 0: print(n) F(n - 3) F(n // 3)

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

✍ Решение:

    Рассмотрим алгоритм:

Результат: 9631231

Подробное решение 16 (11) задания демоверсии ЕГЭ 2018 года смотрите на видео:

Ниже записан рекурсивный алгоритм F. Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(130). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

procedure F(n: integer); begin if n > 1 then begin write(n); F(n div 10); F(n - 40) end end;

SUB F(n) IF n > 1 THEN PRINT n F(n \ 10) F(n - 40) END IF END SUB

def F(n): if n > 1: print(n) F(n // 10) F(n - 40)

✍ Решение:

    Разберем алгоритм программы:

Результат: 1301390950510

Предлагаем посмотреть видео разбора задания:

16_11: Решение задания 16 (Поляков К., вариант 135):

Определите, что выведет на экран программа при вызове F(5). Паскаль:

procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin if n > 2 then begin write(n); F(n - 1); G(n - 2); end else write(n+2); end; procedure G(n: integer); begin write(n); if n > 2 then begin G(n - 1); F(n - 2); end; end;

DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 2 THEN PRINT n F(n - 1) G(n - 2) ELSE PRINT n+2 END IF END SUB SUB G(n) PRINT n IF n > 2 THEN G(n - 1) F(n - 2) END IF END SUB

def F(n): if n > 2: print(n, end='') F(n - 1) G(n - 2) else: print(n+2, end='') def G(n): print(n, end='') if n > 2: G(n - 1) F(n - 2)

  • При истинности условия функция F также, как и функция G «запускает» еще две функции: функция F: 1)F(n — 1) и 2)G(n — 2) , а функция G: 1)G(n — 1) и 2)F(n — 2) .
  • Рассмотрим последовательно алгоритм работы функций, нумеруя вызовы функций. Для удобства будем делать отступы для каждой функции. Таким образом, для вызова каждой функции должно быть два внутренних вызова:
  • Перепишем сверху вниз все цифры, выведенные на экран:

Ответ: 543412323

Вызов представленной ниже рекурсивной функции приводит к появлению на экране чисел и точек. С каким минимальным натуральным аргументом а нужно вызвать эту функцию, чтобы в результате на экране появилось 5 точек (не обязательно подряд, между точками могут встречаться числа)? Паскаль:

function gz(a:integer):integer; var p:integer; begin if a<1 then begin gz:=1; exit; end; if a mod 3=0 then begin write('. '); p:=gz(a div 3)+gz(a div 4); end else begin write('.'); p:=gz(a div 4); end; write(p); gz:=2; end;

📎📎📎📎📎📎📎📎📎📎