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

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

1. Строится шестнадцатеричная запись числа N // 2, где "//" - операция деления нацело.

2. К этой записи дописывается ещё три разряда по следующему правилу: если N не делится на 4, то слева к нему приписывается "F", а справа - "A0". В противном случае слева приписывается "15", а справа "C".

Например, N = 4₁₀ => 2₁₆ => 152C₁₆ = 5420₁₀ = R.

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

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

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

2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "2", а справа - "11". В противном случае слева приписывается "13", а справа "02".

Например, N = 45₁₀ = 231₄ => 223111₄ = 2773₁₀ = R

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

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

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

2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "10", а справа - "11". В противном случае слева приписывается "1", а справа "00".

Например, N = 5₁₀ = 101₂ => 1010111₂ = 87₁₀ = R

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

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

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

2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "1", а справа - "11". В противном случае слева приписывается "11", а справа "00".

Например, N = 5₁₀ = 101₂ => 110111₂ = 55₁₀ = R

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

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

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

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

3. К полученной записи повторно применяется алгоритм п. 2.

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

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

1) Число N переводим в двоичную запись.

2) Инвертируем все биты числа кроме первого.

3) Переводим в десятичную запись.

4) Складываем результат с исходным числом N.

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

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1.

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

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

4) Число, полученное на шаге 3, считается результатом работы алгоритма.

Сколько существует различных натуральных чисел N, при обработке которых получится R = 8?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1.

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

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

4) Число, полученное на шаге 3, считается результатом работы алгоритма.

Сколько существует различных натуральных чисел N, при обработке которых получится R = 6?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

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

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

4) Число, полученное на шаге 3, считается результатом работы алгоритма.

Сколько существует различных натуральных чисел N, при обработке которых получится R = 6?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

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

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

4) Число, полученное на шаге 3, считается результатом работы алгоритма.

Сколько существует различных натуральных чисел N, при обработке которых получится R = 2?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

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

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

4) Число, полученное на шаге 3, считается результатом работы алгоритма.

Сколько существует различных натуральных чисел N, при обработке которых получится R = 3?

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

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

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

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

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

Для скольких значений N в результате работы алгоритма получится число 127?

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

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

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

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

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

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

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

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

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

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

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

Для какого максимального значения N в результате работы алгоритма получится число 119?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

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

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

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

Сколько различных чисел, принадлежащих отрезку [50; 80], может получиться в результате работы автомата?

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

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

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

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

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

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

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.

3. Шаг 2 повторяется ещё два раза.

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

При каком наименьшем исходном числе N > 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.

3. Шаг 2 повторяется ещё два раза.

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

При каком наибольшем исходном числе N < 500 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.

3. Шаг 2 повторяется ещё два раза.

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

При каком наибольшем исходном числе N < 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8?

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.

3. Шаг 2 повторяется ещё два раза.

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

При каком наибольшем исходном числе N < 750 в результате работы алгоритма получится чётное число, которое не делится на 4?