Подготовка ребенка* к ЕГЭ по информатике. Часть третья

22.01.19

Разработка - Математика и алгоритмы

Алгоритмы рекурсии, логические задачи. Подготовка к ЕГЭ.

Решение рекурсивных алгоритмов на ЕГЭ

 

Данная тема актуальна в свете того, что ученики часто не понимают, как именно выполняются рекурсивные процедуры, пренебрегают их использованием для решений задач повышенной сложности на ЕГЭ. Поэтому необходимо написать подробный разбор заданий с вариантами решений.

 

Условно можно все задания, относящиеся к рекурсивным алгоритмам на ЕГЭ, можно разделить на три большие группы:

 

  • Алгоритмы, опирающиеся на несколько предыдущих значений ;
  • Вызов рекурсивных процедур;
  • Алгоритмы, опирающиеся на одно предыдущее значение.
     
    1. Алгоритмы, опирающиеся на несколько предыдущих значений

 

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

 

Кроме того, в разделе «Алгоритмы, опирающиеся на несколько предыдущих значений» (исходя из заданий прошлых лет) могут встретиться: числа Трибоначчи, последовательность Люка, последовательность Падована.

 

  1.  

Вызов рекурсивных процедур

 

Источник: Демонстрационная версия ЕГЭ-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, ...}

x2A Чтобы выражение было истинно для любого xN, необходимо, чтобы x ∈ {1, 2, 3, 4, … , 9}. Т.е. A > 81.

 

y2>A т.е. Чтобы выражение было истинно для любого xN, необходимо, чтобы 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

 

Остальные примеры из кодификатора аналогичны вышеуказанным.

 

Вывод

 

Для решения данного задания необходимо хорошо составлять таблицы истинности для различных логических операций, учитывать все условия из текста задания, разбираться в обозначениях логических операций.

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4417    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7462    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8838    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7804    dusha0020    8    

70
Оставьте свое сообщение