Перестановки и идея задачи о N ферзях
Размещайте элементы и возвращайтесь назад при конфликтах
«Перестановки и идея задачи о N ферзях» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
От подмножеств к упорядочиваниям
Перестановка — это расположение всех элементов в некотором порядке. Их генерация — следующий навык поиска с возвратом после подмножеств. 🔀
Сколько существует перестановок
Для n элементов существует факториал n перестановок, потому что для первой позиции есть n вариантов, для следующей — n минус один и так далее. Количество быстро растёт.
Размещайте по одному элементу
Рекурсия заполняет позиции слева направо. На каждом шаге выбирайте неиспользованный элемент, размещайте его и продолжайте рекурсию для остальных.
Отслеживайте использованные элементы
Логический массив использованных элементов отмечает уже размещённые элементы, поэтому каждый из них встречается в каждой перестановке ровно один раз.
Перестановки в коде
Этот поиск с возвратом размещает неиспользованное значение, выполняет рекурсивный вызов, а затем освобождает его для следующей ветви.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Используйте itertools, когда это разрешено
В быстрых соревнованиях функция Python itertools.permutations выдаёт все упорядочивания, поэтому не нужно писать рекурсию самостоятельно.
from itertools import permutations
for p in permutations(a):
print(p)Задача о N ферзях
В задаче о N ферзях нужно разместить n ферзей на доске размером n на n так, чтобы ни один не атаковал другого. Это классическая головоломка на поиск с возвратом. 👑
По одному ферзю в каждой строке
Поскольку два ферзя не могут находиться в одной строке, размещайте ровно по одному ферзю в каждой строке и выбирайте только его столбец. Это значительно сокращает пространство поиска.
Проверяйте три типа конфликтов
Перед размещением отклоняйте любой уже занятый столбец или диагональ. Отслеживайте занятые столбцы и оба направления диагоналей в множествах.
if c in cols or r-c in d1 or r+c in d2:
continueВыполняйте возврат в тупиковой ситуации
Если в строке не подходит ни один столбец, ветвь не приводит к решению. Выполните возврат, уберите последнего ферзя и попробуйте следующий вариант.
Общая схема
Перестановки и задача о N ферзях имеют одну структуру: выбрать, выполнить рекурсию, отменить выбор. Как только вы её увидите, большинство задач на размещение будет решаться по одному шаблону.
Быстрая проверка
Почему в задаче о N ферзях размещают только по одному ферзю в каждой строке?
Повторение: выбрать, выполнить рекурсию, отменить выбор
Вы сгенерировали перестановки, размещая неиспользованные элементы, и узнали, что в задаче о N ферзях применяется та же схема выбора, рекурсивного вызова и отмены выбора с проверкой конфликтов. 🎯
Часто задаваемые вопросы
Урок «Перестановки и идея задачи о N ферзях» бесплатный?
Да — полный текст урока «Перестановки и идея задачи о N ферзях» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Перестановки и идея задачи о N ферзях»?
Размещайте элементы и возвращайтесь назад при конфликтах Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Перестановки и идея задачи о N ферзях»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рекурсивное мышление: база и рекурсия
- Генерация всех подмножеств
- Перестановки и идея задачи о N ферзях
- Сокращение поиска ради соблюдения лимита времени