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

Авторadmin / Опубликовано4 комментария

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

Назад
К оглавлению
Далее
16-е задание: «Вычисление рекуррентных выражений»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 9 минут.
  
Проверяемые элементы содержания: Вычисление рекуррентных выражений
До ЕГЭ 2021 года — это было задание № 11 ЕГЭ
Рекомендации по выполнению:

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

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

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

ФГБНУ "Федеральный институт педагогических измерений"

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

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

  • Процедура (функция)– это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
    • Предназначена для:
  • выполнения одинаковых действий в различных местах одной и той же программы;
  • разбивки программы (или другой процедуры или функции) на подзадачи для улучшения читаемости кода;
    • Особенности программирования процедур (функций):
  • подпрограммы располагаются всегда выше основной программы:

    • процедура

  • сначала составляется заголовок процедуры или функции, в котором перечисляются формальные параметры, они обозначаются идентификаторами, как переменные (т.к. формальные параметры могут меняться, также как переменные):
    • 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.
    		 
    var x,y:integer;
function Sum(x,y:integer): integer; 
begin
{3. Суммируем два числа и присваиваем 
значение функции:}
  Sum:=x+y;
end;
begin
// 1. запрашиваем два числа
 readln(x,y);
{2. передаем запрошенные числа 
в функцию и выводим результат:} 
 write (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
    • рекуррентную формулу (обычно, вызов самой себя с измененным параметром): 
      • row(n-1)

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

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

    Плейлист видеоразборов задания на YouTube:
    Задание демонстрационного варианта 2022 года ФИПИ

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

    16_1:

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

    F(1) = 1
F(n) = F(n–1) * (n + 2), при n > 1

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

    ✍ Решение:
    ✎ Решение с использованием программирования:
    PascalABC.NET (решение №1):

    1
2
3
4
5
6
7
8
9
10
11

    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.

    PascalABC.NET (решение №2):

    1
2
3
4
5
6
7

    function F(n:integer):integer:=
 n=1 ? 1
 :  F(n-1) * (n+2);
 
begin
  print(F(5))
end.

    Питон:

    1
2
3
4
5
6

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

    C++:

    1

     

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

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

    Результат: 840

    16_2:

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

    F(0) = 1, F(1) = 1
F(n) = 2 * F(n–1) + F(n-2), при n > 1

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

    ✍ Решение:
    ✎ Решение с использованием программирования:
    PascalABC.NET (решение №2):

    1
2
3
4
5
6
7
8

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

    ✎ Решение 1. Теоретическое (метод решения с начала к концу):

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

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

    • Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 6:
      • F(6) = 2*F(5) + F(4)
    • Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(2) (F(1) и F(0) известны из условия задачи). Получим:
      • F(6) = 2*F(5) + F(4)
       F(5) = 2*F(4) + F(3)
              F(4) = 2*F(3) + F(2)
                     F(3) = 2*F(2) + F(1)
                              F(2) = 2*F(1) + F(0) = 2*1+1 = 3
                                        1       1
    • Теперь с конца к началу перепишем все получившиеся значения функций:
      • F(6) = 2*F(5) + F(4) = 2*41 + 17 = 99
       F(5) = 2*F(4) + F(3) + 2*17+7 = 41 ↑
              F(4) = 2*F(3) + F(2) = 2*7+3 = 17 ↑
                     F(3) = 2*F(2) + F(1) = 2*3+1 = 7 ↑
                              F(2) = 2*F(1) + F(0) = 2*1+1 = 3 ↑  
                                        1       1

    Результат: 99

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

    📹 YouTube здесь

    16_10:

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

    F(1) = 1; G(1) = 1;
F(n) = F(n–1) – G(n–1), 
G(n) = F(n–1) + 2*G(n–1), при n >= 2

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

      
    Типовые задания для тренировки

    ✍ Решение:
    ✎ Решение с использованием программирования:
    PascalABC.NET:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

    ✎ Решение теоретическое:

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

F(2) = F(1) – G(1) = 1 - 1 = 0
G(2) = F(1) + 2*G(1) = 1 + 2 = 3
F(3) = F(2) – G(2) = 0 - 3 = -3
G(3) = F(2) + 2*G(2) = 0 + 6 = 6
F(4) = F(3) – G(3) = -3 - 6 = -9 
G(4) = F(3) + 2*G(3) = -3 + 12 = 9
F(5) = F(4) – G(4) = -9 - 9 = -18
G(5) = F(4) + 2*G(4) = -9 + 18 = 9
    • Итого:
      • F(5)/G(5) = -18/9 = -2

    Ответ: -2

    16_13:

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

    F(1) = 1; G(1) = 1;
F(n) = F(n–1) + 3·G(n–1), при n >=2 
G(n) = F(n–1) - 2·G(n–1), при n >=2

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

    ✍ Решение:
    ✎ Решение с использованием программирования:
    PascalABC.NET:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    function F(n: integer): integer; forward;
function G(n: integer): integer; forward;
 
function F(n: integer): integer;
begin
  if n = 1 then
    F := 1  // или result := 1
  else if n >= 2 then
    F := F(n - 1) + 3 * G(n - 1) 
    // или result := F(n - 1) + 3 * G(n - 1)
end;
 
function G(n: integer): integer;
begin
  if n = 1 then
    G := 1  // или result := 1
  else if n >= 2 then
    G := F(n - 1) - 2 * G(n - 1)
    // или result := 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.

    Питон:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    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)

    C++:

    1

     

    Результат: 46

    С каким аргументом?

    16_14:

    Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 3200000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

    Pascal:

    procedure F
    ( n: integer );
