Rilevamento del ciclo in un elenco collegato: Teoria di estinzione

Question

Questo NON è il problema relativo al rilevamento del ciclo in un elenco collegato mediante il metodo famous Hare and Tortoise.

Nel metodo Hare & Tortoise abbiamo puntatori in esecuzione in velocità 1x e 2x per determinare che si incontrano e sono convinto che sia il modo più efficiente e l'ordine di quel tipo di ricerca è O (n).

Il problema è che devo presentare una dimostrazione (dimostrazione o confutazione) che è possibile che due puntatori si incontreranno sempre quando la velocità di spostamento è Ax (A volte x) e Bx (B volte x) e A non è uguale a B. Dove A a B sono due numeri interi casuali che operano su un elenco collegato con un ciclo presente.

Questo è stato chiesto in una delle interviste che ho partecipato di recente e non sono stato in grado di dimostrare in modo esauriente a me stesso che se quanto sopra è possibile. Qualsiasi aiuto apprezzato.

Answer 1

Supponiamo che esista un ciclo, ad esempio della lunghezza L.

cassa Facile primo

Per facilitare, in considerazione il caso in cui le due particelle intero ciclo allo stesso tempo. Queste particelle si trovano nella stessa posizione ogni volta n*A = n*B (mod L) per un numero intero positivo n, che è il numero di passaggi finché non si incontrano di nuovo. Prendendo n=L dà una soluzione (anche se potrebbe esserci una soluzione più piccola). Quindi, dopo le unità di tempo L, la particella A ha effettuato i viaggi A attorno al loop per tornare all'inizio e la particella B ha fatto in modo che i viaggi B tornino all'inizio, dove si scontrano felicemente.

Caso generale

Ora, cosa succede quando non entrano nel ciclo, allo stesso tempo? Lascia che A sia la particella più lenta, ovvero A<B, e supponiamo che A entri nel ciclo al momento m e chiamiamo la posizione in cui A entra nel ciclo 0 (poiché sono nel ciclo, non possono mai lasciarlo, così io m semplicemente rinominando le posizioni sottraendo A*m, la distanza A ha viaggiato dopo le unità di tempo m).Quindi, in quel momento, B è già nella posizione m*(B-A) (la sua posizione reale dopo le unità di tempo m è B*m e la sua posizione è quindi B*m-A*m). Quindi dobbiamo mostrare che c'è un tempo n tale che n*A = n*B+m*(B-A) (mod L). Cioè, abbiamo bisogno di una soluzione dell'equazione modulare

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

Prendendo n = k*L-m per k basta che k*L>m fa il trucco grande, anche se ancora una volta, ci può essere una soluzione più piccola.

Pertanto, si, si incontrano sempre.

Answer 2

Se le due dimensioni di passo hanno un fattore x comune: diciamo che le dimensioni del passo sono Ax e Bx, quindi considera solo la sequenza ottenuta prendendo la sequenza originale e prendendo ogni x'th elemento. Questa nuova sequenza ha un ciclo se e solo se la sequenza originale lo fa, e prendendo le misure delle dimensioni A e B su di esso equivale a fare passi di dimensione Ax e Bx sulla sequenza originale.

Questa riduzione significa che è sufficiente dimostrare che l'algoritmo funziona quando A e B sono coprimi.

Answer 3

L'ipotesi è falsa. Ad esempio, se entrambi i puntatori fanno salti di una dimensione pari, il ciclo è anche di dimensioni pari e la distanza tra i puntatori è dispari, non si incontreranno mai.

UPD questa è apparentemente una situazione impossibile. Poiché i due puntatori iniziano nello stesso punto, la distanza tra loro sarà sempre pari.