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

(А. Богданов) Назовём битом чётности остаток от деления числа единиц двоичной записи на 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. В ответе запишите это число в десятичной системе счисления.

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

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

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

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

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

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

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

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

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

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

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

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

Например, исходное число 4₁₀=100₂ преобразуется число 11000₂ = 48₁₀, а исходное число 13₁₀ = 1101₂ преобразуется в число 110111₂ = 55₁₀. Укажите такое число N большее 8, для которого число R является наименьшим среди чисел, превышающих 88. В ответе это число запишите в десятичной системе счисления.

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

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

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

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

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

3. Для полученной записи повторно выполняется п. 2.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите минимальное число R, большее, чем 1500, которое может получится в результате работы алгоритма.

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

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

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

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

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

3. Пункт 2 повторяется ещё раз для записи, полученной после второго пункта.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите максимальное число R, меньшее, чем 1500, которое может получится в результате работы алгоритма.

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

1. Каждая цифра числа N записывается с помощью 4-битного двоичного кода. В конец кода каждой цифры добавляется бит чётности так, чтобы количество единиц в расширенной записи стало чётным.

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

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

Например, для числа 13 двоичные коды цифр: 1 = 0001₂, 3 = 0011₂. С добавленными битами чётности: 00011 и 00110, результат шага 1: 0001100110. Заменяем два левых разряда на 1 и добавляем справа 0: 1011001100₂ = 716.

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

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то 4 младших бита инвертируются, т.е. 0 изменяется на 1, а 1 на 0;

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

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

Например, для исходного числа 36₁₀ = 100100₂. результатом является число 43₁₀ = 101011₂ а для исходного числа 37₁₀ = 100101₂ результатом является число 59₁₀ = 111011₂. Укажите число N, большее 63, после обработки которого с помощью этого алгоритма получается минимальное число R. В ответе запишите число в десятичной системе счисления.

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

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

2. Строится двоичная запись полученного числа.

3. К полученной записи слева дописывается три младших разряда.

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

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

1. 13 = 1101₂, двоичная запись содержит один 0. 13 – 1 = 12.

2. 12₁₀ = 1100₂

3. 1100 -> 1001100.

4. 1001100₂ = 76

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

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

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

2) Если количество цифр в двоичной записи числа N четно, то справа приписывается 10, если нечётно, то слева приписывается 11.

Полученная таким образом запись является двоичной записью искомого числа R. Найдите количество чисел N из отрезка [100; 200], для которых результат работы компьютера будет четным.