Question

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) Затем справа дописываются два разряда: символы 01, если число N четное, и 10, если нечѐтное. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число, большее 73. В ответе это число запишите в десятичной системе.

Answer 1

Ответ:

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₁₀

Объяснение:

Answer 2

Давайте последовательно увеличивать значение N и применять описанный алгоритм, пока не получим число, большее 73.

Попробуем сначала N = 1:

1. Двоичная запись числа 1: 1
2. Дописываем 10 (нечетное число)

Получаем R = 110 (в десятичной системе это 6).

Продолжим увеличивать N:

• При N = 2:

  1. Двоичная запись числа 2: 10
  2. Дописываем 01 (четное число) Результат: R = 1001 (в десятичной системе это 9).

• При N = 3:

  1. Двоичная запись числа 3: 11
  2. Дописываем 10 (нечетное число) Результат: R = 11110 (в десятичной системе это 30).

• При N = 4:

  1. Двоичная запись числа 4: 100
  2. Дописываем 01 (четное число) Результат: R = 1001001 (в десятичной системе это 73).

• При N = 5:

  1. Двоичная запись числа 5: 101
  2. Дописываем 10 (нечетное число) Результат: R = 1011010 (в десятичной системе это 90).

Таким образом, минимальное значение N, при котором после обработки получается число, большее 73, это N = 5. Результат R будет равен 90 в десятичной системе.