Wie funktioniert dieser iterative Turm von Hanoi? C

Mögliche Duplizieren:
How does this work? Weird Towers of Hanoi Solution Wie funktioniert dieser iterative Turm von Hanoi? C

Während Google surfen, fand ich diese interessante Lösung Turm von Hanoi, die nicht einmal Stapel als Datenstruktur zu verwenden ist.

Kann mir jemand kurz erklären, was macht es eigentlich?

Ist diese Lösung wirklich akzeptabel?

-Code

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
    int n, x; 
    printf("How many disks?\n"); 
    scanf("%d", &n); 
    printf("\n"); 
    for (x=1; x < (1 << n); x++) 
     printf("move from tower %i to tower %i.\n", 
     (x&x-1)%3, ((x|x-1)+1)%3); 
return 0; 
}

Update: Was ist die hartcodierte Nummer 3 in der hier?

Quelle

2010-05-20 TCM

Es verwendet die Standard 3 Stangen. –

Gibt es die richtige Reihenfolge der Züge an? Wenn ja, funktioniert es, und es gibt keinen Grund, warum es nicht akzeptabel sein sollte. Sie müssen es jedoch verstehen, bevor Sie es als Lösung für Ihre Hausaufgaben anbieten, oder Sie werden in Schwierigkeiten geraten, wenn Sie dazu aufgefordert werden, es zu erklären, wie Sie es sehr wohl sein können, da es sich vom normalen unterscheidet. –

Es ist nicht meine Hausaufgaben. Ich habe gerade zufällig diesen Algorithmus gefunden und dachte, wie es tatsächlich funktioniert. – TCM

könnte einfacher sein, in Pseudo-Code, um zu sehen:

GET NUMBER OF DISKS AS n 
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS 
    SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A 
    OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B 
    PRINT "MOVE FROM TOWER " A " TO TOWER " B 
    ADD 1 TO x

1 n Bits nach links verschoben wird grundsätzlich 2 hoch N, 16 im Fall von 4-Platten.

If you walk through this sequence manually, you should see the progression of movement of the disks. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif

Quelle

2010-05-20 02:44:59

Dank Harvey ist dieser Pseudocode in der Tat einfach zu verstehen :). Gute Antwort ! – TCM

Uh, "ZWISCHEN 1 UND n" ist nicht das Gleiche wie "für (x = 1; x <(1 << n); x ++)" –

@David: Danke, behoben. –

Es ist eine der binären Lösungen zu Tower of Hanoi, gibt es eine detaillierte Erklärung dieses Algorithmus auf Wikipedia - lesen the "Binary solution" paragraph.

Quelle

2010-05-20 02:42:36 ZelluX

Wie funktioniert dieser iterative Turm von Hanoi? C

Antwort

Verwandte Themen