Разбор теории для 5️⃣-го номера ЕГЭ по информатике 2023 года
Условие: Тип 5 № 17370
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 100 до 3000?
Комментарии к первому варианту решения задачи:
- создаем множество
set()
A
, в которое будем добавлять разность нового числа и исходного - делаем перебор от 100 до 3000 (как сказано в условии)
- переводим число в двоичную систему и делаем срез от 3 цифры, т.к. нам нужно удалить первую единицу слева
- переводим наше число в десятичную систему
- находим разность нового числа и исходного
- добавляем во множество
set()
разность - и выводим длину
A
# Код решения Вариант 1 A = set() for n in range(100, 3000+1): s = bin(n)[3:] s = int(s, 2) r = n - s A.add(r) print(len(A))
Комментарии ко второму варианту решения задачи:
- создаем список
A
, в который будем добавлять разность нового числа и исходного - делаем перебор от 100 до 3000 (как сказано в условии)
- переводим число в двоичную систему и делаем срез от 3 цифры, т.к. нам нужно удалить первую единицу слева
- переводим наше число в десятичную систему
5-6. если такой разности в списке нет, то добавляем в список. Это нужно для того, чтобы не было одинаковых чисел
# Код решения Вариант 2 A = [] for n in range(100, 3001): s = bin(n)[3:] s = int(s, 2) if n - s not in A: A.append(n - s) print(len(A))