Le mot de Fibonacci infini est une séquence infinie spécifique de chiffres binaires, qui sont calculés par concaténation répétée de mots binaires finis.

On définit qu'une séquence de mots de type Fibonacci (ou séquence FTW ) est une quelconque séquence ⟨W _n ⟩ qui est formé comme suit.

• Commencez avec deux tableaux arbitraires de chiffres binaires. Appelons ces tableaux W _-1 et W ₀ .

• Pour chaque n> 0 , soit W _n ≔ W _n-1 ∥ W _n-2 , où ∥ désigne la concaténation.

Une conséquence de la définition récursive est que W _n est toujours un préfixe de W _{n + 1} et, par conséquent, de tout W _k tel que k> n . Dans un sens, cela signifie que la séquence ⟨W _n ⟩ converge vers un mot infini.

Formellement, soit W _∞ le seul tableau infini tel que W _n soit un préfixe de W _∞ pour tout n ≥ 0 .

Nous appellerons tout mot infini formé par le processus ci-dessus un FTW infini .

Tâche

Écrivez un programme ou une fonction qui accepte deux mots binaires W _-1 et W ₀ en entrée et imprime W _∞ , en respectant les règles supplémentaires suivantes:

• Vous pouvez accepter les mots dans n'importe quel ordre; comme deux tableaux, un tableau de tableaux, deux chaînes, un tableau de chaînes ou une seule chaîne avec un délimiteur de votre choix.

• Vous pouvez imprimer les chiffres du mot infini sans délimiteur ou avec un délimiteur cohérent entre chaque paire de chiffres adjacents.

• À toutes fins utiles, supposez que votre code ne manquera jamais de mémoire et que ses types de données ne débordent pas.

  En particulier, cela signifie que toute sortie vers STDOUT ou STDERR résultant d'un plantage sera ignorée.

• Si j'exécute votre code sur ma machine (Intel i7-3770, 16 Go de RAM, Fedora 21) pendant une minute et que je dirige sa sortie vers wc -c, il doit imprimer au moins un million de chiffres de W _∞ pour (W _-1 , W ₀ ) = (1, 0) .

• Les règles de code-golf standard s'appliquent.

Exemple

Soit W _-1 = 1 et W ₀ = 0 .

Alors W ₁ = 01 , W ₂ = 010 , W ₃ = 01001 , W ₄ = 01001010 … et W _∞ = 010010100100101001010… .

C'est le mot infini de Fibonacci.

Cas de test

Tous les cas de test contiennent les 1 000 premiers chiffres du FTW infini.

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 octets

u,peGsGQ

Saisie dans le formulaire "W-1", "W0".

Preuve d'achèvement:

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

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

Preuve de correction:

Voici la série générée en interne. Il est imprimé en concaténation par le programme.

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

Comparez avec les éléments suivants, imprimés en concaténation, qui est simplement la chaîne ajoutée à la chaîne précédente à chaque étape:

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

Nous voulons prouver qu'ils sont équivalents.

De toute évidence, ils sont les mêmes lors des premières étapes. Comparons-les après un peu:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

On voit que les paires de cordes sont alternativement des formes:

01a 10b
a10 b01

Où a et b sont des séquences arbitraires sur 0 et 1. Continuons un peu la séquence, pour prouver qu'elle se poursuit indéfiniment:

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

2 étapes plus tard, il est de la bonne forme.

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

2 étapes plus tard, il est de la bonne forme.

Ainsi, par induction, les chaînes correspondent toujours une fois concaténées.

Haskell, 15 octets

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

La fonction infixe %produit une chaîne infinie, que Haskell imprime pour toujours car Haskell est cool comme ça.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

L'idée récursive est similaire à la solution de Zgarb . Écrivant fpour la fonction %et +pour la concaténation de chaînes, il implémente:

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

La chaîne de sortie infinie commence par w, et le reste est le résultat des chaînes décalées de Fibonacci wet v+w.