begin
  writeln(n-5);
  if n > 1 then begin
    writeln(n+8);
    F(n-2);
    F(n-3);
  end;
end;
    		 Python:

    def F( n ):
  print(n-5)
  if n > 1:
    print(n+8)
    F(n-2)
    F(n-3)
    С++:

    void F( int n )
{
  cout << n-5 << endl;
  if( n > 1 ) {
    cout << n+8 << endl;
    F(n-2);
    F(n-3);
    }
}
    ✍ Решение:
    ✎ Решение с использованием программирования:
    PascalABC.NET:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    var   l := new List<integer>;
 
procedure F(n: integer);
begin
  l.Add(n-5);
  if n > 1 then begin
    l.Add(n +8);
    F(n - 2);
    F(n - 3);
  end;
end;
 
begin
  for var n := 1 to 100 do
  begin
    f(n);
    if l.Sum > 3200000 then
    begin
      print(n, l.sum);
      break;
    end;
    l.Clear; // Обязательно!!!
  end;
end.

    Питон:

    1

     

    C++:

    1

     

    Результат: 46 3267851

    16_8:

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    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;
    ✍ Решение:
      ✎ Решение с использованием программирования:
      Подобные задания потеряли смысл после введения компьютерного ЕГЭ. Однако, при большом количестве чисел имеет смысл ввести сумматор для вычисления суммы данных чисел:
      PascalABC.NET:

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

      procedure F(n: integer); forward;
procedure G(n: integer); forward;
var sum:=0; // сумматор
procedure F(n: integer);
begin
  writeln(n);
  sum+=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); 
  sum+=n; // добавляем число в сумматор
  if n > 0 then F(n);
end;
begin
  F(17);
  print('sum =',sum)
end.

    Результат: 6

    Смотрите подробное аналитическое решение:

    📹 YouTube здесь

    📹 Видеорешение на RuTube здесь (аналитическое)

    Задания прошлых лет для тренировки

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

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

    1
2
3
4
5
6
7

    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
    		 Python:

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

    int F(int a);
int F(int a) {
  if (a > 0)
    return F(a - 1) * a;
  else
    return 1;
}

      

    ✍ Решение:
      ✎ Решение с использованием программирования:
      Подобные задания потеряли смысл после введения компьютерного ЕГЭ. Решение очевидно и просто:
      PascalABC.NET:

      1
2
3
4
5
6
7
8
9
10

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

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

    • Если аргумент функции, т.е. a, равен единице, то функция возвращает в программу значение 1, иначе вызывается функция с аргументом a — 1 и результат этой функции умножается на a.
    • Это рекурсивный алгоритм вычисления факториала числа. Чтобы удостовериться в этом, выполним трассировку функции с аргументом = 6:
      • F(6):
6 > 0, то F(5)*6
F(5):
5 > 0, то F(4)*5
F(4):
4 > 0, то F(3)*4
F(3):
3 > 0, то F(2)*3
F(2):
2 > 0, то F(1)*2
F(1): 
1 > 0, то F(0)*1
F(0):
0 > 0 - нет, то F(0) = 1

