ЕГЭ-05. Анализ простых алгоритмов

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

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

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

а) если N четное, то к нему справа приписываются два нуля, а слева единица;

б) если N нечетное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;

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

Например, исходное число 4₁₀=100₂ преобразуется число 11000₂ = 48₁₀, а исходное число 13₁₀ = 1101₂ преобразуется в число 110111₂ = 55₁₀. Укажите такое число N большее 8, для которого число R является наименьшим среди чисел, превышающих 88. В ответе это число запишите в десятичной системе счисления.

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.

3. Для полученной записи повторно выполняется п. 2.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите минимальное число R, большее, чем 1500, которое может получится в результате работы алгоритма.

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.

3. Пункт 2 повторяется ещё раз для записи, полученной после второго пункта.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите максимальное число R, меньшее, чем 1500, которое может получится в результате работы алгоритма.

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

1. Каждая цифра числа N записывается с помощью 4-битного двоичного кода. В конец кода каждой цифры добавляется бит чётности так, чтобы количество единиц в расширенной записи стало чётным.

2. Далее к этой записи справа дописывается 0, а два левых разряда заменяются на 1.

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

Например, для числа 13 двоичные коды цифр: 1 = 0001₂, 3 = 0011₂. С добавленными битами чётности: 00011 и 00110, результат шага 1: 0001100110. Заменяем два левых разряда на 1 и добавляем справа 0: 1011001100₂ = 716.

Укажите минимальное N, после обработки которого с помощью этого алгоритма получится 674890.

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то 4 младших бита инвертируются, т.е. 0 изменяется на 1, а 1 на 0;

б) если сумма цифр в двоичной записи числа нечётная, то инвертируются 4 бита в двоичных разрядах 1-4 (нумерация разрядов справа налево, начиная с 0).

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

Например, для исходного числа 36₁₀ = 100100₂. результатом является число 43₁₀ = 101011₂ а для исходного числа 37₁₀ = 100101₂ результатом является число 59₁₀ = 111011₂. Укажите число N, большее 63, после обработки которого с помощью этого алгоритма получается минимальное число R. В ответе запишите число в десятичной системе счисления.

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

1. Из числа N вычитается количество нулей в двоичной записи числа N.

2. Строится двоичная запись полученного числа.

3. К полученной записи слева дописывается три младших разряда.

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

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

1. 13 = 1101₂, двоичная запись содержит один 0. 13 – 1 = 12.

2. 12₁₀ = 1100₂

3. 1100 -> 1001100.

4. 1001100₂ = 76

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

(А. Игнатюк) Компьютер по имени Иннокентий преобразует натуральное число N по следующим правилам и получает число R:

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

2) Если количество цифр в двоичной записи числа N четно, то справа приписывается 10, если нечётно, то слева приписывается 11.

Полученная таким образом запись является двоичной записью искомого числа R. Найдите количество чисел N из отрезка [100; 200], для которых результат работы компьютера будет четным.

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число N и строит новое число R следующим образом.

1) Строится шестнадцатеричная запись числа N.

2) Далее эта запись обрабатывается по следующему правилу:

а) Если число чётное, справа приписывается максимально возможная цифра, в противном случае справа приписывается 0.

б) Справа приписывается шестнадцатеричная цифра – остаток от деления суммы цифр шестнадцатеричной записи на 16.

в) Пункт б выполняется ещё один раз.

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

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

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число N и строит новое число R следующим образом.

1) Строится шестнадцатеричная запись числа N.

2) Далее эта запись обрабатывается по следующему правилу:

а) Если число чётное, справа приписывается максимально возможная цифра, в противном случае справа приписывается 0.

б) Справа приписывается шестнадцатеричная цифра – остаток от деления суммы цифр шестнадцатеричной записи на 16.

в) Пункт б выполняется ещё один раз.

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

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

(А. Игнатюк) Исполнитель «Аппо» получает на вход четырехзначное число N и строит новое число R по следующим правилам:

1. Если первая цифра числа N делится на 4, то заменяем её на цифру 9.

2. Если первая цифра числа N делится на 2 и не делится на 4, то заменяем её на цифру 3.

Сколько существует чисел N, для которых соответствующее число R начинается с цифры 9, а восьмеричная запись числа R оканчивается цифрой 4?

(А. Игнатюк) Исполнитель «Аполлон» получает на вход четырёхзначное число N и строит новое число R по следующим правилам:

1. Если число N начинается с чётной цифры, то число R вычисляется как сумма первой и третьей цифр и модуля разности второй и четвёртой цифр.

