游戏新闻

状态不断指向下一状态时怎样用快慢指针识别循环:规则演算第13例

2026-11-18

某些巡逻或菜单状态每次只有一个下一状态。从任意起点不断跟随,总会在有限状态中再次遇见旧状态;需要区分进入循环前的长度,以及循环本身的长度。

本例采用的规则

本例每个状态恰有一个后继,且后继一定存在。慢指针每轮走一步,快指针走两步,直到相遇。随后把一个指针放回起点,两者都每次走一步,再次相遇处就是循环入口;最后从入口绕行一圈计数,得到循环长度。

具体输入与记录

十八个状态,起点5;列表第i项就是状态i的唯一后继。

后继列表:[11, 17, 9, 13, 7, 0, 9, 8, 3, 15, 7, 0, 4, 8, 10, 2, 9, 12] 追赶:轮数 | 慢指针 | 快指针 [1, 0, 11] [2, 11, 11] 寻找入口:已走步数 | 从起点出发 | 从相遇点出发 [0, 5, 11] [1, 0, 0] 入口0,入环前长度1,环状态[0, 11],环长2。

这些记录只描述本次输入。请先确认编号、时间或坐标的起点,再比较中间结果。空集合、数值零以及没有定义分别表达不同含义,不能任意互换。分数保持精确值,显示近似小数并不意味着计算过程按同样位数舍入。

如何独立复算

第一次相遇的位置不一定是入口。表格分别记录快慢追赶、寻找入口和绕圈计数,避免把三个阶段的步数混在一起。起点本身在环内时,入环前长度为零;自循环的环长为一,都是正常情况。

用字典记录第一次遇到每个状态的序号,可以独立复核入口和环长。字典方案更直观,但额外占用与访问状态数相关。两种方法的结果应相同,展示日志则帮助检查快指针是否真的连续执行了两次后继跳转。

适用范围

如果不保存展示日志,核心算法只需要少量状态变量;本例为了可读性额外记录过程。它依赖下一状态确定且调用过程中不改变。如果转移随机、途中删除状态或存在无后继终点,需要先修改终止条件,不能直接无限追赶。

复现时可以一次改变一个条件,观察结果从哪一行开始变化。出现差异应先核对规则,再检查输入和每一步状态,而不是直接把最终答案改成表中数字。把输入、边界约定和演算过程一起保存,才能在下一次调整后作出有意义的比较。