Теперь подставляем значения, двигаясь вверх по прописанному алгоритму:
F(1)= F(0)*1 = 1*1 = 1
F(2)= F(1)*2 = 1*2 = 2
F(3)= F(2)*3 = 2*3 = 6
F(4)= F(3)*4 = 6*4 = 24
F(5)= F(4)*5 = 24*5 = 120
F(6)= F(5)*6 = 120*6 = 720
    • Т.е. 6! = 720

    Ответ: 720

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    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
    		 Python:

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

    void F(int n) {
  std::cout << "*";
  if (n > 10) {
    F(n - 2);
  }
  else {
    G(n);
  }
}
void G(int n) {
  std::cout << "**";
  if (n > 0)
    F(n - 3);
}

      
    Типовые задания для тренировки

    ✍ Решение:

    >

      ✎ Решение с использованием программирования:
      Подобные задания потеряли смысл после введения компьютерного ЕГЭ. Однако, при большом количестве звездочек имеет смысл ввести счетчик для хранения кол-ва звезд:
      PascalABC.NET:

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

      procedure F(n: integer); forward;
procedure G(n: integer); forward;
var k:=0; // объявление глобальной переменной-счетчика 
procedure F(n: integer);
begin
  write('*');
  k+=1; // увеличение счетчика
  if n > 10 then F(n - 2) else G(n);
end;
 
procedure G(n: integer);
begin
  write('**');
  k+=2;// увеличение счетчика
  if n > 0 then F(n - 3);
end;
begin
 f(18);
 print(k) // вывод счетчика
end.

      ✎ Решение теоретическое:

    • Для удобства восприятия задания, выпишем рекуррентные формулы и условия остановки рекурсии для двух процедур:
      • Для F:
*
F(n - 2) при n > 10
G(n) при n <= 10

Для G:
**
F(n - 3) при n > 0

      ✎ Способ 1:

    • Выпишем последовательность вызовов процедур, начиная с указанного в задании F(18):
      • F(18) -> F(16) -> F(14) -> F(12) -> F(10) -> G(10) -> 
F(7) -> G(7) -> F(4) -> G(4) -> F(1) -> G(1) -> F(-2) -> G(-2)
    • Обратим внимание, что независимо от условия процедура F выводит на экран одну *, а процедура G выводит две *. Посчитаем для последовательности вызовов итоговую сумму звездочек: 9F + 5G = 9*1 + 5*2 = 19

      • Результат: 19

      ✎ Способ 2:

    • Рассмотрим пошагово выполнение программы при вызове F(18):
      • 1 шаг: F(18)
       *    F(16)
2 шаг:      *    F(14)
3 шаг:           *    F(12)
4 шаг:                *    F(10)
5 шаг:                     *    G(10)
6 шаг:                          **   F(7)
7 шаг:                                *  G(7)
8 шаг:                                   **  F(4)
9 шаг:                                       *    G(4)
10 шаг:                                           **   F(1)
11 шаг:                                                *   G(1)
12 шаг:                                                    **   F(-2)
13 шаг:                                                         *   G(-2)
14 шаг:                                                             **
    • Посчитаем количество звездочек: 19

    Результат: 19

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

    📹 YouTube здесь

    Видеорешение на RuTube здесь

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

    Паскаль:

    1
2
3
4
5
6
7
8
9

    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
    		 Python:

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

    void F(int n) {
  std::cout << ″*″;
  if (n > 0) {
    F(n - 2);
    F(n / 2);
    F(n / 2);
  }
}
    ✍ Решение:
    • В начале каждого вызова независимо от условия на экран выводится «звездочка». Кроме того, если условие n > 0 истинно, то функция вызывается еще три раза с разными аргументами. Таким образом, каждая функция выводит на экран либо одну звездочку (если условие ложно), либо 4 звездочки если условие истинно.
    • Схематично рассмотрим вызов каждой функции, начиная с функции F(5). Дойдя до F(0), для которой условие будет ложно, будем подставлять полученное количество «звездочек», двигаясь опять к F(5):
      • F(5) = одна '*', F(3), F(2), F(2)
F(3) = одна '*', F(1), F(1), F(1)
F(2) = одна '*', F(0), F(1), F(1)
F(1) = одна '*', F(-1), F(0), F(0)
F(0) = одна '*' = 1  (условие ложно)
F(-1) = одна '*' = 1 (условие ложно)
---
Движение обратно:
F(1) = одна '*', F(-1), F(0), F(0) = 1 + 1 + 1 + 1 = 4 '*'
F(2) = одна '*', F(0), F(1), F(1) = 1 + 1 + 4 + 4 = 10 '*'
F(3) = одна '*', F(1), F(1), F(1) = 1 + 4 + 4 + 4 = 13 '*'
F(5) = одна '*', F(3), F(2), F(2) = 1 + 13 + 10 + 10 = 34 '*'

    Ответ: 34

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    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
    		 Python:

    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)
    С++:

    void F(int n) {
  std::cout << n << endl;
  if (n % 2 == 0) {
    F(n / 2);
  }
  else {
    G((n - 1) / 2) ;
  }
}
void G(int n) {
  std::cout << n << endl;
  if (n > 0)
    F(n);
}

      
    Типовые задания для тренировки

    ✍ Решение:
      ✎ Решение с использованием программирования:
      Подобные задания потеряли смысл после введения компьютерного ЕГЭ. Однако, при большом количестве чисел имеет смысл ввести сумматор для вычисления суммы данных чисел:
      PascalABC.NET:

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

      procedure F(n: integer); forward;