2. Если число N начинается с нечётной цифры, то цифры числа N располагают в неубывающем порядке. Число R вычисляется как сумма цифр в двоичной записи полученного числа.

Сколько существует чисел N, для которых результат работы алгоритма будет более 20?

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

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

Например, для исходного числа 6 = 110₂ результатом является число 1000₂ = 8, а для исходного числа 4 = 100₂ результатом является число 1101₂ = 13.

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

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

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

2. Из полученной записи убирается старшая (левая) единица.

3. Если в полученной записи количество единиц четное, то слева дописывается 10, иначе слева дописывается 1, а справа – 0.

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

Например, для исходного числа 4₁₀ = 100₂ результатом будет являться число 8₁₀ = 1000₂, а для исходного числа 6₁₀ = 110₂ результатом будет являться число 12₁₀ = 1100₂.

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

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

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

2. Складываются все цифры двоичной записи числа N. Если полученная сумма чётна, из числа убирают ведущую единицу (а также ставшие незначащими нули). В противном случае слева приписывается 1, а справа – два ноля.

3. Над новой записью снова производятся действия, описанные в пункте 2.

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

Например, N = 5₁₀ = 101₂ => 1 => 1100₂ = 12₁₀ = R

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

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

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

2. Если количество единиц в этой записи чётно, стирается ведущая единица. В противном случае из записи числа убираются все нули, а в конец приписывается 1.

3. Над новой записью снова производятся действия, описанные в пункте 2.

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

Например, N = 5₁₀ = 101₂ => 1 => 11₂ = 3₁₀ = R.

Сколько существует чисел N, не превосходящих 1000, таких что R = 7?

(В. Шубинкин) Автомат получает на вход номер банковской карты (число N из 16 цифр) и строит по нему контрольное число S следующим образом (вариант алгоритма Лу́на):

– цифры числа нумеруются справа налево, начиная с ноля;

– цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются;

– результат S вычисляется как сумма всех цифр на чётных позициях и преобразованных цифр на нечётных позициях.

Например, для числа 4096 8308 0309 8323 сумма цифр на чётных позициях (с конца) 3+3+9+3+8+3+6+0=35, сумма преобразованных цифр на нечётных позициях 4+7+0+0+0+7+9+8=35. Общая сумма S = 70.

Найдите наименьший номер банковской карты N, для которого результатом работы алгоритма будет число 30. В ответе укажите остаток от деления найденного числа N на 10₈.

(В. Шубинкин) Автомат производит первичную проверку правильности номера банковской карты. Он получает на вход число N из 16 цифр и обрабатывает его по следующим правилам (вариант алгоритма Лу́на):

– цифры числа нумеруются справа налево, начиная с нуля;

– цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются;

– складываются все цифры на чётных позициях и преобразованные цифры на нечётных позициях;

– если полученная сумма кратна 10, считается, что номер корректный.

Например, для числа 4096 8308 0309 8323 сумма цифр на чётных позициях (с конца) 3+3+9+3+8+3+6+0=35, сумма преобразованных цифр на нечётных позициях 4+7+0+0+0+7+9+8=35. Общая сумма 70 кратна 10, значит номер корректен.

Определите наименьшее число N, большее 1234 5678 9101 1121, которое может быть корректным номером согласно указанному алгоритму. Укажите в ответе последние 8 цифр числа.

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

1. Вычисляется число SN как квадрат суммы цифр двоичной записи числа N.

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

3. Результат R вычисляется как SN – SM.

Укажите минимальную сумму чисел N и M, при которых получается R = 33.

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

1. Если число N четное, то цифры этого числа сортируются в порядке убывания, затем полученное число делится на 2 нацело (остаток отбрасывается). Полученное значение является числом R.

Пример: N = 1488 => R = 8841//2 = 4420.

2. Если число N нечетное, то цифры этого числа сортируются в порядке возрастания, затем полученное число умножается на 2. Полученное значение является числом R.

Пример: N = 3807 => R = 378·2 = 756.

Укажите наименьшее число R, которое больше соответствующего исходного числа N на 1.

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

1. Вычисляется произведение P₁ всех ненулевых чётных цифр чисел N и M.

2. Вычисляется произведение P₂ всех нечётных цифр чисел N и M.

3. Результат R вычисляется как модуль разности P₁ и P₂.

Например, для N = 256 и M = 108 получаем P₁ = 2·6·8 = 96 и P₂ = 5·1 = 5, так что R = |96 - 5|= 91. Укажите минимальное число M, при котором для N = 120 получается R = 29.