Автомат преобразует натуральное число N: если N чётное, к его двоичной записи справа дописывают '10'; если нечётное, слева дописывают '1', а справа '00'. Полученное число в десятичной системе больше 107. Найдите наименьшее N.
Подробное объяснение
Рассмотрим два случая. Если N чётное, результат R = 4N + 2. Решая неравенство 4N+2 > 107, получаем N > 26.25, минимальное чётное N = 28 даёт R = 114. Если N нечётное, пусть k — длина двоичной записи N, тогда R = 2^{k+2} + 4N. Проверяем нечётные N: N=9 даёт R=100 (≤107), N=11 даёт R=108 (>107). Сравнивая N=28 и N=11, выбираем наименьшее N=11.
Часто задаваемые вопросы (FAQ)
1
Как вывести формулу для результата при чётном N?
Приписывание '10' справа эквивалентно умножению на 4 и добавлению 2, так как '10' в двоичной системе равно 2. Таким образом, R = 4N + 2.
2
Как вывести формулу для результата при нечётном N?
Приписывание '1' слева увеличивает число на 2^{k+2}, где k — длина исходной записи, а приписывание '00' справа умножает N на 4. Итого R = 2^{k+2} + 4N.
3
Почему при нечётном N нужно учитывать длину k?
Потому что добавление '1' слева сдвигает все биты на k+2 разряда влево, что соответствует степени двойки, зависящей от k.
Типичные ошибки
1
Считать, что для нечётного N результат равен N + 2^{k+2} без умножения на 4.
Забывают, что приписывание '00' справа умножает N на 4, а не просто добавляет нули. Правильно: R = 2^{k+2} + 4N.
2
Не рассматривать оба случая (чётное/нечётное) и сразу брать минимальное N из одного случая.
Наименьшее N может оказаться в другом случае, поэтому нужно проверять оба и выбирать минимум.
3
Ошибочно считать, что для чётного N результат равен 2N + 2.
Приписывание двух битов справа (не одного) — это умножение на 4, а не на 2. Правильно: R = 4N + 2.