Решение рекурсивных алгоритмов на ЕГЭ
Данная тема актуальна в свете того, что ученики часто не понимают, как именно выполняются рекурсивные процедуры, пренебрегают их использованием для решений задач повышенной сложности на ЕГЭ. Поэтому необходимо написать подробный разбор заданий с вариантами решений.
Условно можно все задания, относящиеся к рекурсивным алгоритмам на ЕГЭ, можно разделить на три большие группы:
- Алгоритмы, опирающиеся на несколько предыдущих значений ;
- Вызов рекурсивных процедур;
- Алгоритмы, опирающиеся на одно предыдущее значение.
- Алгоритмы, опирающиеся на несколько предыдущих значений
1.1. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 2
F(2) = 5
F(n) = F(n–1) * (n+1) + F(n–2) * (n + 2) , при n >2
Чему равно значение функции F(4)?
В ответе запишите только натуральное число.
Удобнее всего данное задание решать составлением таблицы значений.
|
Значение аргумента x функции F(x) |
Значение функции F(x) |
|
1 |
2 |
|
2 |
5 |
|
3 |
F(3) = F(2)*4 + F(1)*5 = 30 |
|
4 |
F(4) = F(3)*5 + F(2)*6 = 180 |
Ответ: 180
1.2. Последовательность чисел Фибоначчи задается рекуррентным соотношением:
Function(1) = 1
Function(2) = 1
Function(x) = Function(x–2) + Function(x–1), при x >2, где x – натуральное число.
Чему равно шестое число в последовательности Фибоначчи?
В ответе запишите только натуральное число.
Вероятно, проще прописать числа данной последовательности, не обращаясь к значениям функции, т. к. последовательность Фибоначчи – довольно известный числовой ряд.
|
№ числа |
1 |
2 |
3 |
4 |
5 |
6 |
|
Значение |
1 |
1 |
2 |
3 |
5 |
8 |
Ответ: 8
Кроме того, в разделе «Алгоритмы, опирающиеся на несколько предыдущих значений» (исходя из заданий прошлых лет) могут встретиться: числа Трибоначчи, последовательность Люка, последовательность Падована.
Вызов рекурсивных процедур
Источник: Демонстрационная версия ЕГЭ-2015 по информатике
2.1. Ниже записан рекурсивный алгоритм F.
procedure F(n: integer);
begin
writeln(n);
if n < 5 then
begin
F(n + 1);
F(n + 3)
end
end
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Разберемся, что делает этот алгоритм. Удобно рисовать дерево, и потом подниматься с нижних ветвей вверх, но для статьи будет предложена подробная таблица.
|
Шаг |
Что происходит |
|
1 |
Печатает на экране 1, вызывает F(2) |
|
2 |
Печатает на экране 2, вызывает F(3) |
|
3 |
Печатает на экране 3, вызывает F(4) |
|
4 |
Печатает на экране 4, вызывает F(5) |
|
5 |
Печатает на экране 5, передает управление F(4) |
|
6 |
F(4) вызывает F(7) |
|
7 |
Печатает на экране 7, передает управление F(3) |
|
8 |
F(3) вызывает F(6) |
|
9 |
Печатает на экране 6, передает управление F(2) |
|
10 |
F(2) вызывает F(5) |
|
11 |
Печатает на экране 5, передает управление F(1) |
|
12 |
F(1) вызывает F(4) |
|
13 |
Печатает на экране 4, вызывает F(5) |
|
14 |
Печатает на экране 5, передает управление F(4) |
|
15 |
F(4) вызывает F(7) |
|
17 |
Печатает на экране 7, процедура закончена |
Анализируем данные и выбираем, какие числа были напечатаны:
Sum = 1 + 2 + 3 + 4 + 5 + 7 + 6 + 5 + 4 + 5 + 7 = 49
Ответ: 49
Источник: Досрочная волна. ЕГЭ 5.05.2015
2.2. Ниже записаны две рекурсивные функции (процедуры): F и G.
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
begin
if n > 0 then
G(n - 1);
end;
procedure G(n: integer);
begin
writeln('*');
if n > 1 then
F(n - 2);
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Заметим, что печать происходит лишь при вызове процедуры G(n).
|
Шаг |
Что происходит |
|
1 |
F(11) вызывает G(10), печатается звездочка |
|
2 |
G(10) вызывает F(8) |
|
3 |
F(8) вызывает G(7), печатается звездочка |
|
4 |
G(7) вызывает F(5) |
|
5 |
F(5) вызывает G(4), печатается звездочка |
|
6 |
G(4) вызывает F(2) |
|
7 |
F(2) вызывает G(1), печатается звездочка |
После аргумент n перестает отвечать заданному условию.
Ответ: 4
2.3. Ниже записана рекурсивная функция (процедура) F.
procedure Function(n: integer);
begin
write(n);
if n > 2 then
begin
Function(n − 2);
Function(n − 1);
Function(n − 1)
end
end;
Что выведет программа при вызове F(3)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).
Рассмотрим, как выполняется данный алгоритм:
|
Шаг |
Что происходит |
|
1 |
Печатается 3, F(3) вызывает F(1) |
|
2 |
Печатается 1, F(1) передает управление F(2) |
|
3 |
Печатается 2, F(2) передает управление F(2) |
|
4 |
Печатается 2, условие перестает выполняться |
Ответ: 3122
Источник: Демонстрационная версия ЕГЭ-2018 по информатике
2.4 Ниже на записан рекурсивный алгоритм F.
procedure F(n: integer);
begin
if n > 0 then begin
writeln(n);
F(n - 3);
F(n div 3)
end
end;
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Рассмотрим, как выполняется данный алгоритм:
|
Шаг |
Что происходит |
|
1 |
Печатается 9, F(9) вызывает F(6) |
|
2 |
Печатается 6, F(6) вызывает F(3) |
|
3 |
Печатается 3, F(3) вызывает F(0) |
|
4 |
F(0) передает управление F(1) |
|
5 |
Печатается 1, F(1) вызывает F(-2) |
|
6 |
F(-2) передает управление F(2) |
|
9 |
Печатается 2, F(2) вызывает F(-1) и F(0) |
|
10 |
F(0) передает управление F(3) |
|
11 |
Печатается 3, F(3) вызывает F(0) и F(1) |
|
11 |
Печатается 1 |
Ответ: 9631231
Довольно любопытное задание можно найти на другом сайте по подготовке к ЕГЭ (ссылка: http://kpolyakov.spb.ru/):
2.5 При выполнении вызова F(8) на экран было выведено математическое выражение. Вычислите его значение.
procedure G(n: integer);forward;
procedure F(n: integer);
begin
write('2');
if n > 0 then begin
write('*');
G(n - 1);
end;
end;
procedure G(n: integer);
begin
write('3');
if n > 1 then
F(n - 2);
end;
Рассмотрим, как выполняется данный алгоритм:
|
Шаг |
Что происходит |
|
1 |
Печатается 2, Печатается *, F(8) вызывает G(7) |
|
2 |
Печатается 3, G(7) вызывает F(5) |
|
3 |
Печатается 2, Печатается *, F(5) вызывает G(4) |
|
4 |
Печатается 3, G(4) вызывает F(2) |
|
5 |
Печатается 2, Печатается *, F(2) вызывает G(1) |
|
6 |
Печатается 3 |
Получившееся выражение: 2*32*32*3 = 6144
Ответ: 6144
Алгоритмы, опирающиеся на одно предыдущее значение
Источник: Демонстрационная версия ЕГЭ-2013 по информатике
3.1. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * n, при n >1
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Очевидно, что требуется найти факториал от 5. Таблицу факториалов до 6 нужно знать.
|
№ числа |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
Значение |
1 |
1 |
2 |
6 |
24 |
120 |
720 |
Ответ: 120
3.2 Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
Function(1) = 1
Function(n) = Function(x–1) + 2n–1 , если x> 1.
Чему равно значение функции Function(9)?
В ответе запишите только натуральное число.
Можно заметить, что F(9) = 2^9 – 1 = 511.
Ответ: 511
3.3. Алгоритм вычисления значения функции Function(x), где x — натуральное число, задан следующими соотношениями:
Function(1) = 4;
Function(x) = F(x − 1) + x если x>1
Чему равно значение функции Function(36)? В ответе запишите только натуральное число.
Легко заметить, что данная функция представляет собой сумму арифметической прогрессии Function(x) = Function(1) + d(x-1), где Function(1) = 4, d = 1. Sum Function(x) = (Function(1) + Function(x))/2*x = (Function(1) + Function(1) + d(x-1))/2*x = 774
Ответ: 774
3.4. Алгоритм вычисления значения функции Function(x) и G(x), где x – натуральное число, задан следующими соотношениями:
Function(1) = 1
Function(x) = 2 * G(x–1) + 5 * x, при x >1
G(1) = 1
G(x) = F(n–1) + 2 * x, при x >1
Чему равно значение функции F(4) + G(4)?
В ответе запишите только натуральное число.
Составим таблицу значений для F(x) и для G(x):
|
Значение аргумента x функции F(x) |
Значение функции Function(x) |
|
2 |
Function(2) = 2*G(1) + 10 = 12 |
|
3 |
Function(3) = 2*G(2) + 15 = 25 |
|
4 |
Function(4) = 2*G(3) + 20 = 56 |
|
Значение аргумента x функции G(x) |
Значение функции G(x) |
|
2 |
G(2) = Function(1) + 4 = 5 |
|
3 |
G(3) = Function(2) + 6 = 18 |
|
4 |
G(4) = Function(3) + 8 = 33 |
Function(4) + G(4) = 56 + 33 = 89
Нет никакой сложности в том, чтобы составить таблицу значений и для двух функций.
Ответ: 89
Таким образом, для этого типа заданий характерны арифметические, геометрические или произвольные последовательности. Рекомендуется выучить формулы n-члена для арифметической и геометрической последовательностей, формулы суммы n-членов последовательностей.
Вывод
Исходя из всего вышесказанного, можно сделать вывод, что наиболее трудные задачи – из 2 подраздела (Вызов рекурсивных процедур), т. к. необходимо очень хорошо понимать, как работает программа, простая математика не поможет. Необходимо делать упор на отработку именно этого типа задач. Рекомендуется составлять программы самостоятельно с использованием рекурсивных функций, проводить отладку со входом в подпрограмму. Можно расписывать дерево решений, составлять таблицы.
Преобразование логических высказываний на ЕГЭ
Предлагаю также рассмотреть преобразование логических высказываний (задание 18), как второе наиболее сложное для учеников в первой части экзамена.
Их также можно условно разделить на 2 группы:
- Числовые отрезки;
Логические высказывания.
1. Числовые отрезки
Перечислим операции в порядке убывания приоритетов (выполнения) :
Символ ¬ обозначает инверсию
Символ & обозначает конъюнкцию
Символ | обозначает дизъюнкцию
Символ → обозначает импликацию
Прочие операции:
Символ ≡ обозначает эквивалентость
Символ ∈ обозначает принадлежность
Символ ≠ обозначает неэквивалентность
1.1. На числовой прямой даны два отрезка: P = [7, 39] и Q = [18, 26]. Укажите наибольшую возможную длину промежутка A, для которого формула
((x ∈ P) ≡ (x ∈ Q)) → ¬(x ∈ A)
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Преобразуем данное логическое выражение в соответствие с законами логики:
|
Начальное выражение |
Конечное выражение |
|
((x ∈ P) ≡ (x ∈ Q)) → ¬(x ∈ A) = 1 |
((x ∈ P) ≠ (x ∈ Q)) | ¬(x ∈ A) = 1 |
Для того, чтобы данное выражение всегда принимало значение истина, необходимо и достаточно, чтобы A∈[7; 18) или A∈(26; 39]. В таком случае, наибольшая длина отрезка A = 39-26 = 13.
Ответ: 13
Все остальные задания аналогичны этому.
2. Логические высказывания
2. 1. Элементами множества А являются натуральные числа. Известно, что выражение
(x ∈ {5, 8, 13, 32}) → (((x ∈ {7, 9, 13}) ∧ ¬(x ∈ A)) → ¬(x ∈ {5, 8, 13, 32}))
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее наименьшее возможное количество элементов во множестве A.
Преобразуем данное логическое выражение в соответствие с законами логики:
|
Начальное выражение |
Конечное выражение |
| (x ∈ {5, 8, 13, 32}) → (((x ∈ {7, 9, 13}) ∧ ¬(x ∈ A)) → ¬(x ∈ {5, 8, 13, 32})) = 1 |
(x ∉ {7, 9, 13}) | (x ∉ {{5, 8, 13, 32}) | (x ∈ A) = 1 |
(x ∉ {5, 8, 13, 32}) | (x ∉ {7, 9, 13}) = 1 при всех значениях x, кроме 13 (оно исключено из обоих множеств). Таким образом, множество A должно содержать как минимум 13. Т.е. один элемент.
Ответ: 1
Источник: Досрочная волна. ЕГЭ 5.05.2015
2.2. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Преобразуем данное логическое выражение в соответствие с законами логики:
|
Начальное выражение |
Конечное выражение |
|
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4)) = 1 |
ДЕЛ(x, А) | ¬(ДЕЛ(x, 6) | ¬ДЕЛ(x, 4) = 1 |
Рассмотрим логическое выражение (ДЕЛ(x, 6) | ДЕЛ(x, 4) = 1. В соответствие с формулами де Моргана ¬(¬(ДЕЛ(x, 6) | ¬ДЕЛ(x, 4)) = ДЕЛ(x, 6) & ДЕЛ(x, 4). Таким образом, выражение ДЕЛ(x, А) | (ДЕЛ(x, 6) | ДЕЛ(x, 4) будет тождественно истинно, если A содержит в себе число из множества чисел кратных 4 и 6 одновременно (т. е. A∈{12, 24, 36, 48…}). Допустим, что наибольшее натуральное число A = 24. Проверим значение выражения при x=12:
ДЕЛ(12, 24) | ¬(ДЕЛ(12, 6) | ¬ДЕЛ(12, 4) = 1
ЛОЖЬ ИЛИ ЛОЖЬ ИЛИ ЛОЖЬ = ИСТИНА, что неверно. Аналогично со всеми A>12. Они будут давать ложное значение при x кратных 12.
Таким образом, наибольшее A = 12.
Ответ: 12
Тренировочная работа по информатике, 11 класс 26.11.2016 Вариант ИН10204
2.3. Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&19 = 0 → x&А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Преобразуем данное логическое выражение в соответствие с законами логики:
|
Начальное выражение |
Конечное выражение |
|
x&25 ≠ 0 → (x&19 = 0 → x&А ≠ 0) |
x&25 = 0 | x&19 ≠ 0 | x&A ≠ 0 |
Рассмотрим конечное выражение в двоичной записи. Биты считать справа налево с 0:
|
|
x&11001 = 0 |
x&19 ≠ 0 |
x&A ≠ 0 |
|
Истинно, если |
0 бит = 0 или 3 бит = 0 или 4 бит = 0 |
0 бит = 1 1 бит = 1 4 бит = 1 |
A должно охватывать те x, которые не охватывают остальные выражения. Следовательно:
1 бит = 0 2 бит = 0 или 1 3 бит = 1 |
Т.к. нам надо найти минимальное число A, то 2 бит равен 0, а 3 — 1. Число A = 8.
Ответ: 8
Источник: Демонстрационная версия ЕГЭ-2018 по информатике
2.4. Для какого наибольшего целого числа А формула
((x ≤ 9) →(x ⋅ x ≤ A)) & ((y ⋅ y ≤ A) → (y ≤ 9))
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
|
Начальное выражение |
Конечное выражение |
|
((x ≤ 9) → (x ⋅ x ≤ A)) X96; ((y ⋅ y ≤ A) → (y ≤ 9)) = 1 |
((x>9) | (x2 ≤ A)) & ((y2>A) | (y ≤ 9)) = 1 |
Конъюнкция истинна, если истинно каждое из выражений:
x>9 т.е. x ∈ {10, 11, 12, 13, 14, ...}
x2 ≤ A Чтобы выражение было истинно для любого x∈N, необходимо, чтобы x ∈ {1, 2, 3, 4, … , 9}. Т.е. A > 81.
y2>A т.е. Чтобы выражение было истинно для любого x∈N, необходимо, чтобы y ∈ {10, 11, 12, 13, 14, …}. Следовательно, Amax < 100.
y ≤ 9 т.е. y ∈ {1, 2, 3, 4, 5, …, 9}
Получаем A ∈ (81;100). Amax = 99.
Ответ: 99
Источник: Досрочная волна. ЕГЭ-2018, Вариант 1
2.5. Для какого наименьшего целого неотрицательного числа А выражение
(y + 2x < A) ∨ (x > 30) ∨ (y > 20)
тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y?
Для того, чтобы выражение выполнялось для всех x и y, в выражении
y + 2x < A, x ∈ [1; 30], y ∈ [1; 20]
Рассмотрим случай при xmax и ymax:
20 + 2*30 < A
80 < A, следовательно, A ∈ [81; +∞). Amin = 81.
Ответ: 81
Остальные примеры из кодификатора аналогичны вышеуказанным.
Вывод
Для решения данного задания необходимо хорошо составлять таблицы истинности для различных логических операций, учитывать все условия из текста задания, разбираться в обозначениях логических операций.
