Поиск циклов в моделировании
Пропускайте шаги, когда состояние повторяется
«Поиск циклов в моделировании» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Когда шаги повторяются
В некоторых задачах на моделирование нужно найти состояние после огромного числа шагов, например после триллиона. Пошаговое выполнение никогда не завершилось бы вовремя. ⏳
Число состояний конечно
Если число возможных состояний ограничено, моделирование рано или поздно снова попадёт в одно из них. После этого состояния начнут бесконечно повторяться по циклу.
Как выглядит цикл
У пути есть хвост, который ведёт к циклу, а затем начинается повторяющаяся последовательность. Если заметить цикл, можно перескочить через миллиарды шагов.
Запоминайте пройденные состояния
Сохраняйте каждое состояние в словаре, сопоставляя ему номер шага, на котором Вы впервые его увидели. Повторное появление состояния выявляет цикл.
seen = {}Обнаружьте повтор
Перед каждым шагом проверяйте, есть ли текущее состояние среди уже просмотренных. Если есть, Вы только что замкнули цикл.
if state in seen:
start = seen[state]Измерьте длину цикла
Длина равна разности между текущим номером шага и номером шага, на котором Вы впервые увидели это состояние. За такое число шагов состояние возвращается обратно.
length = step - seen[state]Перепрыгните вперёд по модулю
Вычтите длину хвоста, а затем возьмите оставшееся число шагов по модулю длины цикла. Теперь Вам нужно промоделировать лишь небольшой остаток.
rem = (N - start) % lengthВыполните оставшиеся шаги
Запустите моделирование только на эти оставшиеся шаги, начиная с начала цикла. Итоговое состояние в точности совпадёт с состоянием на шаге N.
for _ in range(rem):
state = step_fn(state)Сделайте состояние хешируемым
Ключи словаря должны быть хешируемыми, поэтому перед сохранением преобразуйте списки в кортежи. Изменяемое состояние не может быть ключом.
key = tuple(row)Алгоритм Флойда без памяти
Если состояния слишком велики для хранения, алгоритм Флойда с «черепахой и зайцем» находит цикл с помощью двух указателей и почти без дополнительной памяти.
Почему это спасает ситуацию
Поиск циклов превращает невозможный цикл на триллион шагов в несколько тысяч шагов. Весь приём заключается в распознавании повторений.
Быстрая проверка
Впервые Вы увидели текущее состояние на шаге s, а сейчас находитесь на шаге t.
Итоги
Когда состояния повторяются, сохраняйте каждое в словаре, находите длину цикла, перемещайтесь вперёд по модулю и моделируйте только оставшиеся шаги. 🚀
Часто задаваемые вопросы
Урок «Поиск циклов в моделировании» бесплатный?
Да — полный текст урока «Поиск циклов в моделировании» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Поиск циклов в моделировании»?
Пропускайте шаги, когда состояние повторяется Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Поиск циклов в моделировании»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Моделирование состояния и переход вперёд
- Обходы сетки и векторы направлений
- Поиск циклов в моделировании
- Приручаем сложные крайние случаи