ЕГЭ · информатика · номер 16 · решения с ответами

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

Все задачи задания 16 из открытого банка ФИПИ с готовым ответом и началом разбора. Полное решение по шагам и официальный ключ — по ссылкам в карточке.

Задания без решений

решений с ответами

тем в номере

страниц списка

01ФИПИ 097227№ 16ПовышеннаяДинамическое программирование

Вычисление рекурсивной функции

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n<3$; $F(n)=F(n-2)-F(n-1)$, если $n>2$ и при этом $n$ чётно…

1
Так как $1<3$ и $2<3$, начальные значения равны:$$F(1)=F(2)=1$$
2
Последовательно применяем соответствующую формулу для чётных и нечётных значений $n$:$$F(3)=1,\ F(4)=0,\ F(5)=-1,\ F(6)=1,\ F(7)=3,\ F(8)=-2$$

Ещё 3 шага — в полном решении

Решение полностьюОтвет Решать самому5 шагов в разборе

02ФИПИ 0C9871№ 16ПовышеннаяАлгоритмы и исполнители

Рекурсивная функция и факториал

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=nF(n-1)$, если $n>1$. Чему равно значение выражения…

1
Из рекуррентного соотношения следует, что $F(n)=n!$.$$F(2024)=2024\cdot2023\cdot F(2022),\quad F(2023)=2023\cdot F(2022)$$
2
Подставим эти выражения в исходную формулу и сократим на $F(2022)$:$$\frac{F(2024)/4+F(2023)}{F(2022)}=\frac{2024\cdot2023\cdot F(2022)/4+2023\cdot F(2022)}{F(2022)}=2023\left(\frac{2024}{4}+1\right)$$

Ещё 1 шаг — в полном решении

Решение полностьюОтвет Решать самому3 шага в разборе

03ФИПИ 0D4EB5№ 16ПовышеннаяАлгоритмы и исполнители

Подсчёт рекурсивных вызовов

Ниже приведены две рекурсивные функции F и G. Функция G печатает символ «звёздочка» и при выполнении условия вызывает функцию F. Сколько символов «звёздочка» будет напечатано на экране при…

1
Вызов F(14) удовлетворяет условию $n > 0$, поэтому выполняется вызов G(11).$$F(14) \to G(11)$$
2
Функция G(11) печатает одну «звёздочку» и вызывает F(10), так как $11 > 1$.$$G(11) \to F(10)$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

04ФИПИ 0E2072№ 16ПовышеннаяОсновы программирования

Разность значений рекурсивной функции

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=3$ при $n<3$; $F(n)=n+F(n-2)$, если $n\geqslant 3$. Чему равно значение выражения…

1
Из рекуррентного соотношения следует, что $F(n)-F(n-2)=n$.$$F(n)-F(n-2)=n$$
2
Раскроем разность значений функции через два последовательных шага:$$F(2022)-F(2018)=\bigl(F(2022)-F(2020)\bigr)+\bigl(F(2020)-F(2018)\bigr)$$

Ещё 1 шаг — в полном решении

Решение полностьюОтвет Решать самому3 шага в разборе

05ФИПИ 1644D5№ 16ПовышеннаяДинамическое программирование

Рекурсивная функция F(18)

1
По условию $F(n)=1$ при $n<3$, поэтому $F(1)=1$ и $F(2)=1$.$$F(1)=F(2)=1$$
2
Последовательно применяем соответствующую формулу для чётных и нечётных значений $n$.$$F(3)=1,\ F(4)=0,\ F(5)=-1,\ F(6)=1,\ F(7)=3,\ F(8)=-2,\ F(9)=-7$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

06ФИПИ 1A2ED5№ 16ПовышеннаяОсновы программирования

Рекуррентная функция F

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=2nF(n-1)$, если $n>1$. Чему равно значение выражения…

1
По рекуррентному соотношению выразим $F(2024)$ через $F(2023)$:$$F(2024)=2\cdot2024\cdot F(2023)=4048F(2023)$$
2
Тогда числитель выражения равен:$$F(2024)-3F(2023)=(4048-3)F(2023)=4045F(2023)$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

07ФИПИ 1ADC01№ 16ПовышеннаяОсновы программирования

Разность значений рекурсивной функции

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=n$ при $n\geq 2025$; $F(n)=2n+F(n+2)$, если $n<2025$. Чему равно значение выражения…

