3622
правки
Изменения
→Доказательство корректности алгоритма
Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
Пусть <tex>H</tex> {{- --}} голова списка, <tex>X</tex> {{--- }} точка встречи, <tex>A</tex> {{--- }} первый элемент цикла, <tex>Q</tex> {{--- }} расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:
<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>
