Um zu erfahren, was der Turm von Hanoi ist, googeln Sie ihn oder schauen Sie auf der Wikipedia- Seite nach.
Ihr Code sollte in der Lage sein, zwei Dinge zu tun, und diese sind die folgenden:
- Akzeptieren Sie Benutzereingaben, die die Anzahl der Discs am Startpunkt des Hanoi-Turms angeben
- Erstellen Sie eine Ausgabe auf eine Weise Ihrer Wahl (sofern dies irgendwie logisch ist), um die Lösung für das Turmrätsel zu zeigen.
Ein Beispiel für eine logische Ausgabe wäre das Folgende (unter Verwendung eines 4-Disc-Starts):
L1L2C1L1R-2R-1L1L2C1C-1R-2C1L1L2C1
L
stellt den linken Stift dar, C
stellt den mittleren Stift dar und R
stellt den rechten Stift dar. Die Zahlen geben an, wie weit und in welche Richtung die Scheibe auf diesem Stift bewegt werden soll. Positive Zahlen geben die Anzahl der Stifte an, die sich in Richtung des am weitesten rechts liegenden Stifts bewegen (da die Festplatten am am weitesten links liegenden Stift beginnen).
Die Regeln zum Turm von Hanoi sind einfach:
- Es kann jeweils nur eine Festplatte verschoben werden.
- Jede Bewegung besteht darin, die obere Scheibe von einem der Stifte zu nehmen und auf einen anderen Stift zu schieben, über die anderen Scheiben, die möglicherweise bereits auf diesem Stift vorhanden sind.
- Es darf keine Festplatte auf eine kleinere Festplatte gelegt werden.
Die Scheiben beginnen am linken Stift, am größten unten, am kleinsten oben.
Antworten:
Schale , 5 Bytes
Probieren Sie es online aus!
Jedes
n
in der Ausgabe repräsentiert das Verschieben der Festplatten
zum nächsten verfügbaren Stift (zyklisches Umwickeln).Erläuterung
quelle
Python, 76 Zeichen
Für N = 3 wird beispielsweise Folgendes zurückgegeben:
quelle
Perl - 54 Zeichen
Führen Sie mit aus
perl -M5.010
und geben Sie die Anzahl der Discs auf stdin ein.Ausgabeformat:
Eine Zeile pro Zug, die erste Ziffer ist vom Stift, die zweite Ziffer ist vom Stift (ab 0)
Beispiel:
quelle
$x=--$_&-$_,say(($_-$x)%3,($_+$x)%3)for 2..1<<<>
GolfScript (
31 2524 Zeichen)Vielen Dank an Ilmari Karonen für den Hinweis, dass meine ursprünglichen
tr
S / Permutationen um 6 Zeichen verkürzt werden könnten. Indem ich sie als Produkt von zwei Permutationen zerlegte, gelang es mir, eine weitere zu speichern.Beachten Sie, dass das Ausklammern die
3%
Länge um ein Zeichen erhöht:Einige Leute haben wirklich komplizierte Ausgabeformate. Dies gibt den Stift aus, der von (nummeriert 0, 1, 2) bewegt wurde, und den Stift, zu dem bewegt wurde. Die Spezifikation gibt nicht an, zu welchem Stift bewegt werden soll, daher bewegt sie sich zu Stift 1.
Z.B
quelle
])~{.{3^3%}%2,@{2\-}%++}*
Perl, 75
79ZeichenKeith Randalls Ausgabeformat total stehlen:
Rufen Sie mit
-M5.010
für diesay
.(Ich denke, dies kann verbessert werden, wenn Sie einen Weg finden, den Rückgabewert der Funktion zu nutzen, anstatt ihn nur zu unterdrücken.)
quelle
say
" Empfehlung]SML, 63
Aufruffunktion
f(n,s,t)
mit:quelle
Bash (64 Zeichen)
Posting dieses, obwohl es mehr als doppelt so lang ist wie das GolfScript, weil ich die Wiederverwendung von
t
als magecho $s
.quelle
Scala,
928887 ZeichenAusgabeformat
Sagen Sie dann die Anzahl der Festplatten = 3,
quelle
C
989287 ZeichenImplementiert den trivialsten Algorithmus.
Die Ausgabe erfolgt in der Form,
ab ab ab
in der jedes Paar "die obere Scheibe von Stift a nach Stift b bewegen" bedeutet.BEARBEITEN : Bewegungen werden jetzt hexadezimal codiert - 0x12 bedeutet, dass von Stift 1 zu Stift 2 gewechselt wird. Einige Zeichen wurden gespeichert.
BEARBEITEN : Liest die Nummer von stdin und nicht von Parametern. Kürzer.
Beispiel:
% echo 3 | ./hanoi
13 12 32 13 21 23 13
quelle
h(x,printf(...))
ist einfach eine Möglichkeit anzurufen,printf
bevorh
aufgerufen wird. Der letzten++
wird nach der innerenh
Rückkehr gemacht. Es wird verwendet, um die Initiale rückgängig zu machenn--
.;
wäre das hier gleich.,
ist oft nützlich (zBif(x)a,b;
ersetztif(x){a;b;}
), hat hier aber keinen Vorteil.Gelee , 5 Bytes
Probieren Sie es online aus!
0
Verschieben Sie die kleinste Festplatte um ein Leerzeichen nach rechts (ggf. zurück zum Start).1
Verschieben Sie die zweitkleinste Festplatte in die einzige andere zulässige Spalte.2
Verschieben Sie die drittkleinste Festplatte in die einzige andere zulässige Spalteusw.
Algorithmus
Wir können die Lösung des Towers of Hanoi-Problems rekursiv sehen; einen Stapel von Größe zu bewegen n von A zu B , zu bewegen , um einen Stapel von Größe n -1 von A bis C , so ist die Scheibe der Größe n von A nach B , dann zu bewegen , um einen Stapel von Größe n -1 von B zu C . Dies erzeugt ein Muster der folgenden Form (in dem von diesem Programm verwendeten Ausgabeformat):
Wir können beobachten, dass diese Sequenz A007814 auf dem OEIS ist. Eine andere mögliche Definition der Sequenz ist "das k- te (1-basierte) Element der Sequenz ist die Anzahl der Nullen am Ende der Zahl k, wenn sie binär geschrieben ist". Und genau das berechnet das Programm hier.
Erläuterung
Zuerst berechnen wir die Anzahl der Züge in der Lösung, 2 n -1. Es stellt sich als am kürzesten heraus, tatsächlich einen zusätzlichen Zug zu berechnen und ihn später zu verwerfen. Dies ist
2*
also 2 nach der Kraft von etwas. (Die einzige Eingabe, die wir bisher vorgenommen haben, ist das Befehlszeilenargument, das standardmäßig verwendet wird.)Als nächstes verwenden wir Jellys Builtin, um die Anzahl der Nullen am Ende einer Zahl in Basis b zu berechnen . das ist . Da wir binär rechnen, ist es . Alles was wir tun müssen, ist dieses eingebaute auf die Zahlen von 1 bis einschließlich 2 n -1 anzuwenden .
ọb
ọ2
Es gibt zwei einfache Möglichkeiten , um Iterierte über einen Bereich von Zahlen in Jelly,
€
undR
, und meine früheren Versuche, dieses Problem verwendet eine davon. In diesem Fall ist es jedoch möglich, etwas kürzer zu werden:Ṗ
Wenn Sie eine Zahl als EingabeṖ
eingeben , können Sie eine Iteration ausführen, bei der ein Element kurz gehalten wird (im Allgemeinen wird ein Element verwendet, mit dem alle Elemente bis auf ein Element verarbeitet werden). Das ist genau das, was wir in diesem Fall wollen (weil2*
man zu viele elments erzeugt), so dass es zu Link mit2*
undọ2
in2*Ṗọ2
gibt uns eine 5-Byte - Lösung für das Problem.quelle
Awk, 72 Zeichen
Das Ausgabeformat ist das gleiche wie das von Keith Randall .
quelle
Bash-Skript,
10096 ZeichenDas Ausgabeformat ist das gleiche wie das von Keith Randall .
Bearbeiten : 4 Zeichen durch Peters Kommentar gespeichert .
quelle
$@
J, 23 Bytes
Lösung für Binärzahlen
Diese Lösung verwendet die in diesem Video beschriebene binäre Zählmethode .
Das heißt, ich generiere die Binärziffern von
1
bis zu2^n
, nehme dann Infixe der Länge 2 und vergleiche jedes Bit mit dem entsprechenden Bit der vorherigen Zahl und überprüfe, ob sie ungleich sind. Die Anzahl der ungleichen Bits ist die Ausgabe für diese Bewegung.Ausgabe, z. B. für 3 Festplatten, wobei die kleinste Festplatte mit 1 gekennzeichnet ist:
1
bedeutet "Bewegen Sie die kleinste Scheibe um einen Stift nach rechts und kehren Sie bei Bedarf zum ersten Stift zurück"n
bedeutet für alle anderenn
"Festplatten
auf einen legalen Stift verschieben" (es wird immer genau einen geben)Probieren Sie es online aus!
rekursive Lösung
Gleiche Ausgabe wie die obige Lösung, aber die Logik hier macht die rekursive Natur des Problems klarer.
Die Visualisierung als Baum unterstreicht auch diesen Punkt:
Probieren Sie es online aus!
quelle
APL (Dyalog Classic) , 19 Bytes
Probieren Sie es online aus!
Die Ausgabe ist eine 2-Spalten-Matrix von Ints in {0,1,2} - von Peg zu Peg
quelle
K (ngn / k) , 23 Bytes
Probieren Sie es online aus!
quelle
R , 73 Bytes
R auf die Karte setzen. Inspiriert von [Keith Randalls Antwort] [1] mit vereinfachter Eingabe, drucken Sie nur den End- und Startstift, um 2 Bytes zu sparen. Auch 0-indizierte Stifte.
Probieren Sie es online aus!
quelle
JavaScript (ES6), 45b
zB anrufen
h(4, 'A', 'B', 'C')
(4 Discs mit dem Hilfsstift B von Stift A auf Stift C verschieben)kehrt zurück
'ABACBCABCACBABACBCBACABCABACBC'
(verschieben Sie eine Disc von Stift A zu Stift B, verschieben Sie eine Disc von Stift A zu Stift C, verschieben Sie eine Disc von Stift B zu Stift C usw.)quelle