1
Раскроем рекурсивные формулы до достижения аргумента, при котором функция задаётся напрямую:$$F(82)=2\cdot82+2\cdot84+\ldots+2\cdot2024+F(2026)$$
2
Для нечётного аргумента получаем:$$F(81)=2\cdot81+2\cdot83+\ldots+2\cdot2023+F(2025)$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

08ФИПИ 1C457A№ 16ПовышеннаяОсновы программирования

Вывод рекурсивной функции

Ниже на пяти языках программирования записан рекурсивный алгоритм F. При вызове функции сначала выводится значение параметра n. Если n >= 4, затем выполняются вызовы F(n - 3) и F(n - 1) именно в…

1
При вызове $F(6)$ сначала выводится 6. Так как $6 \ge 4$, выполняется вызов $F(3)$, который выводит 3 и завершается.$$F(6): 6 \to F(3): 3$$
2
Затем выполняется вызов $F(5)$, который выводит 5. Он вызывает $F(2)$ и $F(4)$ в этом порядке.$$F(5): 5 \to F(2): 2,\ F(4): 4$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

09ФИПИ 1CCE58№ 16ПовышеннаяОсновы программирования

Рекурсивный алгоритм F

Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. Во всех вариантах алгоритм эквивалентен следующему: функция $F(n)$ выводит число $n$. Если $n \ge 3$, сначала вызывается…

1
Вызов $F(5)$ сразу выводит число 5. Затем выполняется вызов $F(2)$.$$5$$
2
Вызов $F(2)$ выводит 2 и не порождает новых вызовов, так как $2 < 3$.$$52$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

10ФИПИ 1D337E№ 16ПовышеннаяОсновы программирования

Вывод рекурсивной функции

Ниже на пяти языках программирования записана рекурсивная функция (процедура) F. Функция сначала выводит значение n, затем, если n >= 3, вызывает F(n - 1), а после этого — F(n - 3). Что выведет…

1
Вызов $F(5)$ сначала выводит цифру 5, затем вызывает $F(4)$ и $F(2)$.$$F(5) \to 5, F(4), F(2)$$
2
Раскрываем вызов $F(4)$: выводится 4, затем выполняются $F(3)$ и $F(1)$.$$F(4) \to 4, F(3), F(1)$$

Ещё 3 шага — в полном решении

Решение полностьюОтвет Решать самому5 шагов в разборе

11ФИПИ 26ADAF№ 16ПовышеннаяОсновы программирования

Вывод рекурсивной функции

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

1
При вызове $F(3)$ сначала выводится число 3. Затем выполняются вызовы $F(1)$, $F(2)$ и $F(1)$.$$F(3) \to 3, F(1), F(2), F(1)$$
2
Вызов $F(1)$ выводит только число 1, так как условие $n \geq 2$ не выполняется.$$F(1) \to 1$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

12ФИПИ 2778CC№ 16ПовышеннаяОсновы программирования

Рекурсивный подсчёт звёздочек

Ниже приведены две рекурсивные функции F и G. Функция F(n) вызывает G(n - 2), если n > 0. Функция G(n) печатает символ «*» и вызывает F(n - 1), если n > 1. Сколько символов «звёздочка» будет…

1
Вызов $F(12)$ удовлетворяет условию $n > 0$, поэтому вызывается $G(10)$.$$F(12) \to G(10)$$
2
Функция $G(10)$ печатает одну звёздочку и вызывает $F(9)$.$$G(10) \to F(9)$$

Ещё 3 шага — в полном решении

Решение полностьюОтвет Решать самому5 шагов в разборе

13ФИПИ 28131C№ 16ПовышеннаяАлгоритмы и исполнители

Трассировка рекурсивной функции

Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. Во всех вариантах алгоритм выводит значение параметра $n$, а затем, если $n \ge 4$, вызывает функцию для $n - 1$ и для целой…

