Решение: Анализ алгоритма деления
Ниже на пяти языках программирования записан алгоритм. Получив на вход число $x$, этот алгоритм печатает два числа: $L$ и $M$. Алгоритм повторяет действия, пока $x > 0$: увеличивает $M$ на 1, увеличивает $L$ на 1, если текущее значение $x$ чётное, затем заменяет $x$ на результат целочисленного деления на 2. Найдите наименьшее число $x$, при вводе которого алгоритм печатает сначала 6, а потом 7.
1x = int(input()) 2L = 0 3M = 0 4while x > 0: 5 M = M + 1 6 if x % 2 == 0: 7 L = L + 1 8 x = x // 2 9print(L) 10print(M)
Решение по шагам
4 шагаПеременная $M$ увеличивается на каждой итерации. Чтобы получить $M = 7$, исходное число должно иметь 7 цифр в двоичной записи.
Переменная $L$ увеличивается тогда, когда текущее значение $x$ чётное. Для получения $L = 6$ первые шесть значений должны быть чётными, а последнее — нечётным.
Наименьшее семиразрядное двоичное число, у которого первые шесть значений при последовательном делении на 2 чётные, — $1000000_2$. В десятичной системе это $64$.
Проверка: последовательность значений $x$ равна $64, 32, 16, 8, 4, 2, 1$. Получаем $L = 6$ и $M = 7$.
Где здесь ошибаются
Путать количество итераций цикла с количеством делений до получения нуля.
Не учитывать последнее нечётное значение $x = 1$.
Выбирать число 63, у которого недостаточно последовательных чётных значений.