Число шагов алгоритма: задания с разбором — ЕГЭ по информатике

ЕГЭ Информатика

ЕГЭ по информатике, тема «Число шагов алгоритма». Ответ проверяется на странице, разбор открывается сразу.

Пример 1

Алгоритм начинает работу с числа 54 и на каждом шаге вычитает из него 9. Как только получится 0, алгоритм останавливается. Сколько шагов он сделает?

Ответ и разбор

Ответ: 6

Один шаг уменьшает число ровно на 9, а пройти надо весь путь от 54 до 0.
Значит, шагов столько, сколько раз 9 укладывается в 54: 54 : 9 = 6.

Проверка по цепочке: 54 → 45 → 36 → 27 → 18 → 9 → 0.
Чисел в цепочке 7, а шагов на одно меньше — 6: само 54 записано ещё до первого шага. Поэтому 7 — это отвлекающий ответ, посчитанные числа вместо шагов.
Второе отвлекающее число — 45: столько останется после первого шага. Спрашивают не остаток, а сколько раз повторится вычитание.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-obratnogo-otscheta-1m32x0j

Ещё задания — ниже. Открыть тренажёр

Символы CR и LF в ASCII изначально описывают разные движения печатающего устройства: возврат к началу строки и переход на следующую строку. Поэтому перевод строки может состоять из двух управляющих знаков. Они есть в данных, хотя не печатаются как обычные буквы.

Все карточки предмета — в разделе «Формулы»

Ещё задания

Пример 2

Число n = 132 обрабатывают так: пока n больше 0, выполняется шаг — если n чётное, его делят на 2, иначе из него вычитают 1. Сколько шагов будет выполнено?

Ответ и разбор

Ответ: 9

Трасса: 132 → 66 → 33 → 32 → 16 → 8 → 4 → 2 → 1 → 0 — 9 шагов.

Проверка по двоичной записи: 132 = 10000100₂ — 8 цифр, из них 2 единицы. Деление на 2 стирает последний 0, вычитание 1 превращает последнюю 1 в 0, поэтому шагов (8 − 1) + 2 = 9.

Ответ: 9.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-chet-nechet-pyv3j2

Пример 3

Алгоритм получает на вход натуральное число n и, пока n больше 1, повторяет шаг: если n чётное, n делится на 2, иначе из n вычитается 1. Сколько существует натуральных чисел n, не превышающих 511, для которых алгоритм выполнит ровно 9 шагов?

Ответ и разбор

Ответ: 54

Посмотрим на двоичную запись n. Деление чётного числа на 2 стирает последнюю цифру 0, вычитание 1 из нечётного превращает последнюю 1 в 0. Поэтому каждая единица записи даёт один шаг «вычесть 1», а каждая цифра, кроме старшей, — один шаг «разделить на 2»; при «пока n больше 1» последняя единица (само число 1) не вычитается. Если в записи L цифр и e единиц, шагов (L − 1) + (e − 1).
Числа, не превышающие 511 = 2⁹ − 1, — это записи длиной не больше 9 цифр. Нужно (L − 1) + (e − 1) = 9, причём 1 ≤ e ≤ L (старшая цифра — единица, единиц не больше, чем цифр).
L = 6: e = 5 — старшая единица и ещё 4 единицы на 5 местах: C(5, 4) = 5;
L = 7: e = 4 — старшая единица и ещё 3 единицы на 6 местах: C(6, 3) = 6 · 5 · 4 : 6 = 20;
L = 8: e = 3 — старшая единица и ещё 2 единицы на 7 местах: C(7, 2) = 7 · 6 : 2 = 21;
L = 9: e = 2 — старшая единица и ещё 1 единица на 8 местах: C(8, 1) = 8;
при L = 5 понадобилось бы 6 единиц — больше, чем цифр.
Всего: 5 + 20 + 21 + 8 = 54.

Ответ: 54.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-po-dvoichnoy-zapisi-df83m

Пример 4

Алгоритм получает на вход натуральное число n и, пока n больше 0, повторяет шаг: если n чётное, n делится на 2, иначе из n вычитается 1. Укажите наименьшее натуральное число n, для которого алгоритм выполнит ровно 10 шагов.

Ответ и разбор

Ответ: 47

Посмотрим на двоичную запись n. Деление чётного числа на 2 стирает последнюю цифру 0, вычитание 1 из нечётного превращает последнюю 1 в 0. Поэтому каждая единица записи даёт один шаг «вычесть 1», а каждая цифра, кроме старшей, — один шаг «разделить на 2». Если в записи L цифр и e единиц, шагов (L − 1) + e.
Чем короче запись, тем меньше число. При длине L единиц не больше L, поэтому шагов не больше (L − 1) + L = 2L − 1; нужно 2L − 1 ≥ 10, значит L ≥ 6.
При L = 6: e = 5. Наименьшее такое число — старшая единица, за ней нули, а остальные 4 единицы — в младших разрядах: 101111₂ = 32 + 15 = 47.