Cela n'a aucun problème à générer un million de caractères en une minute.

Haskell, 31 octets

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

Cela définit une fonction infixe #qui prend deux chaînes et renvoie une chaîne infinie. Usage:

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

Si je recherche le millionième élément de la séquence définie par "1" et "0", même l' interprète en ligne imprime le résultat en moins d'une seconde:

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

Explication

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.

Fondamentalement, nous savons cela w#v == v#(v++w)et w#vcommençons par v, et utilisons ces faits pour définir le résultat. Puisque Haskell est paresseux, cela fonctionne "par magie".

Pip, 8 octets

Hé, à égalité avec Pyth!

(fOba.b)

Définition récursive simple empruntée à la réponse Haskell de xnor . Avec des espaces ajoutés pour plus de clarté:

(f Ob a.b)

Chaque programme dans Pip est une fonction implicite qui prend les arguments de la ligne de commande comme arguments (affectés aux variables avia e) et affiche sa valeur de retour. Oest un opérateur qui génère puis renvoie son opérande, donc la première chose qui se produit ici est le deuxième argument affiché (sans retour à la ligne).

Maintenant, la syntaxe inspirée de Lisp (f x y)dans Pip est un appel de fonction, équivalent à f(x,y)dans les langages de type C. La fvariable fait référence à la fonction actuelle - dans ce cas, le programme de niveau supérieur. Ainsi, le programme s'appelle récursivement avec bet a.bcomme les nouveaux arguments.

J'ai été agréablement surpris de constater que cette approche est très rapide:

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

Il faut environ 30 secondes sur ma machine Ubuntu pour que le programme atteigne la profondeur de récursivité maximale, moment auquel il a imprimé quelque part plus d'un milliard de chiffres.

Cette solution itérative est légèrement plus rapide et monopolise moins de mémoire, au prix d'un octet:

W1Sba.:Ob

CJam, 12 11 octets

llL{@_o+_}h

Cela prend les deux mots sur des lignes distinctes, dans l'ordre inverse, par exemple

0
1

donne

0100101001001010010100100101001...

Explication

L'idée est de construire le mot naïvement (en se souvenant du mot actuel et en y ajoutant le précédent) et pendant que nous faisons cela, nous imprimons tout ce que nous venons d'ajouter (afin de ne pas répéter le préfixe déjà imprimé) . Pour éviter d'avoir à gérer le point de départ séparément, nous partons d'un mot vide, tel que W ₀ est la première chose que nous ajoutons (et imprimons).

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 octets

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

_{Edit - Umm, écrire juste $e.substring($b.length)après avoir concaténé $aet $bensemble équivaut à écrire juste $a... derp.}

Wow, verbeux. Par défaut, PowerShell crache une nouvelle ligne chaque fois que vous sortez quelque chose. Vraiment la seule façon de se déplacer c'est avec write-host -n(abréviation de -NoNewLine), et cela tue absolument la longueur ici.

Essentiellement, cela se répète à travers la séquence, en construisant $ecomme le "courant" W _{n au} fur et à mesure. Cependant, comme nous voulons construire le mot infini au lieu de la séquence, nous utilisons nos variables précédentes pour imprimer le suffixe $aqui a été rempli dans notre boucle précédente. Ensuite, nous configurons nos variables pour le prochain tour et répétons la boucle. Notez que cela s'attend à ce que l'entrée soit explicitement délimitée sous forme de chaînes, sinon l' +opérateur est utilisé pour l'arithmétique au lieu de la concaténation.

Exemple:

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

APL, 24 18

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

L' utilisation de la formulation de xnor a permis de raser quelques caractères.

                 ⍞  ⍝ 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).

Sur une machine infinie en un temps infini, elle afficherait en fait W _∞ trois fois - d'abord de manière incrémentielle lors de l'exécution de la boucle, puis deux fois en résultat de l'expression entière lorsque l' ⍣≡opérateur fixpoint reviendra finalement.

