Решения заданий ФИПИ ЕГЭ по информатике: «Основы программирования» — с ответами

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

Ниже на пяти языках программирования записан один и тот же рекурсивный алгоритм F. Если n > 0, алгоритм сначала вызывает F(n - 1), затем выводит n, а после этого вызывает F(n - 2). Определите…

1. 1
   При n ≤ 0 условие не выполняется, поэтому вызов ничего не выводит.$$F(n)=\varnothing\text{ при }n\leq 0$$
2. 2
   Для вызова F(1) сначала выполняется F(0), затем выводится 1, после чего выполняется F(-1).$$F(1)\to 1$$

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

Рекурсивный вывод чисел

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

1. 1
   При вызове $F(7)$ сначала выполняется $F(5)$, затем $F(2)$, после чего выводится $7$.$$F(7) \to F(5) \to F(3) \to F(1),\ F(1),\ 3,\ F(1),\ 5,\ F(2),\ 7$$
2. 2
   Вызов $F(1)$ не выполняет дальнейших положительных рекурсивных вызовов и выводит $1$. Поэтому вызов $F(3)$ выводит $113$.$$F(3) \to 1,1,3$$

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

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

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

1. 1
   Используем рекуррентное соотношение для соседних значений функции.$$F(n)-F(n-1)=n$$
2. 2
   Представим искомую разность как сумму трёх последовательных разностей.$$F(2024)-F(2021)=2024+2023+2022$$

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

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

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

1. 1
   Начальные значения: $F(1)=F(2)=1$.
2. 2
   Последовательно применяем рекуррентные формулы. Для последних значений получаем:$$F(29)=421,\quad F(30)=450,\quad F(31)=481,\quad F(32)=512$$

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

Рекурсивный вывод чисел

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

1. 1
   Функция сначала выводит значение аргумента, а затем при $n \geq 6$ вызывает себя для $n-1$ и $n-3$.$$F(n)=n,F(n-1),F(n-3)\quad\text{при }n\geq 6$$
2. 2
   Разбираем вызов $F(6)$: сначала выводится 6, затем выполняются $F(5)$ и $F(3)$.$$F(6)=653$$

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

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

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

1. 1
   Начинаем вычисление с базового значения:$$F(1)=1$$
2. 2
   Для каждого следующего натурального числа применяем соответствующую ветвь рекурсивного определения: при чётном аргументе прибавляем значение аргумента к предыдущему значению функции, при нечётном аргументе умножаем значение функции с…

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

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

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

1. 1
   Для аргумента $21$ рекурсия завершается на $2025$: $21+3\cdot 668=2025$. Поэтому$$F(21)=2025+(24+27+\ldots+2025)$$
2. 2
   В сумме $668$ членов. Сумма арифметической прогрессии равна$$24+27+\ldots+2025=\frac{24+2025}{2}\cdot 668=684366$$

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

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

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

1. 1
   При каждом вызове с $n > 2$ сначала выводится значение $n$.$$F(7) \rightarrow 7$$
2. 2
   Затем сначала полностью выполняется рекурсивный вызов $F(n-1)$. Последовательность первого углубления: $7, 6, 5, 4, 3$.

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

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

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

1. 1
   Для первых двух натуральных значений выполняется первое условие:$$F(1)=1,\quad F(2)=1$$
2. 2
   Далее значения функции вычисляются последовательно: для чётных аргументов применяется разность двух предыдущих значений, для нечётных — удвоенное предыдущее значение минус значение двумя шагами ранее.$$F(n)=\begin{cases}F(n-2)-F(n-1),&n\text{ чётно},\\2F(n-1)-F(n-2),&n\text{ нечётно}\end{cases}$$

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

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

Ниже записан рекурсивный алгоритм $F$. При выполнении вызова $F(8)$ определите последовательность чисел, которые будут напечатаны на экране.

