Задачи ЕГЭ-5. Алгоритмы обработки чисел (двоичные числа)

Задание ЕГЭ-5. Алгоритмы обработки чисел.

Задача 1.

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

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

2. К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.

3. Полученное число переводится в десятичную систему счисления.

Какое число получится, если на вход было подано число 19?

Задача 2.

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

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

2. К этой записи дописываются справа еще два разряда по следующему правилу:

   • складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

   • над этой записью производятся те же действия — справа дописывается остаток от деления суммы ее цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите такое наибольшее число N, для которого результат работы данного алгоритма будет меньше значения 86. В ответе это число запишите в десятичной системе счисления.

Задача 3.

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

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

2.  К этой записи дописываются справа ещё два разряда по следующему правилу:

а)  складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б)  над этой записью производятся те же действия  — справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Задача 4.

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

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

2.  К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи:

а)  если сумма нечетная, к числу дописывается 11,

б)  если сумма четная, дописывается 00.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Задача 5

Автомат обрабатывает натуральное число N (0 ≤ N ≤ 255) по следующему алгоритму.

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

2.  Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).

3.  Полученное число переводится в десятичную запись.

4.  Из нового числа вычитается исходное, полученная разность выводится на экран.

Задача 6

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2.  Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3.  Предыдущий пункт повторяется для записи с добавленной цифрой.

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

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

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

2.  Сумма цифр двоичной записи  — 3, остаток от деления на 2 равен 1, новая запись: 11011.

3.  Сумма цифр полученной записи  — 4, остаток от деления на 2 равен 0, новая запись: 110110.

4.  На экран выводится число 54.

 Какое наименьшее число, большее 93, может появиться на экране в результате работы автомата?

Задача 7

Автомат обрабатывает натуральное число N по следующему алгоритму.

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

2.  Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.

3.  Полученное число переводится в десятичную запись.

4.  Новое число вычитается из исходного, полученная разность выводится на экран.

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

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

2.  Удаляется первая единица и следующий за ней ноль: 11.

3.  Десятичное значение полученного числа 3.

4.  На экран выводится число 11 – 3  =  8.

 Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?

Задача 8

Автомат обрабатывает натуральное число N по следующему алгоритму.

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

2.  Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.

3.  Полученное число переводится в десятичную запись.

4.  Новое число вычитается из исходного, полученная разность выводится на экран.

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

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

2.  Удаляется первая единица и следующий за ней ноль: 11.

3.  Десятичное значение полученного числа 3.

4.  На экран выводится число 11 – 3  =  8.

 Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 100 до 3000?

Задача 9

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

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

2.  К этой записи дописываются справа ещё два разряда по следующему правилу:

а)  в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;

б)  к этой записи справа дописывается 1, если остаток от деления количества единиц на 2 равен 0, и 0, если остаток от деления количества единиц на 2 равен 1.

Полученная таким образом запись является двоичной записью искомого числа R.

Укажите минимальное число R, которое превышает 54 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Задача 10

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

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

2.  Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи дописывается 1, если нечётных  — 0. Если чётных и нечётных цифр в десятичной записи поровну, то в конец двоичной записи дописывается 0, если данное число чётное, и 1  — если нечётное.

3−4.  Пункт 2 повторяется для вновь полученных чисел ещё два раза.

5.  Результатом работы алгоритма становится десятичная запись полученного числа R.

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

1.  Строим двоичную запись: 1410  =  11102.

2.  В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной записи 0, получаем 111002  =  2810.

3.  В записи числа 28 чётных цифр больше, дописываем к двоичной записи 1, получаем 1110012  =  5710.

4.  В записи числа 57 нечётных цифр больше, дописываем к двоичной записи 0, получаем 11100102  =  11410.

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

 Определите количество принадлежащих отрезку [123 455; 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.