procedure G(n: integer); forward;
var sum:=0; // сумматор
procedure F(n: integer);
begin
  writeln(n);
  sum+=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); 
  sum+=n; // добавляем число в сумматор
  if n > 0 then F(n);
end;
begin
  F(17);
  print('sum =',sum)
end.

      ✎ Решение теоретическое:

    • Для удобства восприятия задания, выпишем рекуррентные формулы и условия остановки рекурсии для двух процедур:
      • Для F:
n
F(n div 2) при n - четное (n mod 2 = 0)
G((n - 1) div 2) при n - нечетное

Для G:
n
F(n) при n > 0
    • Выпишем последовательность вызовов процедур, начиная с указанного в задании F(17).
    • Обратим внимание, что независимо от условия как процедура F выводит на экран n, так и процедура G выводит n.
      • F(17) -> n - нечетное, G(8) вывод 17
G(8) -> F(8)                вывод 8
F(8) -> n - четное, F(4)    вывод 8
F(4) -> n - четное, F(2)    вывод 4 
F(2) -> n - четное, F(1)    вывод 2
F(1) -> n - нечетное, G(0)  вывод 1
G(0)                        вывод 0
    • Сумма:
      • 17 + 8 + 8 + 4 + 2 + 1 + 0 = 40

    Результат: 40

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    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
    		 Python:

    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
    С++:

    int F(int n);
int G(int n);
int F(int n) {
  if (n > 2)
    return F(n - 1) + G(n - 2);
  else
    return n;
}
int G(int n) {
  if (n > 2)
    return G(n - 1) + F(n - 2);
  else
    return n + 1;
}

      
    Типовые задания для тренировки

    ✍ Решение:
    Результат: 17

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

    📹 YouTube здесь

    Видеорешение на RuTube здесь

    Не актуально для компьютерного ЕГЭ

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

    16_6: Демоверсия ЕГЭ 2018 информатика:

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

    1
2
3
4
5
6
7
8
9

    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
    		 Python:

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

    void F(int n){
  if (n > 0){
    std::cout <<n;
    F(n - 3);
    F(n / 3);
  }
}

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

    Похожие задания для тренировки

    ✍ Решение:
      Рассмотрим алгоритм:

    • В данном фрагменте программы рекурсивная процедура вызывает саму себя дважды.
    • Благодаря условию, находящемуся в процедуре (if n > 0 — условие остановки рекурсии), обеспечивается выход из рекурсии и не происходит «зацикливания».
    • Выполнение процедур закончится, когда в каждой из вызванных процедур выполнятся по две внутренние процедуры, и условие if n > 0 перестанет работать (т.е. когда параметр процедуры n станет <= 0).
    • div — целочисленное деление, т.е., например:
      • 5 div 2 = 2
1 div 2 = 0
    • Отобразим пошагово выполнение каждой процедуры, двигаясь сверху вниз и оставляя отступы слева с каждым новым шагом. В каждой строке будем отображать порядковый номер шага. Под вызовом каждой процедуры разместим именно те действия, которые происходят в данной процедуре:
      •    F(9)
1: 9  F(6)    (9 - 3 = 6)
2:     6   F(3)    (6 - 3 = 3)
3:          3    F(0)    (3 - 3 = 0, условие не работает)
4:         F(1)  (3 div 3 = 1)
5:          1    F(-2)    (1 - 3 = -2, условие не работает)
6:         F(0)    (1 div 3 = 0, условие не работает)
7:    F(2) (6 div 3 = 2)
8:     2   F(-1)    (2 - 3 = -1, условие не работает)
9:    F(0)    (2 div 3 = 0, условие не работает)
10:F(3)  (9 div 3 = 3)
11:3  F(0)     (3 - 3 = 0, условие не работает) 
12:F(1)  (3 div 3 = 1)   
13: 1   F(-2)     (1 - 3 = -2, условие не работает)
    • Выделены те числа, которые выводятся на экран. Подчеркнуты те процедуры, в которых условие не работает, соответственно, ничего на экран не выводится.
    • Перепишем по порядку все выводимые на экран числа сверху вниз: 9631231

    Результат: 9631231

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

    2 способ:
    📹 YouTube здесь
    📹 Видеорешение на RuTube здесь

    16_7:

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

    1