1. 1
   При $n \leq 0$ функция ничего не выводит. При положительном $n$ сначала выполняется $F(n-4)$, затем $F(n \mathbin{//} 2)$, и только после этого выводится $n$.
2. 2
   Разберём вызов $F(1)$: оба рекурсивных вызова завершаются без вывода, затем печатается $1$.$$F(1) \to 1$$

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

Рекурсивный вывод чисел

Ниже на пяти языках программирования записан рекурсивный алгоритм F. Если n > 0, алгоритм выводит число n, затем вызывает F при целочисленном делении n на 3, а после этого вызывает F(n − 2)…

1. 1
   При вызове F(7) сначала выводится 7. Затем выполняются вызовы F(7 div 3) = F(2) и F(7 − 2) = F(5).$$F(7) \to 7,\ F(2),\ F(5)$$
2. 2
   Вызов F(2) выводит 2 и выполняет F(0), после чего рекурсия прекращается.$$F(2) \to 2,\ F(0),\ F(0)$$

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

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

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

1. 1
   Из рекуррентного соотношения следует, что значения функции последовательно выражаются через предыдущие значения.$$F(n)=n\times F(n-1)$$
2. 2
   Выражаем значения $F(2024)$ и $F(2023)$ через $F(2022)$.$$F(2024)=2024\times 2023\times F(2022),\quad F(2023)=2023\times F(2022)$$

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

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

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G. Функция F(n) при $n > 0$ вызывает G(n − 1). Функция G(n) печатает символ «звёздочка», а при $n > 1$ вызывает…

1. 1
   Вызов F(n) при $n > 0$ передаёт управление функции G(n − 1). Функция G всегда печатает одну звёздочку.$$f(n) = 1 + f(n - 4), \quad n > 2$$
2. 2
   После вызова F(18) цепочка рекурсивных вызовов имеет аргументы:$$18 \to 14 \to 10 \to 6 \to 2$$

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

Рекурсивный вызов функций

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

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

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

Рекурсивный вывод чисел

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

1. 1
   Вызов $F(7)$ сначала вызывает $F(4)$, затем $F(3)$, после чего выводит $7$.$$F(7) = F(4), F(3), 7$$
2. 2
   Для вызова $F(1)$ оба последующих вызова имеют неположительные аргументы, поэтому выводится только $1$.$$F(1) = 1$$

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

Рекурсивный вывод чисел

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

1. 1
   При $n \leq 0$ функция ничего не выводит. Поэтому $F(1)$ сначала вызывает $F(-1)$ и $F(0)$, а затем выводит $1$.$$F(1)=1$$
2. 2
   Вызов $F(2)$ сначала выполняет $F(0)$, затем $F(1)$ и после этого выводит $2$.$$F(2)=1\,2=12$$

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

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

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

1. 1
   При вызове $F(n)$, если $n>0$, выполняется вызов $G(n-1)$. Функция $G$ печатает одну звёздочку и при аргументе больше 1 вызывает $F(n-3)$ относительно исходного аргумента $F$.$$F(n)\to G(n-1)\to F(n-3)$$
2. 2
   Последовательность вызовов функций $F$ имеет вид:$$F(13)\to F(10)\to F(7)\to F(4)\to F(1)$$

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

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

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

1. 1
   Из рекуррентного соотношения следует, что разность соседних значений функции равна $n-2$:$$F(n)-F(n-1)=n-2$$
2. 2
   Разложим искомую разность на две разности соседних значений:$$F(2024)-F(2022)=[F(2024)-F(2023)]+[F(2023)-F(2022)]$$

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

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

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

1. 1
   Последовательно раскроем рекуррентную формулу для четырёх переходов от $8563$ к $8567$.$$F(8567)-F(8563)=(8567-1)+(8566-1)+(8565-1)+(8564-1)$$
2. 2
   Складываем полученные слагаемые.$$8566+8565+8564+8563=34258$$

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

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

1. 1
   Так как $1<3$ и $2<3$, имеем базовые значения:$$F(1)=F(2)=1$$
2. 2
   Последовательно применяем рекуррентные соотношения. Для нечётных значений:$$F(33)=F(31)+2\cdot33-2=545,\quad F(35)=F(33)+2\cdot35-2=613$$

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