Решение: Минимальное число после алгоритма
На вход алгоритма подаётся натуральное число $N$. Сначала строится его двоичная запись. Затем справа дописываются два разряда: первый равен остатку от деления суммы цифр исходной записи на 2, а второй равен остатку от деления суммы цифр полученной записи на 2. Полученная запись является двоичной записью числа $R$. Найдите минимальное число $R$, которое превышает 396.
Решение по шагам
5 шаговОбозначим через $p$ остаток от деления суммы единиц в двоичной записи числа $N$ на 2. Первый дописанный разряд равен $p$.
После добавления первого разряда чётность суммы цифр становится $p+p=0$, поэтому второй дописанный разряд равен 0.
Следовательно, $R$ получается умножением $N$ на 4 и добавлением числа $2p$: $R=4N+2p$.
Минимальное число, большее 396, имеющее нужный вид, сначала проверяем среди 398. Для него $N=(398-2)/4=99$, а двоичная запись $99=1100011$ содержит 4 единицы, поэтому $p=0$ и результат был бы $4\cdot99=396$, а не 398.
Следующее число — 400. Для него $N=100$, но двоичная запись $100=1100100$ содержит 3 единицы, поэтому $p=1$ и алгоритм даёт $R=4\cdot100+2=402$.
Где здесь ошибаются
Считать, что оба дописанных разряда всегда равны единице.
Не проверить чётность числа единиц в двоичной записи исходного числа.
Выбрать 398 как первое число после 396 без проверки, может ли оно быть результатом алгоритма.