2
3
4
5
6
7
8
9

    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
    		 Python:

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

    void F(int n){
  if (n > 1){
    std::cout <<n;
    F(n / 10);
    F(n - 40);
  }
}
    ✍ Решение:
      Разберем алгоритм программы:

    • В данном фрагменте программы рекурсивная процедура F вызывает саму себя дважды.
    • В процедуре находится условие if n > 1 — условие остановки рекурсии, благодаря которому обеспечивается выход из рекурсии и не происходит «зацикливания».
    • Выполнение фрагмента программы закончится, когда в каждой из вызванных процедур выполнятся по две внутренние процедуры, и условие if n > 1 перестанет работать (т.е. когда параметр процедуры n станет <= 1).
    • div — целочисленное деление, т.е., например:
      • 5 div 3 = 1
1 div 3 = 0
    • Выполним трассировку кода процедуры: двигаться будем пошагово сверху вниз, оставляя отступы слева с каждым новым шагом. В каждой строке будем отображать порядковый номер шага. Под вызовом каждой процедуры разместим именно те действия, которые происходят в данной процедуре:
      •    F(130) 130  
1: ➥  F(13) (130 div 10 = 13) 13
2:           ➥ F(1) условие не работает! 1 ≤ 0
3:           ➥ F(-27) условие не работает! -27 ≤ 0
4: ➥  F(90) (130 - 40 = 90) 90        
5:           ➥ F(9) (90 div 10 = 9) 9
6:                    ➥ F(0) условие не работает! 0 ≤ 0
7:                    ➥ F(-31) условие не работает! -31 ≤ 0
8:           ➥  F(50) (90 - 40 = 50) 50
9:                     ➥  F(5) (50 div 10 = 5) 5
10:                              ➥ F(0) условие не работает! 0 ≤ 0
11:                              ➥ F(-35) условие не работает! -35 ≤ 0
12:                    ➥  F(10) (50 - 40 = 10) 10
13:                              ➥ F(1) условие не работает! 1 ≤ 0
14:                              ➥ F(-30) условие не работает! -30 ≤ 0
    • Выделены красным цветом те числа, которые выводятся на экран. Подчеркнуты те процедуры, в которых условие не работает, соответственно, ничего на экран не выводится.
    • Перепишем сверху вниз все выводимые на экран числа: 1301390950510

    Результат: 1301390950510

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

    📹 Видеорешение на RuTube здесь

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    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
    		 Python:

    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)
    		 С++:

    void G(int n);
void F(int n) {
	if (n > 2) {
	  std::cout << n;
	  F(n - 1);
	  G(n - 2);		
	  }
	else
	  std::cout << n+2;
}
void G(int n) {
	std::cout << n;
	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).
    • Рассмотрим последовательно алгоритм работы функций, нумеруя вызовы функций. Для удобства будем делать отступы для каждой функции. Таким образом, для вызова каждой функции должно быть два внутренних вызова:
      • F(5) = 5 (на экране)
1) F(n - 1), т.е. F(4)
    F(4) = 4(на экране)
    1) F(n - 1), т.е. F(3)
           F(3) = 3(на экране)
           1) F(n - 1), т.е. F(2)
                  F(2) = n + 2 = 4 (на экране) (блок else)
           2) G(n - 2), т.е. G(1)
   	          G(1) = 1 (на экране)
    2) G(n - 2), т.е. G(2)
	   G(2) = 2 (на экране)
2) G(n - 2), т.е. G(3)
    G(3) = 3 (на экране)
    1)G(n - 1), т.е. G(2)
           G(2) = 2 (на экране)
    2) F(n - 2), т.е. F(1)
           F(1) = n + 2 = 3 (на экране) (блок else)
    • Перепишем сверху вниз все цифры, выведенные на экран:
      • 543412323

    Ответ: 543412323

    Назад
    К оглавлению
    Далее

4 комментария для “ЕГЭ информатика 16 задание разбор”

  1. В последней задаче результат с опечаткой. Там должно быть : 1301390950510
    Обратите внимание)

  2. Спасибо за разбор задач!
    Но как составить решить такую?
    75) Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
    F(n) = n, при n  1,
    F(n) = 1 + F(n / 2), когда n > 1 и чётное,
    F(n) = 1 + F(n + 2) , когда n > 1 и нечётное.
    Назовите минимальное значение n, для которого F(n) = 16.
    Как написать для нее программу. У меня она постоянно выдает ошибку времени выполнения.

  3. Большой спасибо за такой простой разбор и объяснение интересных задач!!!

Обсуждение закрыто.