КЕГЭ № 5. Выполнение и анализ простых алгоритмов. Поразрядное двоичное преобразование

Алгоритм получает на вход натуральное число M > 1 и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. В конец записи дописывается ещё два разряда по следующему правилу: если M чётное, в конец числа дописывается сначала ноль, а затем единица. В противном случае, если M нечётное, справа дописывается сначала единица, а затем ноль. Пример. Двоичная запись 1002 числа 410 будет преобразована в 100012, а двоичная запись 1112 числа 710 будет преобразована в 111102. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа M) является двоичной записью числа S – результата работы данного алгоритма. Какое наибольшее число S, которое меньше 12510, может являться результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. К этой записи дописываются справа ещё несколько разрядов по следующему правилу: а) если M чётное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи; 6) если M нечётное, то к нему справа приписываются два нуля, а слева единица. Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа M) является двоичной записью искомого числа S. Пример. Запись числа 11012 будет преобразована в 11101002. При каком наименьшем числе M в результате работы алгоритма получится S > 21510. В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. Далее эта запись обрабатывается по следующему правилу: а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10; б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11. Полученная таким образом запись является двоичной записью искомого числа S. Пример. Для исходного числа 610 = 1102 результатом является число 10002 = 810, а для исходного числа 410 = 1002 результатом является число 11012 = 1310. При каком наименьшем числе M в результате работы алгоритма получится S > 4010. В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. Складываются все цифры полученной двоичной записи. В конец записи дописывается остаток от деления суммы на 2. 3. Предыдущий пункт повторяется для записи с добавленной цифрой. 4. Результат переводится в десятичную систему. Пример. Дано число M = 1310. Алгоритм работает следующим образом: 1. Двоичная запись числа M: 11012. 2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 110112. 3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 1101102. 4. Результат работы алгоритма S = 5410. При каком наименьшем числе M в результате работы алгоритма получится S > 15010? В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. В конец двоичной записи дописываются две цифры, соответствующие двоичной записи остатка от деления исходного числа на 3. 3. В конец двоичной записи числа, полученного на предыдущем шаге, дописываются три цифры, соответствующие двоичной записи остатка от деления этого числа на 5. 4. Результатом работы алгоритма становится десятичная запись полученного числа S. Пример. Дано число N = 1310. Алгоритм работает следующим образом: 1. Строим двоичную запись: 1310 = 11012. 2. Остаток от деления 13 на 3 равен 1, добавляем к двоичной записи цифры 01, получаем 1101012 = 5310. 3. Остаток от деления 53 на 5 равен 3, добавляем к двоичной записи цифры 011, получаем 1101010112 = 42710. 4. Результат работы алгоритма S = 42710. Определите количество принадлежащих отрезку [1 222 222 222; 1 555 555 666] чисел, которые могут получиться в результате работы этого алгоритма.

Алгоритм получает на вход натуральное число M > 1 и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. Вычисляется количество единиц, стоящих на чётных местах в двоичной записи числа M без ведущих нулей, и количество нулей, стоящих на нечётных местах. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы). 3. Результатом работы алгоритма становится модуль разности полученных двух чисел. Пример. Дано число M = 3910. Алгоритм работает следующим образом: 1. Строится двоичная запись: 3910 = 1001112. 2. Выделяем единицы на чётных и нули на нечётных местах: 1001112. На чётных местах стоят две единицы, на нечётных – один ноль. 3. Модуль разности равен 1. Результат работы алгоритма S = 1. При каком наименьшем числе M в результате работы алгоритма получится S = 510? В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. Далее эта запись обрабатывается по правилу: а) если число M делится на 3, то к этой записи дописываются три последние двоичные цифры; б) если число M на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа. Полученная таким образом запись является двоичной записью искомого числа S. 3. Результат переводится в десятичную систему и выводится на экран. Пример. Для исходного числа 1210 = 11002 результатом является число 11001002 = 10010, а для исходного числа 410= 1002 это число 100112 = 1910. Какое наименьшее число S, которое больше 15110, может являться результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. Полученная запись обрабатывается по следующему правилу: а) если сумма цифр в двоичной записи числа чётна, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 1; б) если сумма цифр в двоичной записи числа нечётна, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11. Полученная таким образом запись является двоичной записью искомого числа S. Пример. Для исходного числа 610 = 1102 результатом является число 1002 = 410, а для исходного 410 = 1002 результатом является число 11012 = 1310. Укажите число M, после обработки которого с помощью этого алгоритма получается наименьшее значение S, большее 2510. В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M > 1 и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. В конец записи дописывается вторая справа цифра двоичной записи. 3. В конец записи дописывается вторая слева цифра двоичной записи. 4. Результат переводится в десятичную систему. Пример. Дано число M = 1310. Алгоритм работает следующим образом: 1. Двоичная запись числа M: 11012. 2. Вторая справа цифра 0, новая запись 110102. 3. Вторая слева цифра 1, новая запись 1101012. 4. Результат работы алгоритма S = 5310. При каком наименьшем числе M в результате работы алгоритма получится S > 12010? В ответе запишите это число в десятичной системе счисления.

Алгоритм получает на вход натуральное число M и строит по нему новое число S следующим образом: 1. Строится двоичная запись числа M. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи числа M, и остаток от деления суммы на 2 дописывается в конец числа. 3. Над этой записью производятся те же действия — в конец числа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа M) является двоичной записью результирующего числа S. Пример. Запись 111002 преобразуется в запись 1110012, а затем в запись 11100102. Укажите такое наименьшее число M, для которого результат работы алгоритма больше числа 7710. В ответе запишите это число в десятичной системе счисления.