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

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

«Алгоритм получает на вход натуральное число 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. ### Шаг 1: Определение условий кратности 4 Число кратно 4, если последние две цифры его двоичной записи формируют число, кратное 4. В двоичной системе это означает, что последние два бита должны быть 00, 01, 10 или 11. Однако, чтобы число было кратно 4, последние два бита должны быть 00. ### Шаг 2: Проверка чисел от 100 до 199 Начнем проверять числа от 100 до 199, чтобы найти наименьшее \( N \), для которого \( R \) будет кратно 4. ### Шаг...