Число шагов алгоритма: задания с разбором — ЕГЭ по информатике
ЕГЭ Информатика
ЕГЭ по информатике, тема «Число шагов алгоритма». Ответ проверяется на странице, разбор открывается сразу.
Пример 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
Ещё задания — ниже. Открыть тренажёр

Все карточки предмета — в разделе «Формулы»
Ещё задания
Пример 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
Рядом
Продолжить тренировку
Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

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