Nieskończony słowo Fibonacciego jest specyficzny, nieskończony ciąg cyfr binarnych, które są obliczane przez wielokrotne łączenie skończonych słów binarnych.
Określmy że sekwencja słowo Fibonacciego typu (lub FTW sekwencja ) jest dowolna sekwencja ⟨W n ⟩ , który jest utworzony w sposób następujący.
Rozpocznij od dwóch dowolnych tablic cyfr binarnych. Nazwijmy te tablice W -1 i W 0 .
Dla każdego n> 0 , niech W n ≔ W n-1 ∥ W n-2 , gdzie ∥ oznacza konkatenację.
Konsekwencją definicji rekurencyjnej jest to, że W n jest zawsze prefiksem W n + 1, a zatem wszystkich W k takich, że k> n . W pewnym sensie oznacza to, że sekwencja „ W n ” zbiega się w nieskończone słowo.
Formalnie niech W ∞ będzie jedyną nieskończoną tablicą, tak że W n jest prefiksem W ∞ dla wszystkich n ≥ 0 .
Każde nieskończone słowo utworzone przez powyższy proces nazwiemy nieskończonym FTW .
Zadanie
Napisz program lub funkcję, która przyjmuje dwa binarne słowa W -1 i W 0 jako dane wejściowe i wypisuje W ∞ , przestrzegając następujących dodatkowych zasad:
Możesz zaakceptować słowa w dowolnej kolejności; jako dwie tablice, tablica tablic, dwa ciągi, tablica ciągów lub pojedynczy ciąg z wybranym ogranicznikiem.
Możesz wydrukować cyfry nieskończonego słowa albo bez separatora, albo ze spójnym separatorem między każdą parą sąsiednich cyfr.
Do wszystkich celów należy założyć, że w kodzie nigdy nie zabraknie pamięci i że jego typy danych nie zostaną przepełnione.
W szczególności oznacza to, że wszelkie dane wyjściowe do STDOUT lub STDERR będące wynikiem awarii zostaną zignorowane.
Jeśli uruchomię kod na moim komputerze (Intel i7-3770, 16 GiB RAM, Fedora 21) przez jedną minutę i potokuję jego dane wyjściowe
wc -c
, musi wydrukować co najmniej milion cyfr W ∞ dla (W -1 , W 0 ) = (1, 0) .Obowiązują standardowe zasady gry w golfa .
Przykład
Niech W -1 = 1 i W 0 = 0 .
Następnie W 1 = 01 , W 2 = 010 , W 3 = 01001 , W 4 = 01001010 … i W ∞ = 010010100100101001010… .
To nieskończony słowo Fibonacciego.
Przypadki testowe
Wszystkie przypadki testowe zawierają pierwsze 1000 cyfr nieskończonej FTW.
Input: 1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001
Input: 11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011
Input: 10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010
Input: 101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101
Odpowiedzi:
Pyth, 8 bajtów
Wprowadź w formularzu
"W-1", "W0"
.Dowód ukończenia:
Dowód poprawności:
Oto seria wygenerowana wewnętrznie. Jest drukowany w konkatenacji przez program.
Porównaj z poniższym, wydrukowanym w konkatenacji, który jest po prostu łańcuchem dodanym do poprzedniego ciągu na każdym kroku:
Chcemy udowodnić, że są równoważne.
Oczywiście są one takie same przez kilka pierwszych kroków. Porównajmy je po chwili:
Widzimy, że pary ciągów są naprzemiennie formami:
Gdzie aib są dowolnymi ciągami zerowymi i zerowymi. Kontynuujmy sekwencję przez chwilę, aby udowodnić, że jest kontynuowana na zawsze przez indukcję:
2 kroki później ma prawidłową formę.
2 kroki później ma prawidłową formę.
Tak więc przez indukcję łańcuchy zawsze pasują do siebie po jednoczeniu.
źródło
W0
ale zamiastW1
drukujeW-1 || W0
, drukuje , co jest „złym” porządkiem konkatenacji. Myślę, że to sięHaskell, 15 bajtów
Funkcja infix
%
generuje nieskończony ciąg, który Haskell drukuje na zawsze, ponieważ Haskell jest taki fajny.Pomysł rekurencyjny jest podobny do rozwiązania Zgarba . Pisząc
f
dla funkcji%
i+
dla konkatenacji łańcuchów, implementuje:Nieskończony ciąg wyjściowy zaczyna się od
w
, a pozostała część jest wynikiem ciągów przesuniętych w Fibonacciegow
iv+w
.Nie ma problemu z wygenerowaniem miliona znaków na minutę.
źródło
Haskell, 31 bajtów
Definiuje to funkcję infix,
#
która pobiera dwa łańcuchy i zwraca łańcuch nieskończony. Stosowanie:Jeśli zapytam o milionowy element sekwencji zdefiniowany przez „1” i „0”, nawet interpreter online wydrukuje wynik w mniej niż sekundę:
Wyjaśnienie
Zasadniczo wiemy o tym
w#v == v#(v++w)
iw#v
zaczynamy odv
i wykorzystujemy te fakty do zdefiniowania wyniku. Ponieważ Haskell jest leniwy, to „magicznie” po prostu działa.źródło
Pip, 8 bajtów
Hej, związany z Pythem!
Prosta rekurencyjna definicja zapożyczona z odpowiedzi Xnora Haskella . Z dodanymi spacjami dla przejrzystości:
Każdy program w PIP jest niejawna funkcja, która przyjmuje argumenty wiersza polecenia jako jego argumenty (przypisane do zmiennych
a
poprzeze
) i wypisuje jej wartość.O
jest operatorem, który wysyła, a następnie zwraca swój operand, więc pierwszą rzeczą, która się tutaj dzieje, jest wyświetlany drugi argument (bez końcowego znaku nowej linii).Teraz składnia inspirowana Lisp
(f x y)
w Pip jest wywołaniem funkcji, równoważnym zf(x,y)
językami podobnymi do C.f
Zmienna odnosi się do bieżącej funkcji - w tym przypadku, program głównego. W ten sposób program rekurencyjnie wywołuje się z nowymi argumentamib
ia.b
jako nowe.Byłem mile zaskoczony, gdy stwierdziłem, że takie podejście jest dość szybkie:
Na mojej maszynie Ubuntu trwa około 30 sekund, zanim program osiągnie maksymalną głębokość rekurencji, w którym to momencie wydrukował gdzieś ponad miliard cyfr.
To iteracyjne rozwiązanie jest nieco szybsze i pochłania mniej pamięci, kosztem jednego bajtu:
źródło
CJam,
1211 bajtówTo bierze dwa słowa w osobnych wierszach, w odwrotnej kolejności, np
daje
Wyjaśnienie
Chodzi o to, aby naiwnie budować to słowo (pamiętając bieżące słowo i dołączając do niego poprzednie), a gdy to robimy, drukujemy wszystko, co właśnie dodaliśmy (aby nie powtarzać wcześniej wydrukowanego prefiksu) . Aby uniknąć konieczności osobnego obchodzenia się z punktem początkowym, zaczynamy od pustego słowa, tak że W 0 jest pierwszą rzeczą, którą dodajemy (i drukujemy).
źródło
PowerShell,
9776 bajtówEdycja - Umm, pisanie
$e.substring($b.length)
po tym, jak właśnie połączyliśmy$a
i$b
razem jest równoznaczne z pisaniem po prostu$a
... derp.Wow, gadatliwy. Program PowerShell domyślnie wypluwa nowy wiersz za każdym razem, gdy coś wypisujesz. Naprawdę jedynym sposobem na obejście tego jest
write-host -n
skrót (skrót-NoNewLine
), i to absolutnie zabija tutaj długość.Zasadniczo, iteruje się przez sekwencję, budując
$e
jako „prąd” W n w miarę, jak idziemy. Ponieważ jednak chcemy zbudować nieskończone słowo zamiast sekwencji, wykorzystujemy nasze poprzednie zmienne, aby wydrukować sufiks$a
wypełniony w poprzedniej pętli. Następnie ustawiamy nasze zmienne na następną rundę i powtarzamy pętlę. Zauważ, że oczekuje to, że dane wejściowe zostaną jawnie rozdzielone jako ciągi, w przeciwnym razie+
operator przyzwyczai się do arytmetyki zamiast konkatenacji.Przykład:
źródło
APL,
2418Zastosowanie formuły xnor pozwoliło na ogolenie kilku postaci.
Na nieskończonej maszynie w nieskończonym czasie drukowałby W ∞ trzy razy - najpierw przyrostowo podczas działania pętli, a następnie dwa razy w wyniku całego wyrażenia, gdy
⍣≡
operator punktu końcowego w końcu powraca.To nie jest bardzo szybkie, ale wystarczająco szybkie. W GNU APL:
źródło
⍣≡
; brzmi bardzo przydatnie.Pure Bash, 58
Skończy mi się pamięć przed 1 minutą, ale do tego czasu mam dużo cyfr - po 10 sekundach mam 100 milionów cyfr:
źródło
Mathematica, 56 bajtów
źródło
C, 76 (gcc)
Jest to dość prosta drukarka rekurencyjna, zaimplementowana jako funkcja zagnieżdżona (rozszerzenie GNU C nieobsługiwane przez clang), aby uniknąć konieczności omijania
v
.p(n)
drukuje W n-2 , gdzie W -1 i W 0 należy podać wv[1]
iv[2]
. To początkowo wzywap(4)
do wydrukowania W 2 . Następnie zapętla się: wywołujep(3)
wydrukowanie W 1 , co daje pełną moc wyjściową W 2 W 1 , czyli W 3 . Następnie wywołujep(4)
wydruk W 2 , co daje pełną moc wyjściową W4itp. Wydajność jest nieco lepsza niż moja wcześniejsza odpowiedź: za minutę widzę 1875034112 wartości.C, 81 (clang)
Jest to zupełnie inne podejście od powyższego, które moim zdaniem warto nadążyć, nawet jeśli ma gorsze wyniki.
Ma to wszelkiego rodzaju nieokreślone zachowanie, głównie dla zabawy. Działa z clang 3.6.2 w Linuksie i clang 3.5.2 w Cygwin dla przypadków testowych w pytaniu, ze specjalnymi opcjami wiersza polecenia lub bez nich. Nie psuje się, gdy włączone są optymalizacje.
Nie działa z innymi kompilatorami.
Akceptuję słowa jako argumenty wiersza poleceń w formacie łańcuchowym.
Używam znaku nowej linii jako spójnego separatora.
Mam dostęp
s
poza granicami. To musi z pewnością zakończyć się awarią lub naruszeniem dostępu w pewnym momencie.s
zdarza się, że zostaje umieszczony na końcu segmentu danych, więc nie powinien blokować innych zmiennych i dawać złych danych wyjściowych przed tym segfaultem. Ufnie.Testując za pomocą
{ ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c
, otrzymuję 1816784896 cyfr w ciągu jednej minuty na mojej maszynie, gdy program został skompilowany-O3
, i 1596678144, gdy został skompilowany z optymalizacjami porzuconymi.Bez golfa, bez UB, z wyjaśnieniem:
źródło
s[]
sztuczka działa dobrze z clangiem (właśnie go zainstalowałem). Jestem dość zaskoczony, że to naprawdę działa. Do wszystkich celów należy założyć, że w kodzie nigdy nie zabraknie pamięci i że jego typy danych nie zostaną przepełnione. Niestety oznacza to, że zwykłe drukowanie W97 nie jest uważane za prawidłowe. Czy możesz zadzwonićp
rekurencyjnie? To wyeliminowałoby potrzebęmain
.p
wp
sobie bez dodawania dodatkowego kodu, ale jeśli znajdę sposób, dokonam ponownej edycji.JavaScript (53 bajty)
Dane wejściowe powinny być ciągiem, a nie liczbą (
'0'
i nie tylko0
).źródło
Perl 5,
455549 bajtów44 bajty plus 1
-E
zamiast zamiast-e
Użyj jako np
Wyświetla to kolejne przybliżenia W ∞ a zatem, jeśli będziesz czekać wystarczająco długo, drukuje, w ostatnim wierszu wyjścia, W ∞ do dowolnej pożądanej długości, zgodnie z wymaganiami. Cyfry tego słowa są konkatenowane bez separatora.
Ponieważ korzystam z systemu Windows, przetestowałem go pod kątem „co najmniej miliona cyfr W ∞ ”, uruchamiając go z wyjściem przekierowanym do pliku i zabijając go po około 59 sekundach, a następnie uruchamiając program
wc -L
GnuWin32, który wydrukował 701408733.Aktualizacja:
OP wyjaśnił w komentarzu do tej odpowiedzi (i prawdopodobnie powinienem był i tak zdawać sobie sprawę), że dodatkowe wyjście poprzedzające W ∞ dyskwalifikuje powyższe. Zamiast tego oto 55-bajtowe rozwiązanie, które drukuje tylko W ∞ :
Używany w ten sam sposób, ale z argumentami w odwrotnej kolejności i nie wymaga
-E
:Bez wątpienia można grać w golfa dalej, ale nie wiem, jak to zrobić.
Dalsza aktualizacja:
Dennis ogolił pięć bajtów, używając
-a
(tym samym czytając,<>
aby usunąćsub
) i ponownie przypisując parametr przekazanyprint
na końcuredo
bloku:Z
-ane
i odczytywanie<>
(oba wejścia w jednym wierszu, oddzielone spacjami, w odwrotnej kolejności); 48 + 2 bajty:Na tej podstawie ogoliłem jeszcze jeden bajt (tak samo jak powyżej, ale teraz dane wejściowe są w odpowiedniej kolejności); 47 + 2 bajty:
źródło
REXX , 48
ftw.rex
exec ftw.rex 0 1
Obecnie nie mogę przetestować wydajności, ponieważ napisałem ją za pomocą kompilatora online. „Na zawsze” można zastąpić dowolną liczbą, w której są wydrukowane liczby ftw (liczba + 2).
Napisałem również małe (niechlujne) rozwiązanie w Prologu. Nie wymyśliłem sposobu testowania wydajności za pomocą tego, ale i tak jest prawdopodobnie okropny.
źródło
Python 2, 67 bajtów
Akceptuje dane wejściowe jako parę ciągów znaków oddzielonych przecinkami:
"1","0"
na przykład w pytaniu.Brak tłumacza online, ponieważ nieskończone pętle są złe.
Buforowane wyjście sprawiło, że zyskałem dużo bajtów. :(Dziękujemy Dennisowi za zwrócenie uwagi, że 1 cyfra na linię jest ważna.Czas na mojej (znacznie słabszej) maszynie:
źródło
Dyalog APL, 9
Ten służy
∇
do zdefiniowania funkcji rekurencyjnej. To bezpośrednie tłumaczenie odpowiedzi Xnora na Python 3 . Przyjmuje W 0 jako prawo, a W -1 jako lewy argument, oba powinny być wektorami znaków.źródło
Minkolang 0.11 , 62 bajty
Wypróbuj tutaj. Oczekuje danych wejściowych w kolejności W 0 , W -1 z odstępem pomiędzy nimi.
Wyjaśnienie
Meta wytłumaczeniem tego jest to, że w tym momencie mamy dwie liczby, po których następuje ciąg „0” i „1” bez separacji. Jeżeli długości W 0 i W, -1 jest
a
ib
, odpowiednio, po czym te dwie liczby z przodu stosu mają<a+b>
i<a>
, w tej kolejności. Słowo utworzone przez połączenie W i + 1 i W i , tj. W i + 1 + W i , jest równe 2 * W i + 1 - W i . Poniższy kod powiela stos (2 * W i + 1 ), wyskakuje z góry<a>
elementy (- Wi ), a następnie zastępuje<a+b>
oraz<a>
ich następcami,<a+2b>
oraz<b>
.źródło
Python 3, 32
Ten sam rekurencyjny pomysł jak moja odpowiedź Haskella , z tym wyjątkiem, że drukowany jest prefiks, ponieważ Python nie obsługuje nieskończonych ciągów.
Użył sztuczki ze Sp3000, aby drukować bez spacji, umieszczając ciąg jako
end
argument w Pythonie 3źródło
Perl, 32 bajty
Licząc shebang jako dwa, dane wejściowe są pobierane ze stdin, spacja oddzielona jako W 0 , W -1 . Wyjście 1 MB razy przy ~ 15ms, z których większość można przypisać uruchomieniu interpretera.
Przykładowe użycie
źródło
Prolog, 69 bajtów
Przykładowe dane wejściowe: p („1”, „0”)
Nie znalazłem sposobu na usunięcie dodatkowego zapisu.
Powinienem być w stanie to poprawić, jeśli wymyślę, jak to zrobić.
źródło