На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N бы...
На вход алгоритма подаётся натуральное число N. Алгоритм
строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается справа бит чётности: 0, если в
двоичном коде числа N было чётное число единиц, и 1, если
нечётное.
3) К полученному результату дописывается ещё один бит
чётности.
Полученная таким образом запись (в ней на два разряда
больше, чем в записи исходного числа N) является двоичной
записью искомого числа R. Укажите минимальное число R,
большее 180, которое может быть получено в результате
работы этого алгоритма. В ответе это число запишите в
десятичной системе
Гость
Ответ(ы) на вопрос:
Гость1. Установим допустимые сочетания двух последних битов (битов четности).
Если в N было четное количество единиц, то дописывается ноль. Поскольку ноль не меняет количества единиц, второй бит четности тоже будет нулевым. Правило №1: Если в двоичном представлении четное количество единиц, то дописывается 00.
Если в N было нечетное количество единиц, то дописывается единица. Это меняет количество единиц на четное, поэтому второй бит четности будет нулевым. Правило №2: Если в двоичном представлении нечетное количество единиц, то дописывается 10.
Первое число R, большее 180, это 181. Переведем его в двоичную систему счисления.
181₁₀ = 10110101₂
Мы видим, что оба наших правила нарушены, т.е. число 181 не подходит в качестве R.
Представление N (101101) содержит четное количество единиц, а для четного количества действует Правило №1 и мы должны записать 00, что уменьшит наше минимально возможное число R=181₁₀
Но если мы в числе N поменяем местами два правых бита, получим число 101110, которое больше чем 101101 и теперь по все тому же Правилу №1 мы получаем право приписать два нолика и получить R=10111000₂ = 184₁₀
Не нашли ответ?
Похожие вопросы