Zählen Sie bei einer Ganzzahl n alle möglichen vollständigen Binärbäume mit n internen Knoten auf. (Vollständige Binärbäume haben genau 2 Kinder auf jedem internen Knoten). Die Baumstruktur sollte als Vorbestellungsdurchquerung des Baums ausgegeben werden, wobei 1 einen internen Knoten und 0 einen externen Knoten (Null) darstellt.
Hier sind Beispiele für die ersten paar n:
0:
0
1:
100
2:
11000
10100
3:
1110000
1101000
1100100
1011000
1010100
Dies ist ein Code-Golf, bei dem der Preis an die wenigsten Charaktere geht. Die Bäume sollten eine pro Zeile an stdout ausgegeben werden. Das Programm sollte n von der Kommandozeile oder stdin lesen.
code-golf
combinatorics
binary-tree
Kyle Butt
quelle
quelle
Antworten:
Perl -
12579 ZeichenDie Anzahl enthält 4 Zeichen für "
-ln
" Optionen. Nimmt n von stdin.Neuer konstruktiver Ansatz:
Bilden Sie die Lösung für n, indem Sie für jedes Blatt ("0") in jedem Baum aus der Lösung für n-1 einen neuen internen Knoten ("100") einsetzen.
(Ich verdanke dieses Konzept den Lösungen anderer, die den internen Knoten verwenden, um [100-> 0] als Ersatz für die Überprüfung von sequentiell generierten Zeichenfolgen zu verwenden, und ich glaube, ich habe - nachdem ich meine Antwort basierend auf diesem Konzept geschrieben habe - dieselbe 0- gesehen. > 100 Konstruktionsmethode in einer Zwischenbearbeitung.)
Bisheriger rekursiver Ansatz:
Rekursiv ungolfed:
quelle
PHP
(142)(138)(134)(113)Läuft über die Befehlszeile, dh "php golf.php 1" gibt "100" aus.
BEARBEITEN: Schneiden Sie 4 Zeichen mit einer alternativen Methode aus und bauen Sie die Zeichenfolgen von 0 auf, anstatt von $ n aus zu rekursieren. Verwendet PHP 5.3 für den verkürzten ternären Operator. Andernfalls werden 2 weitere Zeichen benötigt.
BEARBEITEN 2: 4 weitere Zeichen mit einigen Änderungen an den Schleifen gespeichert.
EDIT 3: Ich habe einen anderen Ansatz ausprobiert und ihn schließlich unter die alte Methode gebracht.
Alle Bäume können als binäre Darstellungen von ganzen Zahlen zwischen 4 ^ n (oder 0, wenn n = 0) und 2 * 4 ^ n betrachtet werden. Diese Funktion durchläuft diesen Bereich und ruft die Binärzeichenfolge jeder Zahl ab. Anschließend wird sie wiederholt reduziert, indem "100" durch "0" ersetzt wird. Wenn die letzte Zeichenfolge "0" ist, handelt es sich um einen gültigen Baum. Geben Sie ihn daher aus.
quelle
Ruby,
9994928987 ZeichenDie Eingabe wird von stdin gelesen.
Bearbeiten 1: Geänderte E / A (siehe Kommentare von Lowjacker)
Edit 2: Geänderter Algorithmus.
Edit 3: Die Version verfolgt nun den dritten Ansatz (unter Verwendung der Idee von Migimaru).
Edit 4: Wieder zwei Zeichen. Vielen Dank an Migimaru.
quelle
*?\n
, daputs
jedes Element des Arrays in einer eigenen Zeile gedruckt wird.Ruby 1,9
(80)(79)Verwendung des nicht rekursiven, konstruktiven Ansatzes von DCharness.
BEARBEITEN: 1 Zeichen gespeichert.
quelle
Haskell 122 Zeichen
Da das E / A ein nicht trivialer Teil des Codes in haskell ist, kann möglicherweise jemand eine ähnliche Lösung in einer anderen Sprache verwenden. Im Wesentlichen zufällige Spaziergänge in einem Quadrat von links unten nach rechts oben, wobei angehalten wird, wenn die Diagonale gekreuzt wird. Entspricht dem Folgenden:
quelle
Golfscript, 60
83Ich habe einen Golfscript-Modus für Emacs erstellt, um daran zu arbeiten, falls jemand interessiert ist.
quelle