§ 8.10. Вложенные циклы

Школьный курс C++
Содержание

Синтаксис вложенных циклов

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

Программа 8.10.1
i = 1
while i < 10:
    j = 1
    while j < 10:
        print(f'{i * j:>2}', end=' ')
        j += 1
    print() # Переходим на новую строку
    i += 1

Вывод

 1  2  3  4  5  6  7  8  9 
 2  4  6  8 10 12 14 16 18 
 3  6  9 12 15 18 21 24 27 
 4  8 12 16 20 24 28 32 36 
 5 10 15 20 25 30 35 40 45 
 6 12 18 24 30 36 42 48 54 
 7 14 21 28 35 42 49 56 63 
 8 16 24 32 40 48 56 64 72 
 9 18 27 36 45 54 63 72 81

Блок-схема

Матричный вывод используется довольно часто, особенно для массивов. Матрица представляет собой прямоугольную таблицу. Данные в ней распределяются по строкам и столбцам. Строки матрицы перебирает внешний цикл, а элементы столбцов – вложенный. После завершения работы вложенного цикла, когда вывод значений элементов строки во вложенном цикле завершен, осуществляется переход на новую строку. В python для этого используется функция print() без аргументов.
Приведем пример вложенных циклов в программе с черепахой.
Задача 2. Составить программу рисования по окружности 12 шестиугольников так, чтобы одна из вершин шестиугольника была обращена к центру окружности, а две другие, смежные с ней, касались шестиугольников по соседству. Заливку шестиугольников выполнить случайными цветами. Сторону шестиугольника d ввести с клавиатуры.

Программа 8.10.2
import turtle as t
from random import random, seed
##################### Параметры холста ######################
seed()
w = t.Screen()
w.reset()
w.title('Шестиугольники')
w.bgcolor('black')
w.setup(width = 600, height = 600, startx = -10, starty = 10)
#################### Параметры черепахи #####################
t.speed(10)
t.hideturtle()
t.up()
t.goto(-50,-150)
t.down()
###################### Решение задачи #######################
d = int(input('d = ')) # Сторона шестиугольника
i = 0
while i < 12:  
    t.lt(30)
    R = random() # Красный канал
    G = random() # Зеленый канал
    B = random() # Синий канал
    t.fillcolor(R, G, B)
    t.begin_fill()
    j = 0
    while j < 6: # Рисуем шестиугольник
        t.fd(d)
        t.rt(60)
        j += 1
    t.end_fill()
    t.up() # Переходим к рисованию следующего
    t.fd(d)
    t.rt(60)
    t.fd(d)
    t.lt(60)
    t.down()
    i += 1
w.exitonclick()
t.mainloop()

Возможный вывод
d = 50

Выполнить данное построение не сложно, если учесть, что 360° / 12 = 30°. Это и будет угол поворота (строка 20) перед отрисовкой каждого шестиугольника.

Многократная вложенность

В принципе, количество вложенных друг в друга циклов может быть неограниченно большим. Но на практике, количество вложенных циклов редко превосходит 4. Также, как и в случае с условной инструкцией, глубокую вложенность цикловых инструкций следует избегать, так как это увеличивает сложность алгоритма и значительно усложняет его читаемость.
Рассмотрим наглядно многократную вложенность на примере программы в которой черепаха мостит плитку по всей площади холста.
Задача 3. Составить программу мощения черепахой квадратной плитки по всей площади холста. Цвет плитки определить случайным образом. Длину стороны плитки d ввести с клавиатуры.

Программа 8.10.3
import turtle as t
from random import random, seed
##################### Параметры холста ######################
seed()
w = t.Screen()
w.reset()
w.title('Плитка')
w.bgcolor('black')
w.setup(width = 600, height = 600, startx = -10, starty = 10)
#################### Параметры черепахи #####################
t.speed(10)
t.pensize(1) # Рамка
t.hideturtle()
###################### Решение задачи #######################
d = int(input('d = ')) # Длина стороны
k = 0
dy = 0
n = 600 / d # Определяем количество плиток по ширине и высоте
while k < n:
    i = 0
    t.up() # Устанавливаем новую позицию
    t.goto(-300,300 - dy)
    t.down()
    while i < n: # Создаем ряд плиток    
        R = random()
        G = random()
        B = random()
        t.fillcolor(R, G, B)
        t.begin_fill()
        j = 0
        while j < 4: # Рисуем квадрат
            t.fd(d)
            t.rt(90)
            j += 1
        t.end_fill()
        t.up() # Переходим к следующему
        t.fd(d)
        t.down()
        i += 1
    dy += d # Смещаемся по вертикали, вниз
    k += 1
w.exitonclick()
t.mainloop()

Возможный вывод
d = 50

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

Вывод по образцу

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

* 
* * 
* * * 
* * * * 
* * * * * 
* * * * * * 
* * * * * * * 
* * * * * * * * 
* * * * * * * * * 
* * * * * * * * * * 

Символьная длина нижней стороны вводится с клавиатуры.

Программа 8.10.4
n = int(input('n = '))
i = 0
while i < n:
    i += 1
    j = 0
    while j < i:
        j += 1
        print('*', end='')
    print()

Вывод при n = 10 см. выше.
Обратите внимание, что на каждом шаге внешнего цикла значение переменной i увеличивается, а значит будет увеличиваться количество шагов вложенного цикла, поскольку изменение переменной j поставлено в зависимость от изменения переменной i (стр. 6).
Аналогично выводятся образцы с числами.
Задача 5. Вывести на экран числовой треугольник по образцу:

1  2  3  4  5  6  7  8  9 10
   1  2  3  4  5  6  7  8  9
      1  2  3  4  5  6  7  8
         1  2  3  4  5  6  7
            1  2  3  4  5  6
               1  2  3  4  5
                  1  2  3  4
                     1  2  3
                        1  2
                           1
Программа 8.10.5
n = int(input('n = '))
i = 0
while i < n:
    i += 1
    j = 0
    k = 1
    while k < i: # Выводим пробелы
        k += 1
        print(f'{" ":>3}', end='')
    while j < n - i + 1: # Выводим числа
        j += 1
        print(f'{j:>3}', end='')
    print()

Вывод при n = 10 см. выше.
Сложность этой задачи заключается в том, что выводу чисел должен предшествовать вывод пробельного символа. Очевидный недостаток этой программы в том, что мы не можем управлять шириной поля вывода в процессе работы цикла. Для исправления этого недостатка мы будем использовать возможность замены аргументов форматирования в f-строке. (Чтобы такая замена была возможна, аргументы форматирования заключаются в дополнительные фигурные скобки). Тогда значение ширины поля вывода можно определять динамически. В результате мы избавимся от одного вложенного цикла и программу можно переписать в следующем виде:

Программа 8.10.6
n = int(input('n = '))
i = 0
while i < n:
    i += 1; j = 0
    width = (i-1) * 3
    if i != 1:
        print(f'{" ":{width}}', end='')
    while j < n - i + 1:
        j += 1
        print(f'{j:>3}', end='')
    print()

Поскольку аргумент width не может иметь нулевое значение, первую строку мы должны будем пропустить.
Наконец, существует и третий вариант, когда во вложенном цикле вывод того или иного символа можно производить по результатам работы условной инструкции. Приведем пример программы с условной инструкцией в теле вложенного цикла.
Задача 6. Вывести на экран матрицу по образцу:

1  2  3  4  5  6  7  8  9
*  2  3  4  5  6  7  8  9
*  *  3  4  5  6  7  8  9
*  *  *  4  5  6  7  8  9
*  *  *  *  5  6  7  8  9
*  *  *  *  *  6  7  8  9
*  *  *  *  *  *  7  8  9
*  *  *  *  *  *  *  8  9
*  *  *  *  *  *  *  *  9
Программа 8.10.7
n = int(input('n = '))
i = 0
while i < n:
    i += 1
    j = 0
    while j < n:
        j += 1
        if j >= i:
            print(f'{j:>3}', end='')
        else:
            print(f'{"*":>3}', end='')
    print()

Вывод при n = 9 см. выше.

Вложенные циклы и целые числа

На этом уроке мы продолжим работу с целыми числами. С помощью вложенных циклов реализовано множество известных алгоритмов. К сожалению, недостаток имеющихся знаний, на данном этапе, препятствует нам рассмотреть наиболее важные из них. С ними мы познакомимся позднее. Тем не менее, мы уже можем решить некоторые сложные задачи. В задаче 25 КЕГЭ используются вложенные циклы, которые позволяют произвести детальный анализ целых чисел на определенном отрезке. Рассмотрим типовую задачу.
Задача 7. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [a; b], числа, имеющие ровно 6 различных делителей. Выведите все найденные числа в порядке возрастания. Если таких чисел нет, то вывести False.

Программа 8.10.8
a = int(input('a = '))
b = int(input('b = '))
f = False # Предположим, что таких чисел нет
while a <= b:
    j = 2 # Возможный делитель
    i = 0 # Счетчик делителей
    while j <= a // 2:
        if not a % j:
            i += 1
        if i > 6: break
        j += 1
    else:
        if i == 6:
            f = True # Нашли!
            print(a, end=' ')
    a += 1
else:
    if not f:
        print(f)

Вывод

a = 1
b = 100
24 30 40 42 54 56 66 70 78 88
------------------------
a = 1
b = 10
False

В этом алгоритме используется идея поиска делителей прошлого урока. Таким образом, увеличился лишь код, а не сложность решения. Поскольку целое число (в зависимости от его величины) может содержать большое число делителей, то просматривать их все – не имеет смысла и можно досрочно выйти из цикла, если их число превысило 6 (что обеспечивает быстродействие программы). Мы упростили условие, так как в оригинале требуется сохранять делители. Вскоре мы научимся это делать.
Рассмотрим ещё одну задачу.
Задача 8. Натуральное число из n цифр является числом Армстронга, если сумма его цифр возведенных в n-ую степень равна самому числу. Получите все трёхзначные числа Армстронга. Например: 13 + 53 + 33 = 153

Программа 8.10.9
i = 1
while i < 10:
    j = 0
    while j < 10:
        k = 0
        while k < 10:
            if i * 100 + j * 10 + k ==\
                i ** 3 + j ** 3 + k ** 3:
                    print(i * 100 + j * 10 + k, end=' ')
            k += 1
        j += 1
    i += 1

Вывод

153 370 371 407

В этой программе используется структура из трех вложенных циклов. Каждый из циклов перебирает различные значения разрядов и, в итоге, мы получаем все возможные их комбинации в составе трехзначного числа: от 100 до 999. Переборные циклы с while и целочисленным шагом выглядят некомпактно и некрасиво. Выбора нет, если счетчик цикла имеет дробное приращение. Для целочисленных шагов есть более удобное средство – цикл for и функция range() с которым мы познакомимся на следующем уроке.

Приложение

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Обсуждение закрыто.