2011-12-17 11 views
7

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

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.

risposta

10

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.

1

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.

+0

"Questa nuova sequenza ha un ciclo se e solo se la sequenza originale lo fa" - questo è falso. –

+0

@ n.m: Uh? per un elenco collegato la proprietà del loopback non viene modificata se la passi su ogni elemento 'x'. O continui a camminare per sempre in entrambi i casi (c'è un ciclo) o ti fermi dopo i passi 'n' o' n/x' (non c'è ciclo). Naturalmente la lunghezza del ciclo non sarà necessariamente 'k/x' se il ciclo originale è di lunghezza' k' ... ma questo è irrilevante per l'argomento. – 6502

+0

Scusa se ho sbagliato. Questo non è falso. Ho frainteso la dichiarazione. –

-1

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.

+3

Sai anche che iniziano sullo stesso punto all'inizio. Se consideri l'argomentazione di Paul Hankin, dovrebbe essere chiaro che il tuo caso non è possibile (se c'è un fattore primo in comune tra A e B, allora puoi arrivare a un caso equivalente in cui questo fattore è stato rimosso). – 6502

+0

"Si sa anche che iniziano sullo stesso punto all'inizio" - non necessariamente entrano nel ciclo nello stesso momento in cui vi è una porzione iniziale non ciclica della lista. –

+0

Oh, vedo che non è possibile in effetti. –