模拟中的循环检测
状态重复时跳过中间过程
模拟中的循环检测 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 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 步。
回顾
当状态重复时，请将每个状态记录在映射表中，找到循环长度，使用取模跳过前面的步骤，只模拟剩余步骤。🚀
常见问题解答
「模拟中的循环检测」课时是免费的吗？
是的 — 「模拟中的循环检测」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「模拟中的循环检测」这节课中我会学到什么？
状态重复时跳过中间过程 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「模拟中的循环检测」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。