Тренировка · 8–10 класс
Число выполнений вложенного цикла: задачи с решением
Если внутренний цикл зависит от внешнего счётчика, складываем длины внутренних проходов.
На что обратить внимание
Формула n² подходит только для одинаковых n внутренних повторов; здесь число повторов растёт вместе со счётчиком.
Как решать: разобранный пример
Внешний счётчик i принимает целые значения от 1 до 88 включительно. Для каждого i действие выполняется i+1 раз. Сколько всего выполнений действия?
- Первый проход содержит 2 выполнений, последний — 89.
- Сумма i по всем внешним проходам равна 88·(88+1)/2 = 3916.
- Добавка 1 учитывается 88 раз: 1·88 = 88.
- Итог 3916+88 = 4004. Прямая сумма длин внутренних проходов даёт тот же результат.
Ответ: 4004.
Попробуйте самостоятельно
- 1
Внешний счётчик i принимает целые значения от 1 до 88 включительно. Для каждого i действие выполняется i+1 раз. Сколько всего выполнений действия?
Решить и разобрать - 2
Внешний счётчик i принимает целые значения от 1 до 22 включительно. Для каждого i действие выполняется i+47 раз. Сколько всего выполнений действия?
Решить и разобрать - 3
Внешний счётчик i принимает целые значения от 1 до 289 включительно. Для каждого i действие выполняется i+21 раз. Сколько всего выполнений действия?
Решить и разобрать - 4
Внешний счётчик i принимает целые значения от 1 до 277 включительно. Для каждого i действие выполняется i+6 раз. Сколько всего выполнений действия?
Решить и разобрать - 5
Внешний счётчик i принимает целые значения от 1 до 89 включительно. Для каждого i действие выполняется i+4 раз. Сколько всего выполнений действия?
Решить и разобрать - 6
Внешний счётчик i принимает целые значения от 1 до 453 включительно. Для каждого i действие выполняется i+41 раз. Сколько всего выполнений действия?
Решить и разобрать - 7
Внешний счётчик i принимает целые значения от 1 до 377 включительно. Для каждого i действие выполняется i+16 раз. Сколько всего выполнений действия?
Решить и разобрать - 8
Внешний счётчик i принимает целые значения от 1 до 363 включительно. Для каждого i действие выполняется i+2 раз. Сколько всего выполнений действия?
Решить и разобрать - 9
Внешний счётчик i принимает целые значения от 1 до 488 включительно. Для каждого i действие выполняется i+42 раз. Сколько всего выполнений действия?
Решить и разобрать - 10
Внешний счётчик i принимает целые значения от 1 до 9 включительно. Для каждого i действие выполняется i+11 раз. Сколько всего выполнений действия?
Решить и разобрать - 11
Внешний счётчик i принимает целые значения от 1 до 336 включительно. Для каждого i действие выполняется i+30 раз. Сколько всего выполнений действия?
Решить и разобрать - 12
Внешний счётчик i принимает целые значения от 1 до 403 включительно. Для каждого i действие выполняется i+6 раз. Сколько всего выполнений действия?
Решить и разобрать - 13
Внешний счётчик i принимает целые значения от 1 до 444 включительно. Для каждого i действие выполняется i+24 раз. Сколько всего выполнений действия?
Решить и разобрать - 14
Внешний счётчик i принимает целые значения от 1 до 340 включительно. Для каждого i действие выполняется i+37 раз. Сколько всего выполнений действия?
Решить и разобрать - 15
Внешний счётчик i принимает целые значения от 1 до 16 включительно. Для каждого i действие выполняется i+44 раз. Сколько всего выполнений действия?
Решить и разобрать - 16
Внешний счётчик i принимает целые значения от 1 до 264 включительно. Для каждого i действие выполняется i+23 раз. Сколько всего выполнений действия?
Решить и разобрать - 17
Внешний счётчик i принимает целые значения от 1 до 157 включительно. Для каждого i действие выполняется i+37 раз. Сколько всего выполнений действия?
Решить и разобрать - 18
Внешний счётчик i принимает целые значения от 1 до 223 включительно. Для каждого i действие выполняется i+41 раз. Сколько всего выполнений действия?
Решить и разобрать - 19
Внешний счётчик i принимает целые значения от 1 до 227 включительно. Для каждого i действие выполняется i+34 раз. Сколько всего выполнений действия?
Решить и разобрать - 20
Внешний счётчик i принимает целые значения от 1 до 382 включительно. Для каждого i действие выполняется i+5 раз. Сколько всего выполнений действия?
Решить и разобрать - 21
Внешний счётчик i принимает целые значения от 1 до 414 включительно. Для каждого i действие выполняется i+27 раз. Сколько всего выполнений действия?
Решить и разобрать - 22
Внешний счётчик i принимает целые значения от 1 до 45 включительно. Для каждого i действие выполняется i+35 раз. Сколько всего выполнений действия?
Решить и разобрать - 23
Внешний счётчик i принимает целые значения от 1 до 191 включительно. Для каждого i действие выполняется i+48 раз. Сколько всего выполнений действия?
Решить и разобрать - 24
Внешний счётчик i принимает целые значения от 1 до 227 включительно. Для каждого i действие выполняется i+47 раз. Сколько всего выполнений действия?
Решить и разобрать
Частые вопросы
Равно ли число выполнений тела цикла числу операций программы?
Не обязательно. Внутри одного прохода может быть несколько действий, а проверка условия тоже требует работы. Эта семья считает исполнения заданного тела. Вывод о времени программы дополнительно зависит от стоимости действий и реализации.
Как проверить вложенный цикл на коротком ручном прогоне?
Выберите небольшой допустимый предел и выпишите каждую пару значений внешнего и внутреннего счётчиков. Число полученных пар сравните с суммой длин проходов. Такой след обнаруживает включённую лишнюю границу или пропущенный последний проход.
Методика и условия составлены для проекта; варианты проверены расчётной моделью. Объяснения по предмету.