1
При каждом входе в функцию сначала выводится её параметр $n$.$$F(6) \Rightarrow 6$$
2
Для значений $n \ge 4$ сначала выполняется вызов с параметром $n-1$, затем — с параметром $n \mathbin{//} 2$.$$6 \to 5 \to 4 \to 3 \to 2 \to 2 \to 3$$

Ещё 1 шаг — в полном решении

Решение полностьюОтвет Решать самому3 шага в разборе

14ФИПИ 2C19E5№ 16ПовышеннаяДинамическое программирование

Вычисление рекурсивной функции

Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\times F(n-1)+2$, если $n>1$ и при этом $n$…

1
Начальные значения: $F(0)=0$ и $F(1)=0$. Последовательно применяем заданные правила.
2
Для чётного аргумента $30$ используется второе слагаемое $n/2$: $F(30)=30/2+F(29)$.

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

15ФИПИ 2D68B6№ 16ПовышеннаяОсновы программирования

Порядок рекурсивных вызовов

Ниже на пяти языках программирования записан рекурсивный алгоритм F. При вызове F(n), если n > 2, сначала выводится значение n, затем вызываются F(n / 2) с целочисленным делением и F(n − 1).

1
При вызове F(7) выводится число 7. Затем выполняется F(7 // 2) = F(3).$$7$$
2
Вызов F(3) выводит 3, а вызовы F(1) и F(2) ничего не выводят, поскольку их аргументы не больше 2.$$7\,3$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

16ФИПИ 2E8064№ 16ПовышеннаяОсновы программирования

Рекурсивная функция с шагом два

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=n$ при $n\geq 2025$; $F(n)=n+F(n+2)$, если $n<2025$. Чему равно значение выражения…

1
Раскроем рекурсию для первого значения:$$F(2022)=2022+F(2024)=2022+2024+F(2026)$$
2
Поскольку $2026\geq 2025$, значение функции в этой точке вычисляется по первому соотношению:$$F(2026)=2026$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

17ФИПИ 35359C№ 16ПовышеннаяОсновы программирования

Порядок рекурсивных вызовов

Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. При $n > 0$ алгоритм сначала выводит значение $n$, затем вызывает $F(n - 4)$, а после этого — $F(\lfloor n/2 \rfloor)$…

1
При вызове $F(8)$ сначала выводится число $8$. Затем выполняются вызовы $F(4)$ и $F(4)$.$$F(8) \to 8,\ F(4),\ F(4)$$
2
Первый вызов $F(4)$ выводит $4$, затем вызывает $F(0)$ и $F(2)$. Вызов $F(0)$ ничего не выводит, а $F(2)$ выводит $2$, после чего вызывает $F(-2)$ и $F(1)$.

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

18ФИПИ 367944№ 16ПовышеннаяОсновы программирования

Рекурсивная функция F

Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями: $F(n)=1$ при $n=1$; $F(n)=2 \times n \times F(n-1)$, если $n>1$. Чему равно значение…

1
По рекуррентной формуле выразим соседние значения функции через $F(5324)$.$$F(5325)=2 \cdot 5325 \cdot F(5324)$$
2
Тогда значение функции при аргументе $5326$ равно:$$F(5326)=2 \cdot 5326 \cdot F(5325)=2 \cdot 5326 \cdot 2 \cdot 5325 \cdot F(5324)$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

19ФИПИ 3989D3№ 16ПовышеннаяОсновы программирования

Вывод рекурсивной функции

Ниже на пяти языках программирования записан один и тот же рекурсивный алгоритм $F$. Функция сначала выводит значение параметра $n$, а затем, если $n \geq 7$, вызывает $F(n - 1)$ и $F(n - 3)$ именно…

1
Вызов $F(9)$ сразу выводит число 9, затем вызывает $F(8)$ и $F(6)$.$$F(9) \Rightarrow 9,\ F(8),\ F(6)$$
2
Вызов $F(8)$ выводит 8. Затем $F(7)$ выводит 7 и вызывает $F(6)$, который выводит 6. После этого вызывается $F(5)$, который выводит 5.$$F(8) \Rightarrow 8\,7\,6\,5$$

Ещё 1 шаг — в полном решении

Решение полностьюОтвет Решать самому3 шага в разборе

20ФИПИ 39F802№ 16ПовышеннаяАлгоритмы и исполнители

Рекурсивная функция F

1
Запишем значения функции, используя рекуррентную формулу.$$F(2024)=2\cdot2024\cdot F(2023)=4048F(2023),\quad F(2023)=2\cdot2023\cdot F(2022)=4046F(2022)$$
2
Подставим выражение для $F(2024)$ в числитель.$$F(2024)-F(2023)=(4048-1)F(2023)=4047F(2023)$$

Ещё 2 шага — в полном решении

Решение полностьюОтвет Решать самому4 шага в разборе

Те же задачи без решений, с фильтрами по сложности и типу ответа, — список заданий. Другой предмет — в каталоге.