2011-12-17 11 views
7

Este NO es el problema sobre la detección de ciclo en una lista vinculada utilizando el método famous Hare and Tortoise.Detección de ciclo en una lista vinculada: Teoría exhaustiva

En el método de la tortuga & Tortoise tenemos punteros funcionando en velocidades 1x y 2x para determinar que se encuentran y estoy convencido de que es la forma más eficiente y el orden de ese tipo de búsqueda es O (n).

El problema es que tengo que encontrar una prueba (prueba o desaprobación) de que es posible que dos punteros siempre se encuentren cuando la velocidad de movimiento es Ax (A veces x) y Bx (B veces x) y A no es igual a B. Donde A y B son dos enteros aleatorios que operan en una lista vinculada con un ciclo presente.

Esto fue preguntado en una de las entrevistas a las que asistí recientemente y no pude demostrar de manera exhaustiva a mí mismo que si lo anterior es posible. Cualquier ayuda apreciada.

Respuesta

10

Supongamos que hay un bucle, digamos de longitud L.

Fácil primer caso

Para hacerlo más fácil, en primer lugar considerar el caso en que las dos partículas toda bucle al mismo tiempo. Estas partículas están en la misma posición siempre que n*A = n*B (mod L) para algún entero positivo n, que es el número de pasos hasta que se encuentran de nuevo. Tomar n=L da una solución (aunque puede haber una solución más pequeña). Así que después de L unidades de tiempo, la partícula A ha realizado A viajes alrededor del circuito para volver al principio y la partícula B ha realizado B viajes alrededor del circuito para volver al principio, donde felizmente colisionan.

caso general

Ahora lo que sucede cuando no entran en el bucle al mismo tiempo? Deje A ser la partícula más lenta, es decir A<B, y suponga que A entra en el bucle en el tiempo m, y llamemos a la posición en la que A entra en el bucle 0 (dado que están en el bucle, nunca pueden abandonarlo, entonces Estoy simplemente cambiando el nombre de las posiciones restando A*m, la distancia A ha viajado después de m unidades de tiempo).Entonces, en ese momento, B ya está en la posición m*(B-A) (su posición real después de m unidades de tiempo es B*m y su posición cambiada es por lo tanto B*m-A*m). Entonces tenemos que mostrar que hay un tiempo n tal que n*A = n*B+m*(B-A) (mod L). Es decir, necesitamos una solución a la ecuación modular

(n+m) * (A-B) = 0 (mod L) 

Tomando n = k*L-m para k suficiente como para que k*L>m hace el truco grande, aunque, de nuevo, puede haber una solución más pequeña.

Por lo tanto, sí, siempre se encuentran.

1

Si sus dos tamaños de pasos tienen un factor común x: digamos que los tamaños de los pasos son Axe y Bx, solo considere la secuencia que obtiene de tomar la secuencia original y tomar cada elemento x'th. Esta nueva secuencia tiene un ciclo si y solo si la secuencia original lo hace, y tomar pasos de tamaño A y B equivale a tomar pasos de tamaño Ax y Bx en la secuencia original.

Esta reducción significa que es suficiente para demostrar que el algoritmo funciona cuando A y B son coprime.

+0

"Esta nueva secuencia tiene un ciclo si y solo si la secuencia original lo hace" - esto es falso. –

+0

@ n.m .: ¿Uh? para una lista enlazada, la propiedad de repetir el bucle no se modifica si pasa por encima de cada elemento 'x'. O sigues caminando para siempre en ambos casos (hay un ciclo) o te paras después de los pasos 'n' o' n/x' (no hay ciclo). Por supuesto, la longitud del ciclo no va a ser necesariamente 'k/x' si el ciclo original es de longitud' k' ... pero esto es irrelevante para el argumento. – 6502

+0

Lo siento, estaba equivocado. Esto no es falso Yo malentendí la declaración. –

-1

La hipótesis es falsa. Por ejemplo, si ambos punteros realizan saltos de un tamaño par, el ciclo también es de tamaño par, y la distancia entre los punteros es impar, nunca se encontrarán.

UPD esto es aparentemente una situación imposible. Debido a que los dos indicadores comienzan en el mismo punto, la distancia entre ellos siempre será pareja.

+3

También sabe sin embargo que comienzan en el mismo punto al principio. Si considera el argumento de Paul Hankin, debería quedar claro que su caso no es posible (si hay algún factor primo en común entre A y B, entonces puede llegar a un caso equivalente en el que se haya eliminado este factor). – 6502

+0

"También sabe, sin embargo, que comienzan en el mismo punto al principio": no necesariamente ingresan al ciclo al mismo tiempo que hay una porción inicial no repetitiva de la lista. –

+0

Oh, veo que no es posible de hecho. –

Cuestiones relacionadas