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

(Е. Джобс) На вход алгоритма подаётся натуральное число 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. Если число N не делится на 2, все цифры двоичной записи инвертируются (0 заменяется на 1 и наоборот).

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

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

Например, для числа 6 двоичная запись 110₂ преобразуется в запись 111100₂ = 60, для числа 5 двоичная запись 101₂ преобразуется в 1100₂ = 12. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее чем 60.

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

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

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

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

Например, для числа 12 двоичная запись 1100₂ преобразуется в запись 1100100₂ = 100, для числа 4 двоичная запись 100₂ преобразуется в 10011₂ = 19. Укажите максимальное возможное значение R, меньшее 170, которое может быть получено с помощью этого алгоритма. В ответе запишите это число в десятичной системе счисления.

(Е. Джобс) На вход алгоритма подаётся натуральное число 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. В ответе это число запишите в десятичной системе счисления.

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

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

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

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

Например, для исходного числа 12 = 1100₂ результатом является число 111000₂ = 56, а для исходного числа 5 = 101₂ результатом является число 10100₂ = 20. Укажите число N, после обработки которого с помощью этого алгоритма получается минимальное число R, большее 100.

(М. Гутров) Многие целые числа можно превратить в палиндром после неоднократного сложения самого числа и его инвертированной копии. Например, для числа 254 нужно 3 итерации чтобы оно стало палиндромом: 254 + 452 = 706, 706 + 607 = 1313, 1313 + 3131 = 4444.

В диапазоне чисел от 100 до 200 найдите количество чисел, которые могут быть превращены в палиндром не более чем за 5 итераций.

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

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

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

3. Шаг 2 повторяется.

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

Например, для исходного числа 12 = 1100₂ результатом является число 110000₂ = 48, а для исходного числа 4 = 100₂ результатом является число 10010₂ = 18. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 100.

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

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

2. Если число N делится на 6, в конец двоичной записи дописывается двоичный код числа 7, иначе дописывается единица.

3. Если число, полученное после шага 2, делится на 3, в конец двоичной записи дописывается двоичный код числа 5, иначе дописывается единица.

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

Например, для исходного числа 12₁₀ = 1100₂ (делится на 6) после шага 2 получается число 1100111₂ = 103₁₀ (не делится на 3), а после шага 3 – число 11001111₂ = 207₁₀. Определите наименьшее возможное значение N, для которого в результате работы алгоритма получается R > 300000.

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

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

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

3. Если число, полученное после шага 2, делится на 5, в конец двоичной записи дописывается двоичный код числа 5, иначе дописывается единица.

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

Например, для исходного числа 14₁₀ = 1110₂ (делится на 7) после шага 2 получается число 1110111₂ = 119₁₀ (не делится на 5), а после шага 3 – число 11101111₂ = 239₁₀. Определите наименьшее возможное значение N, для которого в результате работы алгоритма получается R > 500000.

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

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

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

3. Если число, полученное после шага 2, делится на 5, в конец двоичной записи дописывается двоичный код числа 5, иначе дописывается единица.

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

Например, для исходного числа 7₁₀ = 111₂ (не делится на 3) после шага 2 получается число 1111₂ = 15₁₀ (делится на 5), а после шага 3 – число 1111101₂ = 125₁₀. Определите наибольшее возможное значение N, для которого в результате работы алгоритма получается R < 10₆.

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

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

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

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

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

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

Например, для исходного числа 10₁₀ = 101₃ результатом является число 10101₃ = 91₁₀, а для исходного числа 11₁₀ = 102₃ результатом является число 10210₃ = 102₁₀.

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

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

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

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

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

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

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

Например, для исходного числа 11₁₀ = 1011₂ результатом является число 10110₂ = 22₁₀, а для исходного числа 20₁₀ = 10100₂ результатом является число 101000100₂ = 324₁₀.

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

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

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

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

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

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

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 10011₂ = 19₁₀.

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

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

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

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

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

б) если N не делится на 4, то остаток от деления N на 4 умножается на 2 в двоичной системе счисления и дописывается в начало двоичной записи числа N.

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 110000₂ = 48₁₀, а для исходного числа 10₁₀ = 1010₂ результатом является число 1001010₂ = 74₁₀.

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

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

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

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

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

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

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 11001010₂ = 202₁₀, а для исходного числа 10₁₀ = 1010₂ результатом является число 1010010₂ = 82₁₀.

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

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

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

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

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

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

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 10011₂ = 19₁₀.

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

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

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

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

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

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

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

Например, для исходного числа 6₁₀ = 110₂ результатом является число 1010₂ = 10₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 10011₂ = 19₁₀.

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

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

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

2. В конец записи (справа) дописывается остаток от деления числа N на 3, а в начало записи (слева) остаток от деления N на 2.

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

Пример. Дано число N=23. Алгоритм работает следующим образом: 23 113₄ 11132₄ 350₁₀.

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