Алгоритмы для формальных исполнителей

По материалам сайта Решу ЕГЭ.

Задание 1

Автомат обрабатывает натуральное число N по следующему алгоритму: 1.Строится двоичная запись числа N без ведущих нулей. 2. Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль. 3. Полученное число переводится в десятичную запись и выводится на экран. Пример. Дано число N=13. Алгоритм работает следующим образом: 1. Двоичная запись числа N: 1101. 2. В записи больше единиц, справа приписывается единица: 11011. 3. На экран выводится десятичное значение полученного числа 27. Какое наименьшее число, превышающее 100, может получиться в результате работы автомата?

Задание 2

Автомат обрабатывает натуральное число N ()по следующему алгоритму: 1. Строится восьмибитная двоичная запись числа N. 2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0). 3. Полученное число переводится в десятичную запись. 4. Из исходного числа вычитается полученное, разность выводится на экран. Пример. Дано число N = 131. Алгоритм работает следующим образом: 1. Восьмибитная двоичная запись числа N: 10000011. 2. Все цифры заменяются на противоположные, новая запись 01111100. 3. Десятичное значение полученного числа: 124. 4. На экран выводится число: 131-124 = 7. Какое число нужно ввести в автомат, чтобы в результате получилось 185?

Задание 3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: a) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; b) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 97 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Задание 4

Автомат обрабатывает натуральное число N по следующему алгоритму: 1.Строится двоичная запись числа N без ведущих нулей. 2. Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль. 3. Полученное число переводится в десятичную запись и выводится на экран. Пример. Дано число N=13. Алгоритм работает следующим образом: 1. Двоичная запись числа N: 1101. 2. В записи больше единиц, справа приписывается единица: 11011. 3. На экран выводится десятичное значение полученного числа 27. Какое наименьшее число, превышающее 80, может получиться в результате работы автомата?

Задание 5

Автомат обрабатывает натуральное число N ()по следующему алгоритму: 1. Строится восьмибитная двоичная запись числа N 2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0). 3. Полученное число переводится в десятичную запись. 4. Из исходного числа вычитается полученное, разность выводится на экран. Пример. Дано число N=131. Алгоритм работает следующим образом: 1. Восьмибитная двоичная запись числа N: 10000011. 2. Все цифры заменяются на противоположные, новая запись 01111100. 3. Десятичное значение полученного числа: 124. 4. На экран выводится число: 131-124 = 7. Какое число нужно ввести в автомат, чтобы в результате получилось 105?