Ce n'est pas très rapide mais assez rapide. Dans 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
}

Je manque de mémoire avant 1 minute, mais j'ai beaucoup de chiffres d'ici là - après 10 secondes, j'ai 100 millions de chiffres:

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

Mathematica, 56 octets

$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++));}

Il s'agit d'une imprimante récursive assez simple, implémentée comme une fonction imbriquée (une extension GNU C non prise en charge par clang) pour éviter d'avoir à passer v. p(n)imprime W _n-2 , où W _-1 et W ₀ doivent être fournis dans v[1]et v[2]. Cela appelle initialement p(4)à imprimer W ₂ . Il boucle ensuite: il appelle p(3)à imprimer W ₁ , ce qui rend la sortie complète W ₂ W ₁ , qui est W ₃ . Il appelle ensuite p(4)à imprimer W ₂ , ce qui rend la sortie complète W₄ , etc. Les performances sont légèrement meilleures que ma réponse précédente: je vois les valeurs de 1875034112 en une minute.

C, 81 (clang)

C'est une approche complètement différente de ce qui précède que je pense qu'il vaut la peine de suivre, même si elle obtient un score pire.

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

Cela a toutes sortes de comportements indéfinis, principalement pour le plaisir. Il fonctionne avec clang 3.6.2 sous Linux et avec clang 3.5.2 sur Cygwin pour les cas de test de la question, avec ou sans options de ligne de commande spéciales. Il ne se casse pas lorsque les optimisations sont activées.

Cela ne fonctionne pas avec d'autres compilateurs.

Vous pouvez accepter les mots dans n'importe quel ordre; comme deux tableaux, un tableau de tableaux, deux chaînes, un tableau de chaînes ou une seule chaîne avec un délimiteur de votre choix.

J'accepte les mots comme arguments de ligne de commande au format chaîne.

Vous pouvez imprimer les chiffres du mot infini sans délimiteur ou avec un délimiteur cohérent entre chaque paire de chiffres adjacents.

J'utilise la nouvelle ligne comme délimiteur cohérent.

À toutes fins utiles, supposez que votre code ne manquera jamais de mémoire et que ses types de données ne débordent pas.

En particulier, cela signifie que toute sortie vers STDOUT ou STDERR résultant d'un plantage sera ignorée.

J'accède shors des limites. Cela doit sûrement se terminer par une erreur de segmentation ou une violation d'accès à un moment donné. sarrive à être placé à la fin du segment de données, il ne devrait donc pas encombrer d'autres variables et donner une sortie erronée avant ce segfault. J'espère.

Si j'exécute votre code sur ma machine (Intel i7-3770, 16 Go de RAM, Fedora 21) pendant une minute et que je dirige sa sortie vers wc -c, il doit imprimer au moins un million de chiffres de W _∞ pour (W _-1 , W ₀ ) = (1, 0) .

