点击查看原文
一.算法概述
Floyd圆判定算法(Floyd Cycle Detection Algorithm )也称为龟兔赛跑算法(Tortoise and Hare Algorithm )，可在有限状态机、迭代函数或链表上存在环
二.基本想法
本质是设定两个指针，分别作为快进指针。 快进指针如果检查对象中存在循环，则这两个指针一定会相遇。 此时相遇的点是，慢指针走过的节点数*2=快指针满足走过的节点数的i=m (从环的入口到节点的实际位置) k )从相遇点到入口的距离) XL ) l为环的长度)； 2i=m k yl；
那么，m k=nl； 可见m和k之和是环路长度的整数倍。 那么，让快速指针继续到m个节点上吧。 然后快速的指针会到达循环的起点。 那么这个m怎么决定呢？ 在慢指针上
从0开始，m步也前进，当缓慢的指针也到达起点的位置时，这个环的起点是两个指针再次相遇的地方
三.应用
)1)判断是否有环？
龟兔解法的基本思想可以用我们奔跑的例子来说明。 如果两个人同时出发，只要路线上有圈，快的一方就能赶上慢的一方。 他还认为，追赶时跑得快一定比跑得慢多了几圈，也就是说，多跑的路的长度是圈长的倍数。
基于上述考虑，Floyd使用两个指针，一个慢指针(龟)每次前进，快指针(兔)指针每次前进两步) (当有两步或多步效果时等效，只需要一个比另一个快) 如果两者在链表头以外的其他地方相遇(即相等)，则链表中存在循环。 否则，)如果快速指针)到达链表的末尾，则说明它没有损坏。
)2)求出环的长度
将相遇的点作为b点，一个指针停留在b上，另一个一步一步前进并记录步数，再次相遇时的步数为循环的长度。
)3)如何确定环的起点
把相遇点定为b点。 方法是将一个指针移动到链表的起点，另一个指针作为b点，使两者同时移动，一步一步移动，两者相遇的地方就是环的起点。
分析：
首先，设最初相遇时通过慢指针的节点数为I，从链表的头到循环的起点的长度为m，循环的长度为n，相遇的位置和起点与起点的位置之间的距离为k。
于是，有一个：
i=m a * n k
在此，a是缓慢前进的针的数量。
快速指针的速度是慢速指针的两倍，因此可以得到另一个表达式。
2 * i=m b * n k
其中，b是快速指针前进的次数。
公式减法：
I=(B-A ) * n
也就是说I是圈长度的整数倍。
这是将任意一个节点放在起点，同时进行m步时，从头部开始行走的指针位于m的位置。 另外，来自相遇位置的指针应该位于距离起点i m，I为轮廓长度的整数倍的位置，其指针也应该位于距离起点m的位置，即轮廓的起点。
计算委员会
题意：
坏了的计算机只能显示n位。 现在你不断平方数k，最高只能保持n比特。 最大的数量是什么？
问题解决：
当数字出现时，就会产生循环。 每次记录最大数量，出现循环时结束，输出最大数量。
# include cstring # include cstdio # include cmath # includecstdlib # includealgorithmusingnamespacestd； typedef long ll； LL arr[1000]； LLnext(intn，LL k ) { LL res=k*k； int len=0； while(RES ) { arr[ len]=res； res/=10； (} LL ans=0； inted=max(1，len-n 1 )； for(intI=len； i=ed； I--}{ans=ans*10arr[I]； } return ans； (}int main ) ) { int t，n； LL k，res； scanf('%d '，t )； while(t-- ) scanf ) ' %d%lld '，n，k )； LL slow=k，fast=k； res=k； while(true ) ) slow=next(n，slow )； fast=next(n，fast )； RES=max(RES，fast )； fast=next(n，fast )； RES=max(RES，fast )； if(fast==slow ) break； }printf('%lld(n )，res )； (四)下一步行动
TODO----floyed算法求最短距离