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

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

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

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

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

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

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

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

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

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

3. Пункт 2 выполняется повторно.

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

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

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

2. К этой записи дописывается справа бит четности: 0, если в двоичном коде числа N было

четное число единиц, и 1, если нечетное.

3. К полученному результату дописывается еще один бит четности.

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

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

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

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

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

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

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

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, которое может быть результатом работы алгоритма.