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

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

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

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

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

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

Полученная таким образом запись является тринадцатеричной записью искомого числа R. Например, для исходного числа 77 = 5C₁₃ результатом является число 5C48₁₃ = 13073. Укажите число N, после обработки которого с помощью этого алгоритма получается наибольшее число R, меньшее 6000.

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

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

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

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

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

Полученная таким образом запись является восьмеричной записью искомого числа R. Например, для исходного числа 17 = 21₈ результатом является число 211₈ = 137, а для исходного числа 25 = 31₈ это число 3313₈ = 1739. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 1100.

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

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

2. Все разряды двоичной записи инвертируются (0 заменяется на 1, 1 на 0).

3. Если полученное число кратно 5, то в двоичной записи старшие три разряда заменяются на 100, в противном случае в двоичной записи старшие три разряда заменяются на 101.

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

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

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

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

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

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

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

Например, исходное число 4₁₀ = 11₃ преобразуется в число 11100₃ = 117₁₀, а исходное число 7₁₀ = 21₃ преобразуется в число 2110₃ = 66₁₀.

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

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

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

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

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

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

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

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

Пример. Число 11₁₀ = 15₆ не делится на 3, поэтому в конец его шестеричной записи 15₆ дописывается шестеричная запись числа (11 mod 6) · 10 = 20 = 32₆, так что результатом работы автомата является число 1532₆ = 416₁₀. Исходное число 12₁₀ = 20₆ делится на 3, поэтому в конец шестеричной записи 20₆ дописываются её две первых цифры 20, так что результатом работы автомата является число 2020₆ = 444₁₀.

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

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

1. Находится сумма разрядов числа N.

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

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

(a) Если количество единиц четное дописывается единица слева и два нуля справа,

(b) Если количество единиц нечетное дописывается 10 слева и 1 справа.

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

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

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

1. Сумма разрядов 45.

2. Двоичная запись 101101.

3. Единиц четное количество, следовательно, получаем 1+101101+00 = 110110100.

4. 110110100₂ = 436.

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

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

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

2. В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается.

3. Запись записывается справа налево (в обратную сторону).

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

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

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

2. К полученной записи дописываются разряды. Если в числе четное количество единиц,

слева дописывается 1 справа два нуля, если нечетное – слева две единицы.

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

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

1. Двоичная запись числа N: 1101.

2. Число нечетное, следовательно, слева дописываем две единицы слева – 11 + 1101 = 111101.

3. На экран выводится число 111101₂ = 61.

В результате работы автомата на экране появилось число, не меньшее 412. Для какого наименьшего значения N данная ситуация возможна?

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

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

2. Из полученной записи убирается старшая (левая) единица.

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

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

b) если количество единиц нечётное, слева дописывается 1, справа 0.

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

Например, для исходного числа 4 = 100₂ результатом будет являться число 8 = 1000₂, а

для исходного числа 6 = 110₂ результатом будет являться число 12 = 1100₂.

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

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

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

2. Складываются все цифры полученной двоичной записи. Если сумма четная в конец дублируются два младших разряда, если нечетная – в конец дописываются проинвертированные два младших разряда.

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

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

1. Двоичная запись числа N: 1101

2. Число единиц нечетное, следовательно, дописываем инвертированные два младших разряда – 1101 + 10 = 110110₂ = 54₁₀.

В результате работы автомата на экране появилось число, большее 154. Для какого наименьшего значения N это возможно?

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

1. Строится двоичная запись числа N без ведущих нулей.

2. Если в полученной записи единиц больше, чем нулей, то справа приписывается ноль. Иначе справа приписывается две единицы.

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

Найдите наименьшее число N, после обработки которого автомат выдаст результат больший 2019.

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

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

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

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

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

1. Двоичная запись числа N: 13 = 1101.

2. Сумма цифр двоичной записи 3, число нечетное. Значит получается число 110111.

3. 110111₂ = 55₁₀.

Найдите наименьшее число N, для которого результат работы автомата больше, чем 102.

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

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

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

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

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

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

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

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

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

2. Полученная запись переворачивается (записывается слева направо).

3. В полученной записи дублируется младший (правый) бит.

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

Например, для числа 11 алгоритм будет выполняться следующим образом:

1. 11 = 1011₂

2. 1101₂

3. 11011₂ = 27₁₀

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

В ответе запишите это число в десятичной системе.

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

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

2. Все разряды полученного числа инвертируются.

3. К полученному результату справа дописывается бит четности: 0, если в двоичном коде, полученном после шага 2, было четное число единиц, и 1, если нечетное.

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

N) является двоичной записью искомого числа R.

Например, для числа 60 алгоритм будет выполняться следующим образом:

1. N = 60 = 111100₂

2. 000011₂

3. 0000110₂ = 6₁₀

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

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

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

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

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

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

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

Например, для числа 60 алгоритм будет выполняться следующим образом:

1. N = 60 = 111100₂

2. 1111000₂ (4 единицы → дописываем 0)

3. 11110001₂ (N - четное → дописываем 1) = 241₁₀

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

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