Организация программ со структурой вложенных циклов
Структурой с вложенным цикломназывают такую структуру, в которой внутри одного цикла находится один или несколько других циклов. Цикл, расположенный внутри другого цикла, называют внутренним. Цикл, внутри которого находятся другие циклы, называют внешним. Таким образом, один и тот же цикл может выступать и в роли внешнего (если он содержит внутри себя другие циклы), и в роли внутреннего (если он расположен внутри другого цикла). Правильная организация вложенного цикла состоит в том, что внутренний циклдолжен целиком располагаться внутри внешнего цикла.
Допустимыми являются следующие варианты организации вложенных циклов. Первый вариант вложенного цикла – внутри внешнего цикла последовательно расположено несколько внутренних циклов:
for I:=1 to N do //внешний цикл
begin
. . . . . .
for J:=1 to M do //первый внутренний цикл
begin
. . . . . .
end; // конец первого внутреннего цикла
. . . . . .
for K:=1 to L do //второй внутренний цикл
begin
. . . . . .
end; // конец второго внутреннего цикла
. . . . . .
end; // конец внешнего цикла
Частным случаем первого варианта организации вложенных циклов является следующий
for I:=1 to N do
for J:=1 to M do
for K:=1 to L do
A[I,J,K]:=I*J*K;
В приведенном примере все три цикла оканчиваются в одном и том же месте.
Второй вариант организации вложенного цикла – иерархическое расположение циклов (каждый внутренний цикл расположен внутри предыдущего).
for I:=1 to N do //внешний цикл
begin
. . . . . .
for J:=1 to M do // первый внутренний цикл
begin
. . . . . .
for K:=1 to L do //второй внутренний цикл
begin
. . . . . .
end; // конец второго внутреннего цикла
. . . . . .
end; // конец первого внутреннего цикла
. . . . . .
end; // конец внешнего цикла
Следует иметь в виду, что во вложенном цикле параметры каждого из циклов изменяются разновременно, то есть при очередном (фиксированном) значении параметра внешнего цикла параметр внутреннего цикла последовательно принимает все свои возможные значения. Затем параметр внешнего цикла принимает следующее по порядку новое значение и при этом значении параметр внутреннего цикла вновь принимает все свои возможные значения. Поэтому вложенный цикл часто называют циклом с разновременно изменяющимися параметрами. Таким образом, если внутренний цикл должен выполняться M раз, а внешний – N раз, то операторы, стоящие во внутреннем цикле выполнятся в общей сложности M*N раз, т.е. трудоемкость выполнения вложенных циклов может быть весьма высокой, что надо учитывать при разработке программ. Например, если M=N=100, то операторы внутреннего цикла будут выполняться 10000 раз:
//Вычисление и вывод таблицы умножения чисел от 1 до 100
for I:=1 to 100 do
for J:=1 to 100 do
begin
K:=I*J; // умножение выполняется 10000 раз
Write(K:6);
end;
Во вложенных циклах допустимо передавать управление из внутреннего цикла в любую точку внешнего цикла. Передача управления из внешнего цикла в произвольную точку внутреннего цикла запрещена, так как в этом случае вход во внутренний цикл осуществляется не через его начало. Такая передача управления в языке Паскаль возможна только с использованием оператора безусловного перехода. Поскольку применение этого оператора не отвечает принципам структурного программирования, то его, как правило, в программах не используют и, следовательно, подобные структуры встречаться не будут.
При организации вложенных циклов необходимо обращать внимание на правильное задание вложенности циклов. В некоторых программах порядок вложенности циклов не оказывает влияния на правильность получаемого результата. Например, при вычислении суммы всех элементов матрицы порядок следования циклов может быть произвольным:
Вариант 1 Вариант 2
S:=0; S:=0;
for I:=1 to M do for J:=1 to N do
for J:=1 to N do for I:=1 to M do
S:=S+A[I,J]; S:=S+A[I,J];
Однако при решении многих задач изменение порядка вложенности циклов приводит к неверному результату. Напрмер, при вычислении суммы элементов каждой строки матрицы изменение порядка расположения циклов приведет к тому, что будут вычисляться суммы элементов столбцов.
Вариант 1 (правильный) Вариант 2 (неправильный)
for I:=1 to M do for J:=1 to N do
begin begin
S:=0; S:=0;
for J:=1 to N do for I:=1 to M do
S:=S+A[I,J]; S:=S+A[I,J];
WriteLn(S:7:2); WriteLn(S:7:2);
end; end;
Необходимость организации вложенных циклов возникает при решении таких широко распространенных задач, как вычисление определенного интеграла с заданной точностью, вычисление экстремума функции на заданном интервале с заданной точностью. Рассмотрим решение этих задач.