Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 7
Условие
Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Подсказки — как подойти к решению
- Разберись, что именно вычитается: первая единица и идущие за ней нули соответствуют старшей степени двойки в двоичной записи числа. Значит, разность определяется только позицией старшего разряда, а не самим числом.
- Собирай получаемые разности в множество, чтобы одинаковые значения не считались дважды. Пройди перебором весь диапазон из условия и отдельно проверь числа, у которых после удаления разрядов не остаётся цифр.
Решение
Заметим, что при удалении первой единицы и всех стоящих сразу за ней нулей из числа вычитается 2 в степени, равной номеру старшего разряда в двоичной записи числа. Значит, нужно найти количество степеней двойки, которые находятся между 10 и 1000. Также необходимо учесть, что числа от 10 до 15 будут соответствовать предыдущей степени двойки. Значит, к количеству степеней двойки, входящих в диапазон чисел от 10 до 1000, необходимо добавить единицу. Всего в диапазоне от 10 до 1000 шесть степеней двойки. Следовательно, будет показано 6 + 1 = 7 различных чисел.
Ответ: 7.
Приведём решение Юрия Красильникова на языке Python.
print(len(set([n - int(bin(n)[3:],2) for n in range(10,1001)])))
Приведём решение Ильи Молоковича на языке Python.
a = []
for x in range(10, 1001):
i = int(bin(x)[3:], 2)
if x - i not in a:
a.append(x-i)
print(len(a))
Приведём решение Ильи Крылова на языке Python.
l = []
for n in range(10, 1001):
n2 = bin(n)[2:]
n2 = n2[n2.index('1') + 1:]
n2 = n2.lstrip('0')
if n2 == '':
n2 = '0'
n2 = int(n2, 2)
r = n2-n
if(l.count(r)==0):
l.append(r)
print(len(l))
Приведём решение Алексея Третьякова на языке Python.
sp = set()
for n in range(10, 1001):
dv = bin(n)[2:]
first = str(dv).find('1')
second = str(dv).find('1', first + 1)
new_dv = dv[second:]
sp.add(int(dv, 2) - int(new_dv, 2))
print(len(sp))
Примечание.
Заметим, что число 0 не может являться результатом работы алгоритма. Если на вход подается число, равное степени двойки, то после выполнения шага 2 (удаления первой единицы из этого числа) получается 0. На шаге 4 из исходного числа вычитается 0 и получается исходное число, равное степени двойки.
Приведём решение Ивана Гладких на языке Python.
c = set()
for n in range(10,1001):
i = str(bin(n)[3:])
z = n - (int(i,2))
c.add(z)
print(len(c))
Типичные ошибки
- Похоже, ты посчитал только степени двойки, попавшие в диапазон. Не забудь про группу чисел в начале диапазона, где старший разряд стоит на позицию ниже: она даёт ещё одно значение, которого в твоём списке нет.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике