Вложенные циклы - Язык программирования C++ для спортивного программирования
Неделя 6Вложенные циклы, Двумерные массивы и Задачи на сетках
Вложенные циклы
Цикл внутри цикла: как внутренний цикл начинается заново на каждом проходе внешнего и сколько раз выполняется тело; картинки строка за строкой — внутренний цикл, конец которого зависит от i, два внутренних цикла подряд и if по (i, j); счётчик, который продолжается из строки в строку; break и continue внутри; все пары и все тройки; внутренний цикл для каждого числа и делители до √x; и как быстро всё это растёт.
Теория
Урок 1 из 11
22 мин чтения
Вопросов: 6
В Неделе 3 цикл повторял одно действие: напечатать число, прибавить его к
сумме. Во многих задачах повторяется то, что само является повторением.
Картинка — это несколько строк, а каждая строка — несколько символов. В
кинотеатре есть ряды, а в каждом ряду — места. «Каждая пара чисел» — это каждое
первое число и для каждого из них каждое второе. Цикл, в теле которого есть
другой цикл, называется вложенным циклом — о нём этот урок.
Цикл внутри цикла
Выведите прямоугольник из n строк, по m звёздочек в каждой.
Один цикл печатает одну строку: m звёздочек и перевод строки. Прямоугольнику
нужна такая строка n раз — поэтому весь цикл, печатающий строку, помещается
внутрь другого цикла:
Переменная внешнего цикла i говорит, какая строка рисуется; переменная
внутреннего цикла j — какая звёздочка этой строки. Пройдите его по шагам
при n = 2 и m = 3:
Цикл внутри цикла: две строки по три звёздочки
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 int n = 2, m = 3;
9 for (int i = 1; i <= n; i++) {
10 for (int j = 1; j <= m; j++) {
11 cout << '*';
12 }
13 cout << "\n";
14 }
15 return 0;
16}
n = 2, m = 3
строка 8
Две строки по три звёздочки. Один цикл — для строк, другой — для звёздочек в строке.
n2m3i—j—
нажми пуск
1 / 31
дальше
Практика: Фигуры и Таблицы
Картинки и таблицы, напечатанные строка за строкой: прямоугольники, лесенки, пирамиды, рамки, диагонали и зоны.
Поэтому j меняется быстро, а i — медленно, как минуты и часы на часах. Тело
внутреннего цикла выполняется n · m раз: для каждого из n значений i — все
m значений j. Перевод строки стоит после внутреннего цикла и внутри
внешнего, поэтому выполняется один раз на строку. Поставьте его внутрь
внутреннего цикла — и каждая звёздочка окажется на своей строке; поставьте после
внешнего — и весь прямоугольник вытянется в одну длинную строку.
Называйте переменные двух циклов по-разному. Второе int i во внутреннем цикле
заслоняет внешнее i: внутри внутреннего цикла номер строки уже не использовать.
А если внутренний цикл берёт i без объявления, for (i = 1; i <= m; i++), он
меняет счётчик внешнего цикла, и картинка получается неправильной.
Используем i и j
Обе переменные можно использовать в теле. В строке i и столбце j таблицы
умножения стоит i * j:
Счётчик, объявленный до обоих циклов, не обнуляется между строками: он
продолжает расти от строки к строке. Так календарь нумерует дни:
В месяце n дней, и он начинается с понедельника. Выведите календарь: одна
неделя в строке, номера дней через пробел.
Ввод
Вывод
Здесь внешний цикл — while: мы не считаем недели заранее — новая строка
начинается, пока остаются дни. Внутренний цикл останавливается через 7 дней
или когда месяц закончился — смотря что наступит раньше.
Внутренний цикл может зависеть от i
Внутренний цикл не обязан выполняться одинаковое число раз в каждой строке. Его
начало и конец могут использовать i:
При n = 4 получается лесенка: 1, 2, 3, затем 4 звёздочки. Таблица показывает,
как небольшие изменения внутреннего цикла меняют фигуру:
В строке i
Внутренний цикл
n = 4
i звёздочек
for (int j = 1; j <= i; j++)
лесенка, спускающаяся вправо
n - i + 1 звёздочек
for (int j = 1; j <= n - i + 1; j++)
перевёрнутая лесенка
числа 1 … i
тот же цикл, печатающий j
1, 1 2, 1 2 3, …
n - i точек, затемi звёздочек
два внутренних цикла, один за другим
лесенка, прижатая вправо
Для последней строки таблицы нужны два внутренних цикла в одной строке
картинки: первый печатает точки, второй — звёздочки, а перевод строки идёт после
обоих. Пирамида
устроена так же, только из трёх частей: n - i точек, 2 * i - 1 звёздочек,
n - i точек. Если строка картинки состоит из частей, посчитайте длину каждой
части в строке i и напишите по внутреннему циклу на каждую часть.
if для каждой клетки
Некоторые картинки проще представить по клеткам: картинка — это n строк на
m столбцов, и каждая клетка (i, j) — либо #, либо .. Тогда оба цикла
проходят по всему, а решает if:
Выведите рамку высотой n строк и шириной m столбцов: # по краю, .
внутри.
Ввод
Вывод
Клетка лежит на краю, если она в первой или последней строке или в первом или
последнем столбце. Другие частые условия для квадрата n × n:
Клетки, где
Условие
главная диагональ, из левого верхнего угла в правый нижний
i == j
побочная диагональ, из правого верхнего угла в левый нижний
i + j == n + 1
выше главной диагонали (правее неё)
j > i
ниже главной диагонали (левее неё)
j < i
выше побочной диагонали (левее неё)
i + j < n + 1
ниже побочной диагонали (правее неё)
i + j > n + 1
шахматная раскраска: клетки того же цвета, что угол (1, 1)
(i + j) % 2 == 0
Условия соединяются через && и || (Неделя 2): клетка выше обеих
диагоналей (j > i && i + j < n + 1) лежит в треугольнике, который касается
верхней стороны. С помощью
if / else if дайте каждой клетке ровно один символ — сначала проверьте
диагонали, потом зоны.
Теперь станьте плиточником. Пол получается ровно таким, каким его печатает
программа, — отметьте клетки, куда ляжет плитка, прежде чем плиточник начнёт:
Выложите пол плиткойпопробуй!
break и continue во вложенных циклах
break и continue (Неделя 3) действуют только на самый внутренний цикл
вокруг них. break во внутреннем цикле заканчивает внутренний цикл; внешний
просто переходит к следующему проходу.
Чтобы остановить оба цикла — например, как только найдена какая-нибудь
пара, — заведите переменную типа bool: установите её перед break во
внутреннем цикле и проверяйте во внешнем.
continue во внутреннем цикле пропускает остаток одного прохода (i, j) и
переходит к следующему j. continue во внешнем цикле, до внутреннего,
пропускает целую строку.
Каждая пара
Очень частый вопрос — о парах элементов вектора: сколько пар равны, дают в
сумме k, близки друг к другу? Внешний цикл выбирает первый элемент пары,
внутренний — второй. Если второй всегда стоит после первого, каждая пара
просматривается ровно один раз:
Каждая пара один раз: j начинается после i
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {3, 7, 5, 5};
9 int n = a.size(), cnt = 0;
10 for (int i = 0; i < n; i++) {
11 for (int j = i + 1; j < n; j++) {
12 if (a[i] + a[j] == 10) {
13 cnt++;
14 }
15 }
16 }
17 cout << cnt << "\n";
18 return 0;
19}
Четыре числа
строка 8
Какие пары позиций дают в сумме 10? 3 + 7 и 5 + 5.
a4 ячеек
3
7
5
5
0
1
2
3
n—cnt—i—j—
нажми пуск
1 / 41
Когда j начинается с i + 1, пара (0, 1) проверяется, а (1, 0) — те же два
элемента — нет, и ни один элемент не встаёт в пару сам с собой. Из n элементов
получается n · (n − 1) / 2 таких пар: 6 для 4 элементов и около 12,5 миллиона
для 5000.
Дан рост каждого из n игроков в сантиметрах. Двое могут тренироваться
вместе, если их рост отличается не больше чем на d. Сколько таких пар?
Ввод
Вывод
Внимательно читайте в условии, какие пары считаются:
В условии сказано
Циклы
i < j или «(i, j) и (j, i) — одна и та же пара»
j от i + 1
i ≤ j: число может стоять в паре само с собой
j от i
«(i, j) и (j, i) — разные пары»
оба с самого начала: j от 1 (или 0); пропускайте j == i, если число не может стоять в паре само с собой
Два числа до 10⁹ в сумме дают до 2 · 10⁹ — больше, чем вмещает int: сравнивайте
a[i] + a[j] с k в long long. И количество пар тоже может быть большим:
у 5000 элементов около 1,25 · 10⁷ пар — это ещё помещается в int, а у 10⁵ —
уже нет.
Пары не обязательно берутся из вектора. «Сколько пар 1 ≤ a ≤ b ≤ N с
a · b = P?» — это те же два цикла по числам от 1 до N. Если условие может
только ухудшаться по ходу цикла, остановите цикл раньше, вписав условие в его
проверку: в a * a + b * b == N, как только a² + b² превысило N, большее b
уже не поможет.
При N до 10⁶ числа a и b остаются меньше 1000, поэтому это меньше
полумиллиона шагов — а два цикла до самого N дали бы 10¹².
Тройки — и на один цикл меньше
Три вложенных цикла перебирают все тройки. При 1 ≤ a ≤ b ≤ c ≤ N и
N = 500 это около 2 · 10⁷ троек — нормально. Но прежде чем писать третий цикл,
спросите себя, не определено ли третье значение двумя первыми:
Сколькими способами можно заплатить n тенге монетами по 1, 2 и 5? Важно
только, сколько монет каждого вида, а не их порядок.
Ввод
Вывод
Когда число пятёрок и двоек выбрано, монеты по 1 — это всё, что осталось:
закончить можно ровно одним способом, поэтому третий цикл по единицам не нужен.
Оба цикла останавливаются, как только выбранные монеты стоят больше n.
Внутренний цикл для каждого числа
Внутренним циклом может быть и один из циклов Недели 3 по числу: по его цифрам
или делителям. «Сколько чисел от 1 до N имеют сумму цифр S?» — это for по
числам, а внутри — цикл % 10 / / 10:
Отрезайте цифры от копииi: если бы внутренний цикл менял само i, внешний
цикл сбился бы со счёта.
Делители. Если считать делители x, перебирая все d от 1 до x, это x
шагов; для каждого x до N получается около N² / 2 шагов — 5 · 10⁹ при
N = 10⁵, слишком медленно. Делители идут парами: если d делит x, то и
x / d делит, а меньший из двух не больше √x. Поэтому перебирайте d только
пока d * d <= x и считайте и d, и его пару x / d — один раз, если это одно
и то же число (d * d == x, как 3 и 3 для 9):
Выведите все совершенные числа от 1 до n: числа, равные сумме своих
делителей, меньших самого числа, как 6 = 1 + 2 + 3.
Ввод
Вывод
Теперь каждое число обходится примерно в √x шагов, а все вместе — меньше N · √N:
около 2 · 10⁷ при N = 10⁵. Проверка на простоту из Недели 3, которая
останавливается на d * d <= x и на первом найденном делителе, точно так же
работает внутри цикла по всем x.
Сколько шагов?
Перемножьте, сколько делает каждый цикл, и сравните с 10⁸ простых шагов в
секунду из Недели 4:
Циклы
Шагов
Успевает за секунду при
n строк, m столбцов
n · m
любом размере картинки или таблицы
каждая пара, j от i + 1
n² / 2
n примерно до 10⁴
каждая тройка
около n³ / 6
n примерно до 500
каждое число, все его делители
около n² / 2
n примерно до 10⁴
каждое число, делители до √x
около n · √n
n примерно до 10⁵ – 10⁶
каждое число, его цифры
n · (число цифр)
n примерно до 10⁷
Ограничения в условии подсказывают, какая строка ожидается. N ≤ 5000
приглашает перебрать все пары; N ≤ 10⁵ с циклом по делителям требует варианта
с √x.
Проверьте себя
Как выполняется вложенный цикл
При одном значении i внутренний цикл проходит до конца: j
принимает все значения от 1 до m.
Только после этого внешний цикл делает свой шаг, и i становится 2.
Затем внутренний цикл начинается заново: снова j = 1, а не 4.
А вы знали?
Самой старой известной десятичной таблице умножения около 2300 лет. Её нашли на
21 бамбуковой дощечке из Древнего Китая — это бамбуковые дощечки Цинхуа,
датированные примерно 305 годом до н. э. Строки и столбцы в ней расположены
точно как в программе выше: одно число сверху, другое сбоку, а их произведение —
там, где строка встречается со столбцом.
for(int i = 1; i <= n; i++){ // внешний цикл: один проход = одна строка for(int j = 1; j <= m; j++){ // внутренний цикл: один проход = одна звёздочка cout << '*';} cout << "\n"; // после внутреннего цикла: конец строки}
проверь себя1 балл
Сколько раз выполнится cnt++?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Сколько раз выполнится cnt++?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В векторе 6 элементов. Сколько раз выполнится if?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
При n = 2 и m = 3 что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Чтобы посчитать делители x, программа перебирает d только пока d * d <= x и учитывает и d, и x / d. Почему этого достаточно?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
for(int i = 1; i <= 3; i++){ for(int j = 1; j <= 4; j++){ cout << i * j << " "; // строка i, столбец j} cout << "\n";}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int day = 1; // счётчик продолжается из недели в неделю while(day <= n){ // один проход = одна неделя = одна строка for(int d = 1; d <= 7 && day <= n; d++){ cout << day << " "; day++;} cout << "\n";} return 0;}
for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ // в строке i — i звёздочек cout << '*';} cout << "\n";}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(i == 1 || i == n || j == 1 || j == m){ cout << '#'; // на краю} else{ cout << '.'; // внутри}} cout << "\n";} return 0;}
for(int i = 1; i <= 3; i++){ for(int j = 1; j <= 5; j++){ if(j == 3){ break; // выходит только из цикла по j} cout << "("<< i << ","<< j << ") ";} cout << "\n";}
bool found = false;for(int i = 0; i < n && !found; i++){ // внешний цикл тоже проверяет found for(int j = i + 1; j < n; j++){ if(a[i] + a[j] == k){ found = true; break;}}}
for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ // j начинается после i // пара (i, j)}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, d; cin >> n >> d; vector<int> h(n); for(int i = 0; i < n; i++){ cin >> h[i];} int pairs = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ // j начинается после i: каждая пара один раз if(abs(h[i] - h[j])<= d){ pairs++;}}} cout << pairs << "\n"; return 0;}
for(int a = 1; a * a < N; a++){ for(int b = a; a * a + b * b <= N; b++){ // останавливается, как только сумма больше N if(a * a + b * b == N){ cnt++;}}}
for(int i = 1; i <= N; i++){ int x = i, sum = 0; // копия: цикл ниже разрушает x while(x > 0){ sum += x % 10; x /= 10;} if(sum == S){ cnt++;}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for(int x = 1; x <= n; x++){ long long sum = 0; // сумма всех делителей x for(int d = 1; d * d <= x; d++){ if(x % d == 0){ sum += d; if(d != x / d){ sum += x / d; // его пара, кроме случая d * d == x}}} if(sum - x == x){ // делители, меньшие x, дают в сумме x cout << x << " ";}} cout << "\n"; return 0;}
int cnt = 0;for(int i = 0; i < 4; i++){ for(int j = 0; j < 6; j++){ cnt++;}}
int cnt = 0;for(int i = 1; i <= 5; i++){ for(int j = 1; j <= i; j++){ cnt++;}}
for(int i = 0; i < 6; i++){ for(int j = i + 1; j < 6; j++){ if(a[i] == a[j]) cnt++;}}
for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cout << '*'; cout << "\n";}}