追击问题和Floyd判圈法

2019-03-12 本文已影响0人 lutl

追击问题大家都知道，是一个算速度差以及距离差的小学题目

速度差×追及时间=追及路程
路程差÷速度差=追及时间

Floyd判圈算法是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法
如果有限状态机、迭代函数或者链表上存在环，那么在某个环上以不同速度前进的2个指针必定会在某个时刻相遇。同时显然地，如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇，那么可以判定存在一个环，且可以求出2者相遇处所在的环的起点与长度

设有两个指针同时从链表起点（即点A处）同时前移，快指针fast每次挪动两格，慢指针slow每次挪动一格

一、证明假如有环，两指针必相遇

虽然看起来仿佛是个这还用证的问题，但还是说一下
因为快指针fast移动速度是慢指针slow的两倍，当慢指针slow从起点A运动到环起点B的时候 $S_{slow} = \frac{1}{2}S_{fast} = m$ 。这时快指针fast在环内，慢指针slow在环起点，实际追击距离为 $0\leq m - i·l < l(i为非零整数，l为环长)$
快指针fast必能追上慢指针slow并且是在一圈内追上

二、如何求环长

设点C为两指针相遇点
将慢指针slow从相遇节点开始继续后移，快指针fast不动，当两指针再次相遇时，慢指针slow移动的距离即为环长l

三、环起点的求法及原理

为了求出环的起点，只要令慢指针slow仍均位于节点C，而令快指针fast返回起点节点A，此时fast与slow之间距为环长度l的整数倍。随后，同时让fast和slow往前推进，且保持二者的速度相同：fast每前进1步，slow前进1步。持续该过程直至fast与slow再一次相遇，设此次相遇时位于同一节点B，则节点B即为从节点A出发所到达的环的第一个节点，即环的一个起点

设其中AB距离为m，BC距离为k，环长为l
$S_{slow} = m + a·l + k(a为非负整数)$
$S_{fast} = m + b·l + k(b为非负整数)$

$S_{fast} - S_{slow} = S_{slow} = (b-a)·l$
由此可知慢指针slow的位移是环长l的整数倍
$S_{slow} = m + a·l + k = (b-a)·l$
$m = (b-2a)·l - k = (b-2a-1)·l + (l - k)$
起点A到环起点B距离m等于环的整数倍外加一段弧长，每次挪1步，必会在点B相遇

追击问题和Floyd判圈法

一、证明假如有环，两指针必相遇

二、如何求环长

三、环起点的求法及原理

猜你喜欢

热点阅读