Информатика · ЕГЭ · 4 мин чтения
Как перебрать все пары без повторов во вложенных циклах?
Редакция Алгоса · Обновлено
Короткий ответ
Для всех пар разных элементов без учёта порядка выбирай индексы i и j так, чтобы i < j. Внешний цикл перебирает i, внутренний — значения j от i + 1 до конца списка. Тогда элемент не соединяется сам с собой, а пара не появляется второй раз в обратном порядке.
Разберись, что нужно найти
Индекс — номер позиции в списке, начиная с нуля. Даже если значения совпадают, позиции могут быть разными. В списке [5, 5, 8] первые две пятёрки находятся на разных местах и образуют допустимую пару позиций. Поэтому условие a[i] != a[j] не заменяет требование разных индексов: оно решает другую задачу.
| Что дано или требуется | Как это использовать |
|---|---|
| i < j | Все неупорядоченные пары разных позиций |
| i ≠ j | Упорядоченные пары разных позиций |
| j = i + 1 | Только соседние пары |
Проследи решение на конкретных данных
Для четырёх элементов с индексами 0, 1, 2, 3 при i = 0 внутренний цикл берёт 1, 2, 3. При i = 1 остаются 2 и 3, при i = 2 — только 3. При i = 3 подходящих j нет. Всего получаем 3 + 2 + 1 = 6 пар.
| Шаг | Результат |
|---|---|
| i = 0 | j = 1, 2, 3 |
| i = 1 | j = 2, 3 |
| i = 2 | j = 3 |
Код для списка a = [2, 4, 7, 9]:
for i in range(len(a)):
for j in range(i + 1, len(a)):
print(a[i], a[j])
Будут выведены пары 2 4; 2 7; 2 9; 4 7; 4 9; 7 9. Верхняя граница range не включается, поэтому индекс len(a) не появится.Проверь границы способа и реши сам
Если порядок важен, ограничение i < j уже лишнее: пары (2, 4) и (4, 2) считаются разными. Тогда можно перебрать все i и j, исключив только i = j. Также не путай все пары с соседними: при n ≥ 1 соседних пар в списке из n элементов лишь n − 1, а всех неупорядоченных — n(n − 1)/2.
Самопроверка: сколько пар разных позиций будет у списка из пяти элементов при i < j? Сколько из них соседние? Проверь отдельно пустой список и список из одного элемента: должно ли происходить хотя бы одно выполнение внутреннего тела?
Ответ и почему так
Всех пар будет 5 × 4 / 2 = 10, соседних — 4. У пустого списка и списка из одного элемента пар разных позиций нет. Условия циклов это обеспечивают без обращения к несуществующим элементам: внутренний диапазон каждый раз оказывается пустым.
Что запомнить
Для неупорядоченных пар разных позиций используй i < j: так нет самопар и повторов в обратном порядке.
Попробовать на Алгосе
Программирование для ЕГЭ
Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.
Перейти к курсу Все курсы