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 ₀ .

• 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 ₀ 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 ₀ ) = (1, 0) .

• Obowiązują standardowe zasady gry w golfa .

Przykład

Niech W _-1 = 1 i W ₀ = 0 .

Następnie W ₁ = 01 , W ₂ = 010 , W ₃ = 01001 , W ₄ = 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

Pyth, 8 bajtów

u,peGsGQ

Wprowadź w formularzu "W-1", "W0".

Dowód ukończenia:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

Dowód poprawności:

Oto seria wygenerowana wewnętrznie. Jest drukowany w konkatenacji przez program.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

Porównaj z poniższym, wydrukowanym w konkatenacji, który jest po prostu łańcuchem dodanym do poprzedniego ciągu na każdym kroku:

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

Chcemy udowodnić, że są równoważne.

Oczywiście są one takie same przez kilka pierwszych kroków. Porównajmy je po chwili:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

Widzimy, że pary ciągów są naprzemiennie formami:

01a 10b
a10 b01

Gdzie aib są dowolnymi ciągami zerowymi i zerowymi. Kontynuujmy sekwencję przez chwilę, aby udowodnić, że jest kontynuowana na zawsze przez indukcję:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 kroki później ma prawidłową formę.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 kroki później ma prawidłową formę.

Tak więc przez indukcję łańcuchy zawsze pasują do siebie po jednoczeniu.

Haskell, 15 bajtów

v%w=w++w%(v++w)

Funkcja infix %generuje nieskończony ciąg, który Haskell drukuje na zawsze, ponieważ Haskell jest taki fajny.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

Pomysł rekurencyjny jest podobny do rozwiązania Zgarba . Pisząc fdla funkcji %i +dla konkatenacji łańcuchów, implementuje:

f(v,w) = w + f(w,v+w)

Nieskończony ciąg wyjściowy zaczyna się od w, a pozostała część jest wynikiem ciągów przesuniętych w Fibonacciego wi v+w.

Nie ma problemu z wygenerowaniem miliona znaków na minutę.

Haskell, 31 bajtów

w#v=v++drop(length v)(v#(v++w))

Definiuje to funkcję infix, #która pobiera dwa łańcuchy i zwraca łańcuch nieskończony. Stosowanie:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

Jeśli zapytam o milionowy element sekwencji zdefiniowany przez „1” i „0”, nawet interpreter online wydrukuje wynik w mniej niż sekundę:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

Wyjaśnienie

w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

Zasadniczo wiemy o tym w#v == v#(v++w)i w#vzaczynamy od vi wykorzystujemy te fakty do zdefiniowania wyniku. Ponieważ Haskell jest leniwy, to „magicznie” po prostu działa.

Pip, 8 bajtów

Hej, związany z Pythem!

(fOba.b)

Prosta rekurencyjna definicja zapożyczona z odpowiedzi Xnora Haskella . Z dodanymi spacjami dla przejrzystości:

(f Ob a.b)

Każdy program w PIP jest niejawna funkcja, która przyjmuje argumenty wiersza polecenia jako jego argumenty (przypisane do zmiennych apoprzez e) i wypisuje jej wartość. Ojest 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 z f(x,y)językami podobnymi do C. fZmienna odnosi się do bieżącej funkcji - w tym przypadku, program głównego. W ten sposób program rekurencyjnie wywołuje się z nowymi argumentami bi a.bjako nowe.

Byłem mile zaskoczony, gdy stwierdziłem, że takie podejście jest dość szybkie:

dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

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:

W1Sba.:Ob

CJam, 12 11 bajtów

llL{@_o+_}h

To bierze dwa słowa w osobnych wierszach, w odwrotnej kolejności, np

0
1

daje

0100101001001010010100100101001...

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 ₀ jest pierwszą rzeczą, którą dodajemy (i drukujemy).

ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.
}h

PowerShell, 97 76 bajtów

param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

