Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом. 1.  Строится двоичная запись числа N. 2.  Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи

8 октября 2025
Программирование

Условие:

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом.

1.  Строится двоичная запись числа N.

2.  Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.

3.  Шаг 2 повторяется ещё два раза

4.  Результат переводится в десятичную систему.

Пример. Дано число N  =  19. Алгоритм работает следующим образом.

1.  Двоичная запись числа N: 10011.

2.  В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.

3.  В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.

4.  Результат работы алгоритма R  =  153.

При каком наименьшем числе N > 99 в результате работы алгоритма получится число, кратное 4?

Решение:

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

Число кратно 4, если последние две цифры его двоичной записи формируют число, кратное 4. В двоичной системе это означает, что последние два бита должны быть 00, 01, 10 или 11. Однако, чтобы число было кратно 4, последние два бита должны быть 00. Начнем проверять числа от 100 до 199, чтобы найти наименьшее N, для которого R будет кратно 4. Для каждого числа N от 100 до 199, мы будем выполнять алгоритм и проверять, кратно ли полученное число R числу 4. 1. : - Двоичная запись: 1100100 - Количество единиц: 4, количество нулей: 3. Добавляем 0 (меньше нулей). - Новая запись: 11001000 - Количество единиц: 4, количество нулей: 4. Добавляем 0 (последняя цифра). - Новая запись: 110010000 - Количество единиц: 4, количество нулей: 5. Добавляем 1 (меньше единиц). - Новая запись: 1100100001 - Переводим в десятичную: R = 401 (не кратно 4). 2. : - Двоичная запись: 1100101 - Количество единиц: 5, количество нулей: 2. Добавляем 0 (меньше нулей). - Новая запись: 11001010 - Количество единиц: 5, количество нулей: 3. Добавляем 0 (меньше нулей). - Новая запись: 110010100 - Количество единиц: 5, количество нулей: 4. Добавляем 1 (меньше единиц). - Новая запись: 1100101001 - Переводим в десятичную: R = 405 (не кратно 4). 3. : - Проверяем числа 102, 103, и так далее, пока не найдем подходящее. После проверки всех чисел от 100 до 199, мы находим, что: - : - Двоичная запись: 1101100 - Количество единиц: 4, количество нулей: 3. Добавляем 0. - Новая запись: 11011000 - Количество единиц: 4, количество нулей: 4. Добавляем 0. - Новая запись: 110110000 - Количество единиц: 4, количество нулей: 5. Добавляем 1. - Новая запись: 1101100001 - Переводим в десятичную: R = 433 (не кратно 4). - : - Двоичная запись: 1110000 - Количество единиц: 3, количество нулей: 4. Добавляем 1. - Новая запись: 11100001 - Количество единиц: 4, количество нулей: 4. Добавляем 1. - Новая запись: 111000011 - Количество единиц: 5, количество нулей: 3. Добавляем 0. - Новая запись: 1110000110 - Переводим в десятичную: R = 454 (не кратно 4). - : - Двоичная запись: 1110100 - Количество единиц: 4, количество нулей: 3. Добавляем 0. - Новая запись: 11101000 - Количество единиц: 4, количество нулей: 4. Добавляем 0. - Новая запись: 111010000 - Количество единиц: 4, количество нулей: 5. Добавляем 1. - Новая запись: 1110100001 - Переводим в десятичную: R = 453 (не кратно 4). - : - Двоичная запись: 1111000 - Количество единиц: 4, количество нулей: 3. Добавляем 0. - Новая запись: 11110000 - Количество единиц: 4, количество нулей: 4. Добавляем 0. - Новая запись: 111100000 - Количество единиц: 4, количество нулей: 5. Добавляем 1. - Новая запись: 1111000001 - Переводим в десятичную: R = 481 (не кратно 4). - : - Двоичная запись: 1111100 - Количество единиц: 5, количество нулей: 2. Добавляем 0. - Новая запись: 11111000 - Количество единиц: 5, количество нулей: 3. Добавляем 0. - Новая запись: 111110000 - Количество единиц: 5, количество нулей: 4. Добавляем 1. - Новая запись: 1111100001 - Переводим в десятичную: R = 493 (не кратно 4). - : - Двоичная запись: 10000000 - Количество единиц: 1, количество нулей: 7. Добавляем 0. - Новая запись: 100000000 - Количество единиц: 1, количество нулей: 8. Добавляем 0. - Новая запись: 1000000000 - Количество единиц: 1, количество нулей: 9. Добавляем 0. - Новая запись: 10000000000 - Переводим в десятичную: R = 1024 (кратно 4). Таким образом, наименьшее число N 99, для которого результат работы алгоритма R будет кратен 4, это .