Question

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3) Шаг 2 повторяется ещё два раза. 4) Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 65 в результате работы алгоритма получится число, кратное 4?

Answer 1

Ответ:284

Объяснение:

for i in range(65, 10000):

   n = i

   x = bin(n)[2:]

   for i in range(2):

       if x.count('0') == x.count('1'):

           x += x[-1]

       else:

           x += '0' if x.count('0') < x.count('1') else '1'

   r = int(x, 2)

   if r % 4 == 0:

       print(r)

       break

Answer 2

Алгоритм получения числа R

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

1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае, в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления.

Наименьшее исходное число N, при котором результат кратен 4

Чтобы определить наименьшее исходное число N, при котором результат работы алгоритма будет кратен 4, мы можем применить алгоритм к различным значениям N, начиная с 65, и проверить результаты.

Применение алгоритма:

1. Для N = 65: - Двоичная запись числа 65: 1000001. - Количество нулей: 5. - Количество единиц: 2. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10000011. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100000110. - Двоичная запись числа: 1000001101. - Переводим результат в десятичную систему: 1101. - Результат не кратен 4.

2. Для N = 66: - Двоичная запись числа 66: 1000010. - Количество нулей: 6. - Количество единиц: 1. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10000101. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100001011. - Двоичная запись числа: 1000010111. - Переводим результат в десятичную систему: 10111. - Результат не кратен 4.

3. Для N = 67: - Двоичная запись числа 67: 1000011. - Количество нулей: 5. - Количество единиц: 3. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10000111. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100001111. - Двоичная запись числа: 1000011111. - Переводим результат в десятичную систему: 11111. - Результат не кратен 4.

4. Для N = 68: - Двоичная запись числа 68: 1000100. - Количество нулей: 5. - Количество единиц: 3. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10001001. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100010011. - Двоичная запись числа: 1000100111. - Переводим результат в десятичную систему: 100111. - Результат не кратен 4.

5. Для N = 69: - Двоичная запись числа 69: 1000101. - Количество нулей: 4. - Количество единиц: 4. - Так как количество нулей и единиц одинаково, добавляем в конец записи последнюю цифру, которая является 1. - Полученная запись: 10001011. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100010111. - Двоичная запись числа: 1000101111. - Переводим результат в десятичную систему: 101111. - Результат не кратен 4.

6. Для N = 70: - Двоичная запись числа 70: 1000110. - Количество нулей: 5. - Количество единиц: 3. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10001101. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100011011. - Двоичная запись числа: 1000110111. - Переводим результат в десятичную систему: 110111. - Результат не кратен 4.

7. Для N = 71: - Двоичная запись числа 71: 1000111. - Количество нулей: 4. - Количество единиц: 4. - Так как количество нулей и единиц одинаково, добавляем в конец записи последнюю цифру, которая является 1. - Полученная запись: 10001111. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100011111. - Двоичная запись числа: 1000111111. - Переводим результат в десятичную систему: 111111. - Результат не кратен 4.

8. Для N = 72: - Двоичная запись числа 72: 1001000. - Количество нулей: 4. - Количество единиц: 3. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная запись: 10010001. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100100011. - Двоичная запись числа: 1001000111. - Переводим результат в десятичную систему: 1000111. - Результат не кратен 4.

9. Для N = 73: - Двоичная запись числа 73: 1001001. - Количество нулей: 3. - Количество единиц: 5. - Так как количество единиц больше, добавляем в конец записи цифру 0. - Полученная запись: 10010010. - Применяем алгоритм ещё два раза: - Двоичная запись числа: 100100101. - Двоичная запись числа: 1001001011. - Переводим результат в десятичную систему: 1001011. - Результат не кратен 4.

10. Для N = 74: - Двоичная запись числа 74: 1001010. - Количество нулей: 5. - Количество единиц: 3. - Так как количество нулей больше, добавляем в конец записи цифру 1. - Полученная