_{Edycja - Umm, pisanie $e.substring($b.length)po tym, jak właśnie połączyliśmy $ai $brazem 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 -nskrót (skrót -NoNewLine), i to absolutnie zabija tutaj długość.

Zasadniczo, iteruje się przez sekwencję, budując $ejako „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 $awypeł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:

PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...

APL, 24 18

{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞

Zastosowanie formuły xnor pozwoliło na ogolenie kilku postaci.

                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

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:

$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010$
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system

Pure Bash, 58

a=$1
b=$2
printf $b
for((;;)){
printf $a
t=$b
b+=$a
a=$t
}

Skończy mi się pamięć przed 1 minutą, ale do tego czasu mam dużo cyfr - po 10 sekundach mam 100 milionów cyfr:

$ ./ftw.sh 1 0 | head -c100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010ubuntu@ubuntu:~$ 
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c
102334155
$ 

Mathematica, 56 bajtów

$IterationLimit=∞;#0[$Output~WriteString~#2;#2,#<>#2]&

C, 76 (gcc)

main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

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 ₀ należy podać w v[1]i v[2]. To początkowo wzywa p(4)do wydrukowania W ₂ . Następnie zapętla się: wywołuje p(3)wydrukowanie W ₁ , co daje pełną moc wyjściową W ₂ W ₁ , czyli W ₃ . Następnie wywołuje p(4)wydruk W ₂ , co daje pełną moc wyjściową W₄itp. 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.

s[],*p=s;main(c,v)char**v;{for(++v;;)for(puts(v[*++p=*++p!=1]);*p+1==*--p;++*p);}

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.

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.

Akceptuję słowa jako argumenty wiersza poleceń w formacie łańcuchowym.

Możesz wydrukować cyfry nieskończonego słowa albo bez separatora, albo ze spójnym separatorem między każdą parą sąsiednich cyfr.

Używam znaku nowej linii jako spójnego separatora.

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.

Mam dostęp spoza granicami. To musi z pewnością zakończyć się awarią lub naruszeniem dostępu w pewnym momencie. szdarza 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.

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 ₀ ) = (1, 0) .

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:

#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    puts(argv[word]);
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
      --ptr;
      ++ptr[-1];
    }
  }
}

JavaScript (53 bajty)

(a,c)=>{for(;;process.stdout.write(a))b=a,a=c,c=b+a;}

Dane wejściowe powinny być ciągiem, a nie liczbą ( '0'i nie tylko 0).

Perl 5, 45 55 49 bajtów

44 bajty plus 1 -Ezamiast zamiast-e

sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}

Użyj jako np

perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

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 -LGnuWin32, 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 _∞ :

sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}

Używany w ten sam sposób, ale z argumentami w odwrotnej kolejności i nie wymaga -E:

perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

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 przekazany printna końcuredo bloku:

Z -anei odczytywanie <>(oba wejścia w jednym wierszu, oddzielone spacjami, w odwrotnej kolejności); 48 + 2 bajty:

$_=$F[0];{print;unshift@F,$F[0].($_=$F[1]);redo}

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:

$_=$F[1];{print;push@F,$F[-1].($_=$F[-2]);redo}

REXX , 48

arg a b
do forever
b=a||b
say b
a=b||a
say a
end

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.

f(A,B,C):-atom_concat(B,A,D),(C=D;f(B,D,C)).

:- C='0';C='1';(f(1,0,C)).

Python 2, 67 bajtów

a,b=input()
print'\n'.join(b+a)
while 1:a,b=b,b+a;print'\n'.join(a)

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:

$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s

Dyalog APL, 9

{⍵∇⍺,⍞←⍵}

Ten służy ∇do zdefiniowania funkcji rekurencyjnej. To bezpośrednie tłumaczenie odpowiedzi Xnora na Python 3 . Przyjmuje W ₀ jako prawo, a W _-1 jako lewy argument, oba powinny być wektorami znaków.

Minkolang 0.11 , 62 bajty

(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

Wypróbuj tutaj. Oczekuje danych wejściowych w kolejności W ₀ , W _-1 z odstępem pomiędzy nimi.

Wyjaśnienie

(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

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 ₀ i W, _-1 jest ai b, 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 (- W_i ), a następnie zastępuje<a+b>oraz<a>ich następcami,<a+2b>oraz<b>.

(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")

Python 3, 32

def f(a,b):print(end=b);f(b,a+b)

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 endargument w Pythonie 3

Perl, 32 bajty

#!perl -pa
$#F=3}for(@F){push@F,$F[-1].$_

Licząc shebang jako dwa, dane wejściowe są pobierane ze stdin, spacja oddzielona jako W ₀ , W _-1 . Wyjście 1 MB razy przy ~ 15ms, z których większość można przypisać uruchomieniu interpretera.

Przykładowe użycie

$ echo 0 1 | perl inf-ftw.pl
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001...

$ echo 110 101 | perl inf-ftw.pl
1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101...

Prolog, 69 bajtów

q(A,B):-atom_concat(B,A,S),write(A),q(B,S).
p(A,B):-write(B),q(A,B).

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ć.