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

(Е. Джобс) Автомат получает на вход четырехзначное число. По этому числу строится новое число по следующим правилам.

1. Перемножаются первая и вторая, а также третья и четвертая цифры исходного числа.

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

Пример. Исходное число: 5431. Произведения: 5 · 4 = 20; 3 · 1 = 3. Результат: 320.

Укажите максимальное число, в результате обработки которого, автомат выдаст число 1214.

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

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

2. Все нечётные цифры записи заменяются на 2.

3. К строке приписывается остаток от деления числа N на 8.

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

5. Затем действия 1-4 повторяются ещё один раз.

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

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

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

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

2. Все чётные цифры записи заменяются на 1.

3. К строке приписывается остаток от деления числа N на 8.

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

5. Затем действия 1-4 повторяются ещё один раз.

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

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

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

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

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

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

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

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

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

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

2. К этой записи дописываются разряды по следующему правилу. Если количество четных цифр в полученной записи больше чем нечетных, слева дописывается 22, иначе 11.

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

Например, для числа 18 троичная запись 200₃ преобразуется в запись 22200₃ = 234, для числа 22 троичная запись 211₃ преобразуется в 11211₃ = 130.

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

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

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

2. К этой записи дописываются разряды по следующему правилу. Если сумма троичных разрядов кратна 3, слева дописывается 20, иначе слева дописывается 10.

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

Например, для числа 10 троичная запись 101₃ преобразуется в запись 10101₃ = 91, для числа 11 троичная запись 102₃ преобразуется в 20102₃ = 173.

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

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

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

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

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

б) если число N на 15 не делится, то остаток от его деления на 15 умножается на 13, переводится в систему счисления с основанием 15 и дописывается в конец числа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Строится число K из цифр числа N, расположенных в порядке невозрастания.

2) Строится число M из цифр числа N, расположенных в порядке неубывания.

3) Число R вычисляется как разность K – M.

Найдите минимальное число N, для которого число R, полученное в результате работы алгоритма, равно 6174 (постоянной Капрекана), и при этом число K максимально возможное.

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

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

2. Цифры числа нумеруются слева направо, начиная с единицы. Отдельно складываются цифры, стоящие на чётных местах, и цифры, стоящие на нечётных местах.

3. Запись меньшей из сумм в системе счисления с основанием 45 приписывается в начало числа, запись большей из сумм в системе счисления с основанием 45 – в конец. В случае появления ведущего нуля, он игнорируется.

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

Пример. Алгоритм получает число N = 95₁₀ = 25₄₅. Цифра 2 стоит на позиции № 1, цифра 5 – на позиции № 2. Сумма цифр на чётных местах равна 5₄₅, сумма цифр на нечётных местах равна 2₄₅.

Приписывая цифры, получаем число 2255₄₅ = 186530₁₀.

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

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

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

2. Отдельно складываются чётные и нечётные цифры числа. Если чётных или нечётных чисел нет, сумма считается равной нулю.

3. У большей из сумм определяется последняя цифра в системе счисления с основанием 80. Эта цифра приписывается в конец восьмидесятеричной записи числа N.

4. Пункты 2 и 3 повторяются ещё один раз.

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

Пример. Алгоритм получает число N = 83₁₀ = 13₈₀. Сумма чётных цифр принимается равной нулю (их нет в записи числа), сумма нечётных цифр равна 4 > 0. Число 4₁₀ = 4₈₀ – заканчивается на цифру 4 в системе счисления с основанием 80; приписываем её к 13₈₀, получаем 134₈₀. Теперь обе суммы равны 4, поэтому в конец приписывается ещё одна цифра 4, получаем 1344₈₀ = 531524₁₀.

Определите наименьшее число N, при котором результат работы алгоритма R будет больше 1 000 000₁₀. В ответе запишите это число в десятичной системе счисления.

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

1. Если число N четное, то оно делится на 2, иначе из него вычитается 1.

2. Если полученное на предыдущем шаге число кратно 6, то оно делится на 6, иначе из него вычитается 1.

3. Если полученное на предыдущем шаге число кратно 15, то оно делится на 15, иначе из него вычитается 1. Это число считается результатом работы алгоритма R.

Найдите минимальное число N, шестнадцатеричная запись которого содержит цифру 'С', а соответствующее число R равно 523.

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

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

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

Укажите сумму наименьшего и наибольшего чисел N, при которых получается R = 317.

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

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

2. Если число N делится на 3, к троичной записи слева приписывается 1, а справа – 02; иначе остаток от деления числа на 3 умножается на 4, переводится в троичную систему и дописывается в конец троичной записи.

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

Например, для числа 11 троичная запись 102₃ преобразуется в запись 10222₃ = 107, для числа 12 троичная запись 110₃ преобразуется в 111002₃ = 353. Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 199.

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

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

2. Если число N делится на 3, к троичной записи справа дописываются две её последние цифры, иначе остаток от деления числа на 3 умножается на 5, переводится в троичную систему и дописывается в конец троичной записи.

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

Например, для числа 11 троичная запись 102₃ преобразуется в запись 102101₃ = 307, для числа 12 троичная запись 110₃ преобразуется в 11010₃ = 111. Укажите минимальное значение R, большее чем 133, которое может быть результатом работы алгоритма.

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

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

2. Если число N делится на 2, к двоичной записи справа дописывается 0, иначе справа дописывается 1.

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

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

Например, для числа 13 двоичная запись 1101₂ преобразуется в запись 110111₂ = 55, для числа 10 двоичная запись 1010₂ преобразуется в 101000₂ = 40. Укажите минимальное значение R, большее чем 2023, которое может быть результатом работы алгоритма.

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

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

2. К этой записи дописываются разряды по следующему правилу. Если число кратно 3, то справа дописывается 010, иначе справа дописывается двоичная запись результата умножения 5 на остаток от деления числа N на 3.

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

Например, для числа 13 двоичная запись 1101₂ преобразуется в запись 1101101₂ = 109, для числа 9 двоичная запись 1001₂ преобразуется в 1001010₂ = 74. Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.

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

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

2. К этой записи дописываются разряды по следующему правилу. Если число кратно 5, то слева дописывается 1, справа две последние цифры (младшие разряды). Иначе слева дописывается двоичное представления остатка от деления числа на 5.

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

Например, для числа 13 = 1101₂ получается 111101₂ = 61, для числа 10 = 1010₂ получается 1101010₂ = 106. Укажите максимальное число R, не превышающее 223, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

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

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

2. К этой записи дописываются разряды по следующему правилу. Если сумма двоичных разрядов кратна 4, слева дописывается 10, иначе 11.

3. К полученной записи справа дописывается еще один разряд – 0, если полученное двоичное число нечетное, 1 в обратном случае.

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

Например, для числа 13 = 1101₂ получается 1111010₂ = 122, для числа 10 = 1010₂ получается 1110101₂ = 117. Укажите максимальное число N, для которого значение R не превышает 250. В ответе это число запишите в десятичной системе счисления.