En testant { ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c, j'obtiens 1816784896 chiffres en une minute sur ma machine lorsque le programme a été compilé avec -O3, et 1596678144 quand il a été compilé avec des optimisations désactivées.

Non golfé, pas d'UB, avec explication:

#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 octets)

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

L'entrée doit être une chaîne et non un nombre ( '0'et pas seulement 0).

Perl 5, 45 55 49 octets

44 octets, plus 1 pour -Eau lieu de-e

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

Utiliser comme par exemple

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

Cela imprime des approximations successives de W _∞ et donc, si vous attendez assez longtemps, imprime, sur sa dernière ligne de sortie, W _∞ à n'importe quelle longueur souhaitée, selon les besoins. Les chiffres du mot sont concaténés sans délimiteur.

Depuis que je suis sous Windows, je l'ai testé pour l' exigence «au moins un million de chiffres de W _∞ » en l'exécutant avec une sortie redirigée vers un fichier et en le tuant après environ 59 secondes, puis en exécutant GnuWin32 wc -L, qui imprimait 701408733.

Mise à jour:

L'OP a précisé dans un commentaire sur cette réponse (et j'aurais probablement dû m'en rendre compte de toute façon) que la sortie supplémentaire précédant W _∞ disqualifie ce qui précède. Voici donc une solution de 55 octets qui imprime uniquement W _∞ :

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

Utilisé de la même manière, mais avec les arguments dans l'ordre inverse , et ne nécessite pas -E:

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

Sans aucun doute, il peut être joué plus loin, mais je ne vois pas comment le faire pour le moment.

Mise à jour supplémentaire:

Dennis a rasé cinq octets en utilisant -a(donc en lisant <>pour supprimer sub) et en réaffectant le paramètre passé printà la fin duredo bloc:

Avec -aneet lecture de <>(les deux entrées sur une ligne, séparées par des espaces, dans l'ordre inverse); 48 + 2 octets:

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

Et, sur cette base, j'ai rasé un octet de plus (comme ci-dessus, mais maintenant les entrées sont dans le bon ordre); 47 + 2 octets:

$_=$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

Actuellement, je ne peux pas tester les performances car j'ai utilisé un compilateur en ligne pour l'écrire. Le "pour toujours" peut être remplacé par n'importe quel nombre alors que les numéros ftw imprimés sont (nombre + 2).

J'ai également écrit une petite solution (désordonnée) dans Prolog. Je n'ai pas compris comment tester les performances avec celui-ci, mais c'est probablement atroce de toute façon.

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 octets

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

Accepte l'entrée comme une paire de chaînes séparées par des virgules: "1","0" par exemple dans la question.

Pas d'interprète en ligne car les boucles infinies sont mauvaises. La sortie tamponnée m'a fait gagner beaucoup d'octets. :( Merci Dennis d'avoir souligné qu'un chiffre par ligne est valide.

Synchronisation sur ma machine (significativement plus faible):

$ 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

{⍵∇⍺,⍞←⍵}

Celui-ci utilise ∇pour définir une fonction récursive. C'est une traduction directe de la réponse Python 3 de ce xnor . Il prend W ₀ comme droite et W ₋₁ comme argument gauche, les deux devraient être des vecteurs de caractères.

Minkolang 0,11 , 62 octets

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

Essayez-le ici. Attend une entrée dans l'ordre W ₀ , W _-1 avec un espace entre les deux.

Explication

(                             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

La méta-explication de ce qui suit est qu'à ce stade, nous avons deux nombres suivis d'une chaîne de "0" et de "1" sans séparation. Si les longueurs de W ₀ et W _-1 sont aet b, respectivement, alors les deux nombres à l'avant de la pile sont <a+b>et <a>, dans cet ordre. Le mot formé en concaténant W _{i + 1} et W _i , c'est-à-dire W _{i + 1} + W _i , est égal à 2 * W _{i + 1} - W _i . Ainsi, le code suivant duplique la pile (2 * W _{i + 1} ), apparaît en haut<a>(- W _i ), puis remplace <a+b>et <a>par leurs successeurs, <a+2b>et <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)

La même idée récursive que ma réponse Haskell , sauf que le préfixe est imprimé car Python ne peut pas gérer des chaînes infinies.

Utilisé une astuce de Sp3000 pour imprimer sans espaces en plaçant la chaîne comme endargument dans Python 3

Perl, 32 octets

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

En comptant le shebang comme deux, l'entrée est tirée de stdin, l'espace séparé par W ₀ , W _-1 . Sortie pendant 1 Mo à ~ 15 ms, dont la plupart peuvent être attribuées au lancement de l'interpréteur.

Exemple d'utilisation

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

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

Prolog, 69 octets

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

Exemple d'entrée: p ('1', '0')

N'a pas trouvé de moyen de supprimer l'écriture supplémentaire.
Je devrais pouvoir améliorer cela si je trouve comment faire ça.