Biorąc pod uwagę liczbę całkowitą n, wylicz wszystkie możliwe pełne drzewa binarne z n węzłów wewnętrznych. (Pełne drzewa binarne mają dokładnie 2 dzieci w każdym węźle wewnętrznym). Struktura drzewa powinna być wyprowadzana jako przejście drzewa przed zamówieniem, przy czym 1 oznacza węzeł wewnętrzny, a 0 reprezentuje węzeł zewnętrzny (Null).
Oto przykłady pierwszych kilku n:
0:
0
1:
100
2:
11000
10100
3:
1110000
1101000
1100100
1011000
1010100
To jest golf golfowy, w którym nagrodą jest jak najmniej znaków. Drzewa powinny być wyprowadzane po jednym w wierszu na standardowe wyjście. Program powinien czytać n z wiersza poleceń lub stdin.
code-golf
combinatorics
binary-tree
Kyle Butt
źródło
źródło
Odpowiedzi:
Perl -
12579 znakówLiczba obejmuje 4 znaki dla
-ln
opcji „ ”. Bierze n od standardowego.Nowe konstruktywne podejście:
Utwórz rozwiązanie dla n, zastępując nowy węzeł wewnętrzny („100”) dla każdego liścia („0”), z kolei w każdym drzewie z rozwiązania dla n-1.
(Zawdzięczam tę koncepcję rozwiązaniom innych, które wykorzystują wewnętrzny węzeł do wstawiania podstawienia [100-> 0] do weryfikacji ciągów generowanych sekwencyjnie i wydaje mi się, że - po napisaniu odpowiedzi opartej na tej koncepcji - to samo 0- > 100 metoda konstrukcji w czyjejś edycji pośredniej).
Poprzednie podejście rekurencyjne:
Rekursywny bez golfa:
źródło
PHP
(142)(138)(134)(113)Działa z wiersza poleceń, tj. „Php golf.php 1” wyprowadza „100”.
EDYCJA: Wytnij 4 znaki alternatywną metodą, budując ciągi od 0 zamiast rekurencji w dół od $ n. Używa PHP 5.3 dla skróconego operatora trójskładnikowego; w przeciwnym razie potrzebne są 2 dodatkowe znaki.
EDYCJA 2: Zapisano 4 kolejne znaki z pewnymi zmianami w pętlach.
EDYCJA 3: Próbowałem innego podejścia i ostatecznie znalazłem go poniżej starej metody.
Wszystkie drzewa można uznać za binarne reprezentacje liczb całkowitych od 4 ^ n (lub 0, gdy n = 0) do 2 * 4 ^ n. Ta funkcja zapętla ten zakres i pobiera ciąg binarny każdej liczby, a następnie wielokrotnie ją zmniejsza, zastępując „100” przez „0”. Jeśli końcowy ciąg to „0”, to jest to prawidłowe drzewo, więc wypisz je.
źródło
Ruby,
9994928987 znakówDane wejściowe są odczytywane ze standardowego wejścia.
Edycja 1: Zmieniono IO (patrz komentarze Lowjackera)
Edycja 2: Zmieniony algorytm.
Edycja 3: Wersja ma teraz trzecie podejście (używając idei migimaru).
Edycja 4: Znów dwie postacie. Dziękuję migimaru.
źródło
*?\n
, ponieważputs
drukuje każdy element tablicy we własnej linii.Rubinowy 1.9
(80)(79)Korzystanie z nierekurencyjnego, konstruktywnego podejścia stosowanego przez DCharness.
EDYCJA: Zapisano 1 znak.
źródło
Haskell 122 znaki
Ponieważ IO jest nietrywialną częścią kodu w haskell, być może ktoś może użyć podobnego rozwiązania w innym języku. Zasadniczo losowe spacery po kwadracie od dołu z lewej do prawej u góry, zatrzymywanie się po przekątnej. Odpowiednik następującego:
źródło
Golfscript, 60
83Zbudowałem tryb gry w golfa dla Emacsa do pracy nad tym, jeśli ktoś jest zainteresowany.
źródło