Уроки 21 - 22
Цикл с условием. Цикл с переменной
§58. Циклические алгоритмы
Содержание урока
Вложенные циклы
Вложенные циклы
В более сложных задачах часто бывает так, что на каждом шаге цикла нужно выполнять обработку данных, которая также представляет собой циклический алгоритм. В этом случае получается конструкция «цикл в цикле» или вложенный цикл.
Предположим, что нужно найти все простые числа в диапазоне от 2 до 1000. Простейший (но не самый быстрый) алгоритм решения такой задачи на псевдокоде выглядит так:
Как же определить, что число простое? Как известно, простое число делится только на 1 и само на себя. Если число n не имеет делителей в диапазоне от 2 до n-1, то оно простое, а если хотя бы один делитель в этом интервале найден, то составное.
Чтобы проверить делимость числа n на некоторое число k, нужно взять остаток от деления n на k. Если этот остаток равен нулю, то n делится на k. Таким образом, программу можно записать так (здесь n, k и count — целочисленные переменные, count обозначает счётчик делителей):
Попробуем немного ускорить работу программы. Делители числа обязательно идут в парах, причём в любой паре меньший из делителей не превосходит √n (так как произведение двух делителей, каждый из которых больше √n, будет больше, чем n). Поэтому внутренний цикл можно выполнять только до значения √n вместо n-1. Для того чтобы работать только с целыми числами (и таким образом избежать вычислительных ошибок), лучше заменить условие k ≤ √n на равносильное ему условие k2 ≤ n. При этом потребуется перейти к внутреннему циклу с условием:
Чтобы ещё ускорить работу цикла, заметим, что когда найден хотя бы один делитель, число уже заведомо составное, и искать другие делители в данной задаче не требуется. Поэтому можно закончить цикл. Для этого в условие работы цикла добавляется условие count = 0, связанное с имеющимся условием с помощью операции «И»:
На первом шаге (при i = 1) переменная k принимает единственное значение
В любом вложенном цикле переменная внутреннего цикла изменяется быстрее, чем переменная внешнего цикла. Рассмотрим, например, такой вложенный цикл:
На первом шаге (при i = 1) переменная k принимает последовательно значение 1. Далее, при i = 2 переменная k принимает последовательно значения 1 и 2. На следующем шаге при i = 3 переменная k проходит значения 1, 2 и 3, и т. д.
Следующая страница 
Вопросы и задания
Cкачать материалы урока
