Урок 4. Программирование вложенных циклов

• Предметная: Сформировать представление учащихся о вложенных циклах, правилах организации вложенных циклов, задачах, решаемых с применением вложенных циклов, методах применения вложенных циклов, правилах выбора порядка вложения циклов.

• Общеобразовательная: Развивать умение осваивать новый материал, умение логически мыслить, применять полученные знания на практике.

• Приветствие класса
• Проверка домашнего задания
• Объявление темы урока

Учащиеся читают теорию (текст спроецирован на экран или интерактивную доску либо находится в файле, имеющемся на каждом компьютере):

Любой цикл может содержать внутри себя один или несколько других циклов. Такая структура называется вложенными циклами. Охватывающие циклы называются внешними, охватываемые – внутренними.

К алгоритмам и программам с вложенными циклами приводят задачи:

1. Табулирования функций нескольких переменных.
2. Вычисления кратных сумм и произведений.
3. Обработки многомерных массивов и др.

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

FOR i := 1 TO 10 DO
FOR j := 15 DOWNTO 5 DO
m := 2 * i – k div j;

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

Пример.

Напечатать таблицу значений функции z = x²+y² для аргумента x, изменяющегося от x₀ до x_k и аргумента y, изменяющегося от от y₀ до y_k Величины x₀, x_k y₀, y_k вводятся с клавиатуры.

Для определения значения функции z при всех значениях аргументов x и y процесс вычислений следует организовать следующим образом:

Зафиксировать значение одного из аргументов, например x, на начальном значении (x0) и при этом значении организовать цикл изменений другой переменной - y, в котором вычисляются соответствующие значения функции z. После выполнения этого цикла следует увеличить на единицу значение переменной x и вновь перейти к полному циклу изменений переменной y. Затем вновь увеличить на единицу значение x и т. д., пока не будут пройдены все значения переменной x вплоть до xk. Поскольку цикл с параметром y необходимо выполнить при всех значениях x от x0 до xk, то по переменной x также следует организовать цикл, причем цикл с параметром y будет вложен внутрь цикла с параметром x.

Программа табулирования функции будет иметь вид:

PROGRAM Tabul;
VAR x0, xk, y0, yk, x, y, z: integer;
BEGIN
readln (x0,xk,y0,yk);
FOR x:=x0 TO xk DO
BEGIN
FOR y:=y0 TO yk DO
BEGIN
z:=sqr(x)+sqr(y);
writeln ('x=',x,',y=',y,',z=',z);
END;
END;
END.

Учащимся предлагается ответить на вопрос:

Что неудачно в этой программе?

(Подсказка:

однократно или многократно вычисляется величина x² при одном и том же значении x?)

(Ответ:

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

Программа, использующая этот метод, имеет вид:

PROGRAM Tabul1;
VAR x0, xk, y0, yk, x, y, z, x2: integer;
BEGIN
readln (x0,xk,y0,yk);
FOR x:=x0 TO xk DO
BEGIN
x2:=sqr (x);
FOR y:=y0 TO yk DO
BEGIN
z:=x2+sqr(y);
writeln ('x=',x,',y=',y,',z=',z);
END;
END;
END.

Использование вспомогательной переменной x2 в данном примере иллюстрирует общее правило организации циклов:
необходимо выносить за пределы цикла все вычисления, которые не зависят от параметра данного цикла.).

Сформулируем еще одно правило организации вложенных циклических процессов. Оно относится к определению порядка вложения циклов.

Если условие задачи непосредственно не определяет, по какому параметру цикл должен быть внешним, а по какому - внутренним, то необходимо определить, с каким из параметров связаны наиболее сложные вычисления. По этому параметру должен быть организован внешний цикл, т. к. тело этого цикла выполняется меньшее количество раз. Поясним сказанное на примере нашей второй программы. Тело цикла с параметром x выполняется n_x = x_k - x₀ + 1 раз. Тело цикла с параметром y для одного значения x выполняется n_y = y_k - y₀ + 1 раз, а для всех значений x - n_x • n_y раз, т. е. вычисления во внутреннем цикле выполняются большее число раз. Именно поэтому нужно стремиться включать во внутренний цикл меньшее количество вычислений. В данной задаче внутренний и внешний циклы можно менять местами, т. к. вычисления, связанные с параметрами x и y, имеют одинаковую сложность. При этом изменится только очередность изменения аргументов при вычислении значений функции.
При прочих равных условиях объем вычислений, а значит, и время выполнения программы, могут быть сокращены путем вложения циклов друг в друга таким образом, чтобы внешний цикл имел меньшее число повторений, чем отдельно взятый внутренний цикл. При этом уменьшается число организаций и повторений циклов.
Например, при вложении циклов

FOR x:=1 TO 20 DO
FOR y:=1 TO 50 DO
z:=x+y;

организация внешнего цикла выполняется 1 раз, внутреннего - 20 раз, повторение внешнего цикла - 20 раз, повторение веутреннего цикла - 1000 раз, т. е. всего будет 21 организация и 1020 повторений двух циклов.

При обратном порядке вложения циклов
FOR y:=1 TO 50 DO
FOR x:=1 TO 20 DO
z:=x+y;
будет 51 организация и 1050 повторений циклов. При равном количестве вычислений второй участок программы будет выполняться дольше первого (хотя и не намного).

Учащиеся составляют программу, выводящую на экран таблицу значений функции z = x³-y³ для аргумента x, изменяющегося от x₀ до x_k и аргумента y, изменяющегося от от y₀ до y_k Величины x₀, x_k y₀, y_k вводятся с клавиатуры.

Программа имеет вид:

PROGRAM Tabul1;
VAR x0, xk, y0, yk, x, y, z, x2: integer;
BEGIN
readln (x0,xk,y0,yk);
FOR x:=x0 TO xk DO
BEGIN
x2:=sqr(x)*x;
FOR y:=y0 TO yk DO
BEGIN
z:=x2-sqr(y)*y;
writeln ('x=',x,',y=',y,',z=',z);
END;
END;
END.

Учащимся предлагается ответить на вопросы:

1. Какая структура называется вложенными циклами?
2. Какие задачи приводят к вложенным циклам?
3. Могут ли два или более вложенных друг в друга циклов заканчиваться одним и тем же оператором?
4. Какие правила следует соблюдать при использовании структуры вложенных циклов?
5. Как правильно выбрать порядок вложения циклов друг в друга?

Составить программу, выводящую на экран таблицу значений функции z = x²+y³ - [p / 10] для аргумента x, изменяющегося от x₀ до x_k, аргумента y, изменяющегося от от y₀ до y_k и аргумента p, изменяющегося от p₀ до p_k. Величины x₀, x_k y₀, y_k, p₀, p_k вводятся с клавиатуры.

Программа имеет вид:

PROGRAM Trojka;
VAR x, y, z, p, x0, xk, y0, yk, p0, pk: integer;
BEGIN
readln (x0,xk,y0,yk,p0,pk);
FOR x:=x0 TO xk DO
BEGIN
FOR y:=y0 TO yk DO
BEGIN
FOR p:=p0 TO pk DO
BEGIN
z:=sqr(x)+sqr(y)*y-p div 10;
writeln ('x=',x,',y=',y,',',p = ', p, ',z=',z);
END;
END;
END;
END.

на главную