Задача 3.1. Найти количество целых чисел на отрезке [A, B], которые делятся на 3

Найти количество целых чисел на отрезке [A, B], которые делятся на 3.

Выдвинем гипотезу, что ответом такой задачи является количество чисел на заданном отрезке, деленное нацело на 3.

Проверим эту гипотезу.

На отрезке [5, 8] имеем 4 числа, при делении 4 нацело на 3 будет 1, что совпадает с правильным ответом.

На отрезке [6, 9] имеем снова 4 числа, при делении 4 нацело на 3 будет 1, в то время, как правильным является ответ 2, поскольку на этом отрезке числа 6 и 9 делятся на 3.

Делаем два вывода. Во-первых, гипотеза оказалось неверной, а во-вторых, примеры показывают, что не все зависит, только от длины отрезка. Есть зависимость и от позиции начала отрезка.

Произведем еще раз упрощение задачи.

Научимся решать задачу вычисления количества чисел, делящихся на 3 на отрезке [1, N].

Для этой задачи, очевидно, что всего на отрезке [1, N] имеется N чисел, из которых кратных трем будет N div 3, где операция div соответствует целочисленному делению одного числа на другое.

Реализуем этот вспомогательный алгоритм в общем виде. Он будет находить сколько чисел кратных K имеется на отрезке [1, N].

алг кратные (N, K)

Нач

вернуть N div K

Кон

Вернемся к решению задачи 3.1.

Количество чисел кратных 3 на отрезке [A, B] равно количеству таких чисел на отрезке [1, B] минус количество таких чисел на отрезке [1, А-1]. Это работает не только для 3, но и для любого целого K.

алг делятся (A, B, K)

Нач

вернуть кратные (B, K) – кратные (A-1, K)

Кон

Теперь мы можем решить основную задачу. Можем это сделать даже в более общей постановке, т.е. найти количество целых чисел на отрезке [A, B], которые делятся на K, но не делятся на M.

алг количество (A, B, K, M)

Нач

вернуть делятся (A, B, K) – делятся (A, B, K*M)

Кон

Объясняется это тем, что среди чисел кратных K не все нужны нам в ответе. Лишними являются числа, которые делятся и на K, и на M, т.е. кратные K*M.

Циклические алгоритмы

В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в циклические алгоритмы входит последовательность команд, выполняемая многократно. Такая последовательность команд называется телом цикла. Однократное выполнение тела цикла принято называть итерацией или шагом цикла.

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

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

записан на естественном языке;

изображен в виде блок-схемы;

записан на алгоритмическом языке;

закодирован на языке программирования.

Блок-схема	Алгоритмический	Паскаль
	нцпока Условие Действие кц	while Условие do Действие;

Действие, которое является телом такого цикла, повторяется пока Условие истинно. С помощью цикла пока можно организовать любые повторяющиеся действия и реализовать любые циклические алгоритмы.

Другой тип цикла – цикл, выполняющийся заданное число раз. Он имеет вид:

нцдля Переменная от НЗ до КЗ

Действие

Кц

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

В случае использования целочисленной переменной в качестве параметра цикла, на каждом шаге цикла она увеличивается на 1. Здесь возможно использование не только целочисленных переменных. Допускается переменная любого типа, в рамках которого определено понятие «следующий». Такие типы принято называть порядковыми. К ним, например, относятся символы.

В некоторых случаях используется модифицированный вариант цикла для. В нем Переменная на каждом шаге цикла увеличивается не на 1, а с некоторым заданным шагом.

нцдля Переменная от НЗ до КЗ шаг Ш

Действие

Кц

Любой цикл для может быть заменен циклом пока. Так данной наиболее полной версии цикла для соответствует цикл пока:

Переменная:= НЗ

нцпока Переменная <= КЗ

Действие

Переменная: = Переменная + Ш

Кц

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

Циклы повышают эффективность применения компьютера. С помощью короткой циклической программы можно организовать выполнение большого количества действий.

Приведем примеры применения циклов.