Если в теле одного цикла имеется другой цикл, то такая структура алгоритма называется вложенными циклами. Рассмотрим задачу, программа решения которой имеет структуру вложенных циклов.
Требуется получить на экране компьютера таблицу умножения в форме матрицы Пифагора. Блок-схема алгоритма будет следующей (рис. 3.17).
Рис. 3.17. Блок-схема алгоритма получения таблицы умножения
Здесь цикл по параметру у вложен в цикл по параметру х. Последовательность изменения значений параметров циклов такая:
Таким образом, внешний цикл исполнится 9 раз, а внутренний — 9 • 9 = 81 раз. На один шаг повторения внешнего цикла происходит полная прокрутка внутреннего.
При программировании вложенных циклов используется понятие глубины вложенности. В данном примере глубина вложенности внутреннего цикла равна единице. Если бы внутри вложенного цикла был еще один вложенный цикл (например, для вычисления всех вариантов перемножения трех сомножителей), то его глубина вложенности равнялась бы двум.
Программа на Паскале получения матрицы Пифагора:
В результате выполнения программы на экране получим:
Итерационные циклы
Итерационный цикл — это цикл, для которого число повторений тела цикла заранее неизвестно. В итерационных циклах на каждом шаге вычислений происходят последовательное приближение и проверка условия достижения искомого результата. Выход из итерационного цикла осуществляется в случае выполнения заданного условия.
Пример 1. Снова рассмотрим задачу вычисления суммы числового ряда:
Но теперь условие будет таким: в сумму нужно включить только слагаемые, значение которых больше некоторой малой величины 8. При этом полученная сумма будет отличаться от предельного значения (константы е) на величину, не большую ε.
Поскольку с увеличением значения i величина 1/i! уменьшается, в сумму надо включать все слагаемые, предшествующие первому значению, меньшему ε. Вот две программы решения этой задачи, использующие циклы с предусловием и постусловием:
Решить эту задачу, используя цикл с параметром, нельзя. Итерационные циклы программируются путем использования либо цикла-пока, либо цикла-до.
Пример 2. В § 17 была рассмотрена задача вычисления суммы цифр трехзначного натурального числа. Программа имела линейную структуру. Поставим задачу в более общем виде: для любого многозначного натурального числа вычислить сумму всех его цифр.
Выделение цифр происходит с помощью однотипных действий: использования операций mod и div. Очевидно, что их можно «зациклить». Однако число повторений цикла будет разным для чисел разной длины. Поэтому эта задача не решается с помощью цикла с заданным числом повторений. В таком случае в программе можно использовать либо оператор цикла While, либо Repeat и нельзя — цикл с параметром For. Программа с использованием цикла с предусловием:
Поскольку при каждом повторении цикла от числа X отбрасывается одна младшая цифра, закончить цикл нужно тогда, когда X станет равным нулю. Обратите внимание на типы переменных. Надо помнить о разнообразии групп типов в Паскале. Назначение переменной X типа Longint дает возможность вводить в нее значения, включающие до десяти знаков. Для переменной Sum назначен тип Word, поскольку сумма цифр может быть только положительным числом.
Возможны случаи, когда внутри тела цикла необходимо повторять некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая структура получила название цикла в цикле или вложенных циклов. Глубина вложения циклов (то есть количество вложенных друг в друга циклов) может быть различной.
При использовании такой структуры для экономии машинного времени необходимо выносить из внутреннего цикла во внешний все операторы, которые не зависят от параметра внутреннего цикла. Пример вложенных цикловдля
Вычислить сумму элементов заданной матрицы А(5,3).
нц для i от 1 до 5 нц для j от 1 до 3 S:=S+A[i,j] кц кц
Пример вложенных цикловпока
Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.
i:=2; P:=1 нц пока i 10.06.2016. 7.4. В какой форме записываются алгоритмы? 7.5. Что такое словесный способ записи алгоритмов? 7.6. Что такое графический способ записи алгоритмов?
к задачам из плаката «Выбери свой университет» в школах Москвы
Когда на каждый шаг цикла необходимо выполнять некоторый набор инструкций другого цикла, применяется структура вложенных циклов. По отношению друг к другу эти циклы называются внешним и вложенным. Если условия циклов зависят от значения счетчиков, то создаются два счетчика: один для внешнего цикла, а другой для вложенного. При этом, значение счетчика вложенного цикла должно обнуляться (или получать значение по умолчанию) на каждом шаге внешнего цикла. Рассмотрим простой пример. Задача 1. Вывести таблицу Пифагора (таблицу умножения в форме матрицы).
Блок-схема Матричный вывод используется довольно часто, особенно для массивов. Матрица представляет собой прямоугольную таблицу. Данные в ней распределяются по строкам и столбцам. Строки матрицы перебирает внешний цикл, а элементы столбцов – вложенный. После завершения работы вложенного цикла, когда вывод значений элементов строки во вложенном цикле завершен, осуществляется переход на новую строку. Приведем пример вложенных циклов в программе с черепахой. Задача 2. Составить программу рисования по окружности 12 шестиугольников так, чтобы одна из вершин шестиугольника была обращена к центру окружности, а две другие, смежные с ней, касались шестиугольников по соседству. Заливку шестиугольников выполнить случайными цветами. Сторону шестиугольника d ввести с клавиатуры.
Многократная вложенность
В принципе, количество вложенных друг в друга циклов может быть неограниченно большим. Но на практике, количество вложенных циклов редко превосходит 4. Также, как и в случае с условной инструкцией, глубокую вложенность цикловых инструкций следует избегать, так как это увеличивает сложность алгоритма и значительно усложняет его читаемость. Рассмотрим наглядно многократную вложенность на примере программы в которой черепаха мостит плитку по всей площади холста. Задача 3. Составить программу мощения черепахой квадратной плитки по всей площади холста. Цвет плитки определить случайным образом. Длину стороны плитки d ввести с клавиатуры.
Возможный вывод d = 50 Основную часть программы (мощения одного ряда) с небольшими изменениями мы взяли из предыдущей программы. Третий (внешний) цикл нам нужен для того, чтобы подготовить (сместить на нужную позицию) черепаху для рисования следующего ряда ниже. Количество плиток по горизонтали и вертикали определяется делением ширины (или высоты) окна на длину стороны квадрата ( d ). Аналогично осуществляется мощение другими геометрическими фигурами. Обратите внимание, что вложенный цикл фактически выполняет одни и те же инструкции. Такой код рекомендуется выносить из основной программы в функцию. С этим понятием мы познакомимся позднее.
Вывод по образцу
Следует сказать, что условие вложенного цикла может зависеть от изменения переменных во внешнем цикле, например счетчика. Это может сделать программу более эффективной по количеству выполняемых шагов цикла и, возможно, избавиться от использования условной инструкции в теле цикла. Рассмотрим пример задачи, в которой реализуется такой подход. Задача 4. Вывести на экран треугольник с помощью символа ‘*’ по образцу:
Символьная длина нижней стороны вводится с клавиатуры.
Вывод при n = 10 см. выше. Обратите внимание, что на каждом шаге внешнего цикла значение переменной i увеличивается, а значит будет увеличиваться количество шагов вложенного цикла, поскольку изменение переменной j поставлено в зависимость от изменения переменной i (стр. 6). Аналогично выводятся образцы с числами. Задача 5. Вывести на экран числовой треугольник по образцу:
Вывод при n = 10 см. выше. Существует и другой вариант, когда во вложенном цикле вывод того или иного символа можно производить по результатам работы условной инструкции. Приведем пример программы с условной инструкцией в теле вложенного цикла. Задача 6. Вывести на экран матрицу по образцу:
Персональная страничка Диканева Тараса Викторовича
5.1. Вложенные циклы: теория
Циклы позволяют повторять выполнение любого набора операторов. В частности можно повторять много раз выполнение другого цикла. Такие циклы называются вложенными.
Пример 1. Напечатать числа в виде следующей таблицы
Данная таблица состоит из четырех строчек, в каждой из которых число 3 напечатано 5 раз. Строчку из пяти чисел можно напечатать с помощью одного цикла for:
Чтобы повторить вывод строчки 4 раза, вставляем этот цикл внутрь другого:
Типичная ошибка, когда в качестве счетчиков вложенных циклов (i и k в приведенном примере) используется одна и та же переменная. То есть нельзя в каждом из циклов использовать одну переменную i. Помнить об этом особенно важно, поскольку данная ошибка не обнаруживается на этапе компиляции. Ваша программа запустится, но делать будет вовсе не то, что вы от нее ждете. В приведенном примере (если допустить ошибку, заменив переменную k на i) внешний цикл выполнится всего 1 раз вместо 4-х. Возможна также ситуация, когда такая ошибка приведет к зацикливанию: внешний цикл будет выполняться бесконечно долго – программа зависнет.
Рассмотрим еще один пример.
Пример 2. Напечатайте числа в виде следующей таблицы:
Снова используем внешний цикл для вывода строк, а внутренний для отдельных чисел в одной строке. Используем также отдельную переменную-счетчик n, в которой будет храниться выводимое число.
Дополнительная переменная-счетчик (n) здесь введена для большей прозрачности алгоритма. Заметив, что всегда выполняется n = (i-1)*4+k, можно обойтись без нее.
Разумеется, ту же задачу можно решить без вложенных циклов (вообще говоря, обойтись без них можно всегда). Например, заметив, что числа, стоящие в конце каждой строки делятся на 4, делаем так:
Однако решения, основанные на вложенных циклах, как правило, интуитивно понятнее, их проще придумывать. Это связано с такой фундаментальной идеей программирования как разделение задачи на подзадачи. Выделяется отдельная часть решения задачи (вывод одной строки в приведенных примерах), затем с помощью внешнего цикла она выполняется много раз.
Типичные ошибки при написании вложенных циклов:
1. Наиболее частая ошибка – использование одной и той же переменной-счетчика для внешнего и внутреннего циклов. Выше она уже упоминалась.
2. При решении некоторых задач необходимо, чтобы одна переменная-счетчик на каждом шаге увеличивалась, а другая при этом уменьшалась. Следуя непостижимыми (для человека наделенного формально-логическим складом ума) путями интуитивного мышления многие студенты для решения этой задачи приходят к конструкции вида:
Если вы хоть что-то поняли про вложенные циклы, то вам должно быть очевидно, что к решению поставленной задачи эта конструкция не имеет никакого отношения.
Напомним, что в качестве пределов изменения переменной-счетчика цикла можно использовать произвольное выражение, дающее результат целого типа:
В частности, если речь идет о вложенных циклах, то пределы изменения переменной во внутреннем цикле могут зависеть от значения переменной внешнего цикла. Например:
Пример 3: Напечатайте числа в виде следующей таблицы:
Поскольку внутри цикла может находиться все, что угодно, то ничто не мешает разместить там два цикла. Например, так:
В заключение небольшое замечание, касающееся правильного стиля написания программы, содержащей множество циклов (в частности вложенных). Следует избегать одновременного использования в качестве счетчиков пар переменных с именами i и j, а также p и q. На вид они очень похожи, что часто приводит к трудно обнаруживаемым ошибкам.
