Автомат обрабатывает натуральное число N по следующему алгоритму. 1) Строится двоичная запись числа N.
2) Все кроме первой значащие цифры инвертируются (0 заменяется на 1, а 1 на 0).
3) Полученное число переводится в десятичную запись.
4) Новое число складывается с исходным, полученная сумма выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 13 = 11012.
2) Все кроме первой значащие цифры инвертируются: 10102.
3) Десятичное значение полученного числа 10.
4) На экран выводится число 13 + 10 = 23.
Укажите такое наибольшее число N, для которого результат работы алгоритма не превышает 123?.
Поехали:
1) Поскольку нам нужно найти наибольшее значение N, мы начинаем с максимального значения, которое может быть представлено в двоичной системе счисления с помощью 4-х бит - 1111. Это соответствует числу 15 в десятичной системе.
2) Сначала мы строим двоичную запись числа N. В данном случае это 1111.
Затем мы инвертируем все цифры, кроме первой цифры, получая 0000.
3) Теперь нам нужно перевести полученное число в десятичную систему счисления. В данном случае это 0.
4) И последним шагом мы складываем исходное число и полученное число, получая сумму 15 + 0 = 15.
Таким образом, результат работы алгоритма для числа 15 равен 15.
5) Продолжаем с предыдущего шага, уменьшая N на 1. Теперь N = 14.
6) Построим двоичную запись числа N: 14 = 11102.
Инвертируем все цифры, кроме первой: 00012.
Переводим полученное число в десятичную систему: 1.
Cкладываем исходное число и полученное число: 14 + 1 = 15.
Результат работы алгоритма для числа 14 также равен 15.
7) Продолжаем уменьшать N на 1. Теперь N = 13.
8) Построим двоичную запись числа N: 13 = 11012.
Инвертируем все цифры, кроме первой: 10102.
Переводим полученное число в десятичную систему: 10.
Cкладываем исходное число и полученное число: 13 + 10 = 23.
Результат работы алгоритма для числа 13 равен 23.
9) Продолжаем уменьшать N на 1. Теперь N = 12.
10) Построим двоичную запись числа N: 12 = 11002.
Инвертируем все цифры, кроме первой: 10102.
Переводим полученное число в десятичную систему: 10.
Cкладываем исходное число и полученное число: 12 + 10 = 22.
Результат работы алгоритма для числа 12 равен 22.
11) Продолжаем уменьшать N на 1. Теперь N = 11.
12) Построим двоичную запись числа N: 11 = 10112.
Инвертируем все цифры, кроме первой: 01002.
Переводим полученное число в десятичную систему: 2.
Cкладываем исходное число и полученное число: 11 + 2 = 13.
Результат работы алгоритма для числа 11 равен 13.
13) Продолжаем уменьшать N на 1. Теперь N = 10.
14) Построим двоичную запись числа N: 10 = 10102.
Инвертируем все цифры, кроме первой: 01002.
Переводим полученное число в десятичную систему: 2.
Cкладываем исходное число и полученное число: 10 + 2 = 12.
Результат работы алгоритма для числа 10 равен 12.
15) Продолжаем уменьшать N на 1. Теперь N = 9.
16) Построим двоичную запись числа N: 9 = 10012.
Инвертируем все цифры, кроме первой: 01102.
Переводим полученное число в десятичную систему: 6.
Cкладываем исходное число и полученное число: 9 + 6 = 15.
Результат работы алгоритма для числа 9 также равен 15.
Как видим, при уменьшении значения N до 9, результат работы алгоритма остается равным 15. Однако, при дальнейшем уменьшении N до 8 результат уже будет больше 123.
Таким образом, наибольшее число N, для которого результат работы алгоритма не превышает 123, равно 9.