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

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a. Если количество единиц четное дописывается единица слева и два нуля справа,

b. Если количество единиц нечетное дописывается 10 слева и 1 справа.

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

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

1. Сумма разрядов равна 45.

1. Двоичная запись числа 45 = 101101₂.

2. Число единиц четное, следовательно, получаем 1+101101+00.

3. На экран выводится число 436 = 110110100₂.

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

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

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

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

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

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

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

2. Число единиц нечетное, следовательно слева дописываем две единицы слева – 11 + 1101 = 111101.

3. На экран выводится число 61 = 111101₂.

Для какого наименьшего значения N результат работы автомата – число, не меньшее 412?

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

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

2. К полученной записи дописываются разряды. Если число четное, слева дописывается 1, а справа – 10, если число нечетное – слева дописывается 11 и справа 0.

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

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

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

2. Число нечетное, следовательно слева дописываем 11, справа 0 – 11+1101+0 = 1111010.

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

Сколько различных результатов, принадлежащих отрезку [800; 1500], может быть получено в результате работы автомата?

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

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

2. К полученной записи дописываются разряды. Если число четное, слева дописывается 1, а справа – 11, если число нечетное – слева дописывается 11 и справа 0.

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

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

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

2. Число нечетное, следовательно слева дописываем 11, справа 0 – 11+1101+0 = 1111010.

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

Сколько существует значений N, для которых в результате работы автомата на экране появляется число из отрезка [500; 1000]?

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

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

2. К полученной записи дописываются разряды. Если число четное, слева дописывается 10, а справа – 1, если число нечетное – слева дописывается 1 и справа 01.

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

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

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

2. Число нечетное, следовательно слева дописываем 1, справа 01 – 1+1101+01 = 1110101.

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

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