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

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

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

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

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

б) если сумма цифр троичной записи не кратна 3, то к записи справа приписывается 101, а затем первые 2 разряда меняются на 22.

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

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

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

2) Полученная запись преобразуется по следующему алгоритму:

а) если сумма значений цифр 19-ричной записи чётная, то последняя цифра перемещается в начало, а справа дописывается 1;

б) если сумма значений цифр 19-ричной записи нечётная, то первая цифра перемещается в конец, а слева дописывается B.

Полученная таким образом запись является 19-ричной записью искомого числа R. Найдите количество чисел N, принадлежащих отрезку [1;10000], для которых результат работы алгоритма кратен либо 5, либо 3, но не обоим числам одновременно.

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

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

2) Полученная запись преобразуется по следующему алгоритму:

а) если запись содержит чётное число разрядов, то число делится посередине на две равные части, вначале записывается вторая часть, а после – первая;

б) если получившаяся запись содержит нечётное число разрядов, то справа дописывается последняя цифра 20-ричной записи числа N.

Полученная таким образом запись является 20-ричной записью искомого числа R. Например, для исходного числа 1 результат работы алгоритма – 21, а для 20 результат работы алгоритма – 1.

Укажите минимальное число N такое, что результат работы алгоритма превышает 190.

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

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

2) Каждая цифра этой записи увеличивается на 1, а если числовое значение цифры уже равно 19, то такая цифра заменяется на 0.

3) В начало числа записывается последняя цифра двоичной записи числа N.

4) Из записи удаляются незначащие нули.

Полученная таким образом запись является 20-ричной записью искомого числа R. Например, для исходного числа 265 = D5₂₀ результатом является число 1E6₂₀ = 686, а для исходного числа 66 = 36₂₀ результатом является число 47₂₀ = 87. Найдите наименьшее число N, такое что 20-ричная запись результата работы алгоритма R содержит не менее трёх разрядов и хотя бы два из них записываются латинскими буквами.

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

1) Число переводится в семеричную систему счисления.

2) Полученная запись преобразуется по следующему алгоритму:

а) если N чётное, то справа дописывается 1, а слева – 52;

б) если N нечётное, то первая и последняя цифры в числе меняются местами, а затем справа дописывается 15.

3) Из записи удаляются незначащие нули.

Полученная таким образом запись является семеричной записью искомого числа R. Укажите максимальное число N, не превышающее 1000, после обработки которого с помощью этого алгоритма получается число R, семеричная запись которого содержит ровно 4 значащих цифры.

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

1) Число переводится в пятеричную систему счисления.

2) Полученная запись преобразуется по следующему алгоритму:

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

б) если N нечётное, то первая и последняя цифры в числе меняются местами, а затем справа дописывается 1.

3) Из записи удаляются незначащие нули.

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

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

1) Число переводится в четверичную систему счисления.

2) Полученная запись преобразуется по следующему алгоритму:

а) если число чётное, то слева дописывается 12, а справа – утроенное значение младшего разряда четверичной записи в четверичной системе счисления;

б) если число нечётное, то слева дописывается 13, а справа – 21.

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

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

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

2. Подсчитывается количество единиц и количество нулей в полученной двоичной записи.

3. Эти числа переводятся в двоичную систему и записываются друг за другом без использования ведущих нулей: сначала количество нулей, затем количество единиц.

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

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

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

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

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

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

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

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

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

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

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

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

1. Число N переводится в систему счисления с основанием 30.

2. Вычисляет сумма значений цифр данного числа в 30-ричной системе счисления.

3. Число R определяется как полученная сумма, умноженная на значение последней десятичной цифры числа N.

Найдите количество чисел N, меньших 10₇, для которых соответствующее значение R – не простое число.

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

1. Число N переводится в систему счисления с основанием 30.

2. Вычисляет сумма значений цифр данного числа в 30-ричной системе счисления.

3. Число R определяется как полученная сумма, умноженная на значение последней десятичной цифры числа N.

Найдите количество чисел N, меньших 1000, для которых соответствующее значение R – не простое число.

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

1. Число N переводится в систему счисления с основанием 19.

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

а) согласные буквы (В, C, D, F, G, H) заменяются на 5;

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

в) две последние цифры записи переставляются в начало (например, из строки 12345 получается 45123).

3. Действия а)-в) в п. 2. повторяются еще раз.

Полученная таким образом запись записью искомого числа R в системе счисления с основанием 19. Укажите максимальное число R с суммой цифр, кратной 7, которое может быть получено в результате работы алгоритма. Запишите его в десятичной системе счисления.

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

1. Число N переводится в двадцатеричную систему счисления.

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

а) гласные буквы (A, E, I) заменяются на 1;

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

в) первая цифра переставляется в конец записи.

3. Действия а)-в) в п. 2. повторяются еще раз.

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

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

1. Если в числе N четных чисел больше, то вычисляется сумма всех четных цифр числа N, иначе вычисляется сумма всех нечетных цифр числа N.

2. Если на предыдущем шаге получилось четное число, то к нему справа приписывается максимальная четная цифра числа N, иначе слева приписывается минимальная нечетная цифра числа N.

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

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

1. Из всех четных цифр числа N составляется наибольшее число.

2. Из всех нечетных цифр числа N составляется наименьшее число.

3. Вычисляется сумма полученных двух чисел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) если число N четное, то слева дописывается 2, а справа – удвоенное значение младшего разряда в троичной системе счисления;

б) если число N нечетное, то справа дописывается 2, а слева – удвоенное значение старшего разряда в троичной системе счисления.

Полученная таким образом запись является троичной записью искомого числа R. Например, для исходного числа 14 = 112₃ результатом является 211211₃ = 616. Укажите минимальное значение большее 100, которое может получиться в результате работы алгоритма.

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

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

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

а) если N делится на 12, то в конец этой записи дописываются три её последние цифры;

б) если число N на 12 не делится, то остаток от деления умножается на 3, переводится в двенадцатеричную запись и дописывается в начало числа.

Полученная таким образом запись является двенадцатеричной записью искомого числа R. Например, для исходного числа 204 = 150₁₂ результатом является число 150150₁₂ = 352716, а для исходного числа 275 = 1AB₁₂ это число 291AB₁₂ = 57299. Укажите такое число N, после обработки которого с помощью этого алгоритма получится наибольшее число R, которое меньше 58000.