Ehi, ho letto la torre di Hanoi online e ho trovato questo algoritmo.
for (x = 1; x < (1 << n); x++)
{
printf("\nMove from Peg %i to Peg %i", (x-(x&-x))%3 + 1;, (x+(x&-x))%3 + 1
}
che visualizza 2 ^ n-1 mosse per un puzzle standard. Ciò che mi confonde è l'algoritmo usato per trovare il da e per i pioli. Capisco il bit shifting, ma questo algoritmo non mi è chiaro. Come ho capito ora, ogni 3 mosse ripristina l'algoritmo, da cui il% 3. Fa (x- (x & -x))% 3 + 1, trova il 1 bit più a destra e (x + (x & -x))% 3 + 1; trova il 1 bit più a sinistra? (Potrei sbagliarmi su questo). Qualcuno può chiarire questo per me. Apprezzo qualsiasi aiuto.
Sono confuso su come questo algoritmo possa risolvere in modo eloquente il puzzle. Interessante anche, ho notato che il valore della funzione interna (x & -x), mi dà uno schema interessante.
1 2 1 4 1 2 1 questo è per un problema di hanoi di 3 dischi. 4 dischi danno questo
1 2 1 4 1 2 1 8 1 2 1 4 1 2 1
Qualcuno può spiegarlo? Guidandomi un po 'pazzo