3.2. Алгоритм нахождения точного отсчета

Определения и обозначения

Точный отсчёт — определение количества объектов или значений, удовлетворяющих заданному условию. Например, можно узнать, сколько чисел в списке больше нуля. Такой приём нужен, когда требуется получить именно количество подходящих элементов, а не перечислить их или сложить их значения.

Счётчик — переменная, в которой накапливается количество найденных объектов. После проверки очередного элемента она показывает, сколько подходящих элементов уже обнаружено. Поэтому счётчик помогает сохранить промежуточный результат, пока алгоритм продолжает работу с данными.

Начальное значение счётчика — значение 0, с которого начинают подсчёт, поскольку до проверки ещё ничего не найдено. Если задать другое значение, оно будет ошибочно учтено как уже найденные объекты. Ноль задаёт правильную отправную точку для последующих изменений.

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

Как это устроено

Сначала счётчику присваивают 0, потому что подсчёт начинается до проверки первого объекта. На каждом шаге его значение означает число уже найденных подходящих элементов, а не номер текущего шага. Если начать с 1, алгоритм будет считать, будто один подходящий объект уже есть, хотя проверка ещё не проводилась. Поэтому начальное значение отделяет результат подсчёта от количества просмотренных объектов.

Чтобы перебрать все объекты, нужно знать, где обработка начинается и где заканчивается. Для списка используют его первый и последний элементы, а для числового диапазона задают нижнюю и верхнюю границы. Затем цикл последовательно переходит от одного элемента к следующему. Такой порядок нужен, чтобы ни один объект не остался без проверки и ни один не был проверен повторно.

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

Счётчик изменяют только после выполнения условия, иначе в результат попадут элементы, которые не подходят. При подсчёте количества его обычно увеличивают на 1: каждый подходящий объект добавляет ровно одну единицу к общему числу. При неподходящем объекте счётчик сохраняет прежнее значение. Так число отражает количество, а не сумму значений элементов.

Перебор, проверка и изменение счётчика образуют единый повторяющийся фрагмент алгоритма. Для каждого объекта цикл выполняет проверку, а ветвление выбирает действие: увеличить счётчик или оставить его без изменения. Когда цикл заканчивается, это означает, что обработаны все заданные объекты. Если перебор был полным, значение счётчика и есть ответ: оно складывает по единице каждый и только каждый подходящий объект.

Этапы алгоритма точного подсчёта

Таблица показывает порядок действий: каждый следующий этап опирается на предыдущий. При составлении алгоритма можно проверить по ней, не забыты ли начальное значение, проверка условия и получение результата. Если условие не выполнено, этап изменения счётчика пропускают.

Разбор задач

Сколько положительных чисел в списке из 6 чисел?

Нужно определить количество чисел больше нуля, а не их сумму. Обозначим текущий элемент списка через x; условие подсчёта — x > 0. Проверим все шесть элементов по очереди, включая те, которые равны нулю или меньше нуля.

1. Задаём счётчику значение 0, потому что пока ни одно число не проверено.
2. Берём первое число и проверяем, выполняется ли x > 0. Если да, увеличиваем счётчик на 1; если нет, оставляем его прежним.
3. Повторяем эту проверку для остальных пяти чисел, не пропуская элементы списка.
4. После шестой проверки используем итоговое значение счётчика.

Например, если положительными оказались три числа, счётчик трижды увеличится на единицу и станет равен 3. Отрицательные числа и ноль не добавят к нему ничего. Ответ: количество положительных чисел равно итоговому значению счётчика.

Сколько целых чисел от 1 до 30 делятся на 4 без остатка?

Здесь элементы не перечислены списком: их задаёт диапазон от 1 до 30 включительно. Число делится на 4 без остатка, если остаток от деления равен нулю; это можно записать как x mod 4 = 0. Проверять надо каждое целое число в диапазоне, а не только его границы.

1. Обнуляем счётчик и задаём перебор целых чисел от 1 до 30 включительно.
2. Для каждого текущего числа x проверяем условие x mod 4 = 0.
3. Если остаток равен нулю, увеличиваем счётчик на 1; в остальных случаях ничего не меняем.
4. После проверки числа 30 счётчик содержит ответ. Подходят 4, 8, 12, 16, 20, 24 и 28, поэтому увеличение происходит семь раз.

В этой задаче можно проверить результат и перечислением подходящих чисел. Особое внимание нужно уделить верхней границе: число 30 тоже проверяется, хотя оно не делится на 4 без остатка. Ответ: 7 чисел.

Сколько оценок не ниже заданного значения?

Пусть заданное значение — порог, с которым сравнивают каждую оценку. Слова «не ниже» означают «больше или равно», поэтому условие записывают как оценка ≥ порог. Строгое сравнение «больше» не подойдёт: оно исключило бы оценку, равную порогу.

1. Задаём счётчику значение 0 и устанавливаем перебор всех оценок списка.
2. Для каждой оценки сравниваем её с порогом по условию оценка ≥ порог.
3. Если условие выполняется, увеличиваем счётчик на 1; если оценка ниже порога, оставляем счётчик без изменения.
4. После проверки последней оценки считываем итоговое значение счётчика.

Например, при пороге 4 оценки 4 и 5 должны быть учтены, а оценки ниже 4 — нет. Проверка равенства помогает убедиться, что граница включена в условие. Ответом будет число оценок, которые не ниже заданного значения.

Типичные ошибки

Если задать счётчику 1 вместо 0, итог будет завышен на единицу: алгоритм заранее учтёт несуществующий найденный объект. Такую ошибку допускают, когда путают счётчик с номером первого элемента. Проверьте начальное присваивание: до начала перебора количество найденных объектов должно быть равно нулю.

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

Неверные границы перебора могут привести к пропуску первого или последнего значения. Это случается, когда условие завершения цикла исключает границу, которую требуется проверить. Сверьте начало и конец перебора с условием задачи, а затем вручную проверьте, входит ли в обработку каждый крайний элемент.

Условие может проверять не текущий элемент или исключать значение, равное границе. Например, для требования «не ниже порога» нужно использовать сравнение ≥, а не строгое >. Ошибку легко заметить, подставив в условие значение, равное порогу, и выяснив, должно ли оно учитываться. Также убедитесь, что проверяется именно тот элемент, который сейчас перебирает цикл.

Связь с другими темами

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

Что запомнить

• Счётчик для точного подсчёта обычно начинают с нуля.
• Каждый нужный объект проверяют ровно один раз.
• Счётчик изменяют только тогда, когда условие выполнено.
• При подсчёте количества подходящих объектов счётчик увеличивают на 1.
• Границы перебора должны включать все требуемые объекты.
• После полного перебора значение счётчика содержит искомое количество.