Ответ: 47.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-po-dvoichnoy-zapisi-8dqvbe

Пример 5

Алгоритм начинает работу с числа 20 и на каждом шаге вычитает из него 4. Как только получится 0, алгоритм останавливается. Сколько шагов он сделает?

Ответ и разбор

Ответ: 5

Один шаг уменьшает число ровно на 4, а пройти надо весь путь от 20 до 0.
Значит, шагов столько, сколько раз 4 укладывается в 20: 20 : 4 = 5.

Проверка по цепочке: 20 → 16 → 12 → 8 → 4 → 0.
Чисел в цепочке 6, а шагов на одно меньше — 5: само 20 записано ещё до первого шага. Поэтому 6 — это отвлекающий ответ, посчитанные числа вместо шагов.
Второе отвлекающее число — 16: столько останется после первого шага. Спрашивают не остаток, а сколько раз повторится вычитание.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-obratnogo-otscheta-14blw6l

Пример 6

Число n = 863 обрабатывают так: пока n больше 0, выполняется шаг — если n чётное, его делят на 2, иначе из него вычитают 1. Сколько шагов будет выполнено?

Ответ и разбор

Ответ: 17

Трасса: 863 → 862 → 431 → 430 → 215 → 214 → 107 → 106 → 53 → 52 → 26 → 13 → 12 → 6 → 3 → 2 → 1 → 0 — 17 шагов.

Проверка по двоичной записи: 863 = 1101011111₂ — 10 цифр, из них 8 единиц. Деление на 2 стирает последний 0, вычитание 1 превращает последнюю 1 в 0, поэтому шагов (10 − 1) + 8 = 17.

Ответ: 17.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-chet-nechet-1vk1ml5

Пример 7

Алгоритм получает на вход натуральное число n и, пока n больше 1, повторяет шаг: если n чётное, n делится на 2, иначе из n вычитается 1. Сколько существует натуральных чисел n, не превышающих 63, для которых алгоритм выполнит ровно 7 шагов?

Ответ и разбор

Ответ: 14

Посмотрим на двоичную запись n. Деление чётного числа на 2 стирает последнюю цифру 0, вычитание 1 из нечётного превращает последнюю 1 в 0. Поэтому каждая единица записи даёт один шаг «вычесть 1», а каждая цифра, кроме старшей, — один шаг «разделить на 2»; при «пока n больше 1» последняя единица (само число 1) не вычитается. Если в записи L цифр и e единиц, шагов (L − 1) + (e − 1).
Числа, не превышающие 63 = 2⁶ − 1, — это записи длиной не больше 6 цифр. Нужно (L − 1) + (e − 1) = 7, причём 1 ≤ e ≤ L (старшая цифра — единица, единиц не больше, чем цифр).
L = 5: e = 4 — старшая единица и ещё 3 единицы на 4 местах: C(4, 3) = 4;
L = 6: e = 3 — старшая единица и ещё 2 единицы на 5 местах: C(5, 2) = 5 · 4 : 2 = 10;
при L = 4 понадобилось бы 5 единиц — больше, чем цифр.
Всего: 4 + 10 = 14.

Ответ: 14.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-po-dvoichnoy-zapisi-1j9eh9e

Пример 8

Алгоритм начинает работу с числа 12 и на каждом шаге вычитает из него 3. Как только получится 0, алгоритм останавливается. Сколько шагов он сделает?

Ответ и разбор

Ответ: 4

Один шаг уменьшает число ровно на 3, а пройти надо весь путь от 12 до 0.
Значит, шагов столько, сколько раз 3 укладывается в 12: 12 : 3 = 4.

Проверка по цепочке: 12 → 9 → 6 → 3 → 0.
Чисел в цепочке 5, а шагов на одно меньше — 4: само 12 записано ещё до первого шага. Поэтому 5 — это отвлекающий ответ, посчитанные числа вместо шагов.
Второе отвлекающее число — 9: столько останется после первого шага. Спрашивают не остаток, а сколько раз повторится вычитание.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-obratnogo-otscheta-883d9n

Пример 9

Число n = 661 обрабатывают так: пока n больше 0, выполняется шаг — если n чётное, его делят на 2, иначе из него вычитают 1. Сколько шагов будет выполнено?

Ответ и разбор

Ответ: 14

Трасса: 661 → 660 → 330 → 165 → 164 → 82 → 41 → 40 → 20 → 10 → 5 → 4 → 2 → 1 → 0 — 14 шагов.

Проверка по двоичной записи: 661 = 1010010101₂ — 10 цифр, из них 5 единиц. Деление на 2 стирает последний 0, вычитание 1 превращает последнюю 1 в 0, поэтому шагов (10 − 1) + 5 = 14.

Ответ: 14.

Нашли ошибку? Напишите нам, код задания: ege-informatics-shagi-chet-nechet-dlwoth

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.