Бесплатный интенсив по информатике
3 огненных вебинара, домашние задания, беседа курса, личный кабинет, связь с преподавателем и
многое другое.
Курс стартует 9 ноября.
Подробнее об интенсиве
Задание 16. Системы счисления. Кодирование чисел. ЕГЭ 2022 по информатике
Средний процент выполнения: 54.9%
Ответом к заданию 16 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
Функция F(n), где n - натуральное число, вычисляется по следующему правилу:
F(n) = n, при n < 4;
F(n) = F(n-3)*3, при n > 3 кратном трём;
F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;
F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.
Чему равно значение функции F(22)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
def f(n):
if n < 4:
return n
elif n % 3 == 0:
return f(n-3)*3
elif n % 3 == 1:
return f(n-1)+7
else:
return f(n-2)+n
print(f(22))
При запуске программа выдаст ответ: 2194
Задача 2
На рисунке на различных языках программирования записан рекурсивный алгоритм F. Определите, сколько чисел будет напечатано на экране при выполнении вызова F(26).
Решение
На рисунке представлена схема выполнения вызова процедуры F(26) в виде дерева.
Согласно алгоритма, вывод чисел на экран осуществляется, когда остаток от деления n на 3 не равен 1.
Количество чисел напечатанных на экране (26, 21, 15, 9, 3) : 5
Задача 3
На рисунке на различных языках программирования записан рекурсивный алгоритм F.
Определите, сколько чисел будет напечатано на экране при выполнении вызова F(6).
Решение
При вызове функции F(6) выполняется подпрограмма, в которой переменная n принимает значение 6. Каждый раз при вызове процедур F(n - 2) и F(n - 3) в качестве фактического параметра n в них передаётся текущее значение этой переменной. На рисунке участки, ограниченные пунктиром, демонстрируют область видимости соответствующего значения переменной n.
Каждый раз, возвращаясь из процедуры, переменная n принимает значение, которое было до вызова данной процедуры. Например, если процедура F(n - 2) была вызвана при n = 6, то, попадая в процедуру, переменная n примет значение 4(= 6 − 2). После выхода из этой процедуры значение переменной n вновь будет равно 6.
На рисунке представлена схема выполнения вызова процедуры F(6) в виде дерева.
В данном случае осуществляется вертикальный обход дерева в прямом (префиксном) порядке. То есть сначала просматривается вершина, затем правое поддерево, затем левое поддерево.
Согласно алгоритму, сразу после входа в процедуру осуществляется вывод на экран переменной n. Следовательно, при выполнении вызова F(6) на экране будет отображена последовательность чисел: 6 4 2 0 -1 1 3 1 0. На экране будет напечатано 9 чисел.