Fibonacci Code Golf

Question

Générez la séquence de Fibonacci avec le moins de caractères possible. Toutes les langues sont acceptables, à l’exception de celle que vous définissez avec un seul opérateur, f, qui affiche les numéros de Fibonacci.

Point de départ: 25 14 caractères dans Haskell :

f=0:1:zipWith(+)f(tail f)

f=0:scanl(+)1f

Answer 1

REPONSE, 9 , 8 caractères

1↓[2?+1]

Ou 10 caractères avec impression:

1↓[2?+↓£1]

Exécuter en utilisant:

RePeNt "1↓[2?+1]"

RePeNt est un langage jouet basé sur une pile que j’ai écrit (et que je suis en train d’améliorer) et dans lequel tous les opérateurs / fonctions / blocs / boucles utilisent la notation polonaise inversée (RPN).

Command      Explanation                                              Stack
-------      -----------                                              -----

1            Push a 1 onto the stack                                  1
↓            Push last stack value                                    1 1
[            Start a do-while loop                                    1 1
2?           Push a two, then pop the 2 and copy the last 2 stack     1 1 1 1
             items onto the stack
+            Add on the stack                                         1 1 2
↓£           Push last stack value then print it                      1 1 2
1            Push a 1 onto the stack                                  1 1 2 1
]            Pop value (1 in this case), if it is a 0 exit the loop   1 1 2
             otherwise go back to the loop start.

La réponse est sur la pile qui se construit comme:

1 1
1 1 2
1 1 2 3
1 1 2 3 5

Il ne se termine jamais (il a l’équivalent d’une boucle C # / JAVA do { } while(true)) car la séquence ne se terminera jamais, mais une solution finale peut s’écrire ainsi:

N_1↓nI{2?+}

qui est 12 caractères.

Je me demande si quelqu'un lira jamais ceci: (

Answer 2

18 caractères d'anglais.

& "Séquence de Fibonacci" & ";

ok, j'échoue. :)

Answer 3

13 caractères de Golfscript :

2,~{..p@+.}do

Mise à jour pour expliquer le fonctionnement du script:

1. 2, crée un tableau de [0 1]
2. ~ place ce tableau sur la pile
3. Ainsi, au moment où nous exécutons do, nous démarrons la pile avec 0 1 (1 en haut de la pile)

La . boucle:

1. Chaque 0 1 1 1 duplique le premier élément de la pile; ici, nous faisons cela deux fois (nous laissant avec p lors de la première exécution)
2. 0 1 1 affiche la valeur la plus haute (nous laissant avec @)
3. 1 1 0 fait pivoter les 3 premiers éléments de la pile, de sorte que le troisième en haut se trouve en haut (+)
4. 1 1 ajoute les 2 premiers éléments de la pile (en laissant <=>)
5. <=> duplique la valeur supérieure, de sorte que la boucle <=> puisse vérifier sa véracité (pour déterminer si elle doit continuer)

En traçant mentalement cela, deux boucles suffiront pour vous dire que cela constitue l’ajout nécessaire pour générer les valeurs de séquence de Fibonacci.

Puisque GolfScript a des bignums, il n’y aura jamais de dépassement d’entier et la valeur du haut de la pile à la fin de la boucle <=> ne sera jamais égale à 0. Le script sera exécuté à jamais.

Answer 4

Langue: erreurs de compilation C ++
Caractères: 205

#define t template <int n> struct 
#define u template <> struct f
t g { int v[0]; };
t f { enum { v = f<n-1>::v + f<n-2>::v }; g<v> x;};
u<1> { enum { v = 1 }; };
u<0> { enum { v = 0 }; };
int main() { f<10> x; }

Answer 5

Perl 6 - 22 caractères:

sub f{1,1...{$^a+$^b}}

Answer 6

Mode réel x86 (appelable en C), 14 octets.
L'entrée est & Nbsp; & Nbsp; n & Nbsp; & Nbsp; sur la pile, renvoie & Nbsp; & Nbsp; F _n & Nbsp ; & nbsp; in AX.

59 31 C0 E3 08 89 C3 40 93 01 D8 E2 FB C3

Answer 7

Brainfuck , 33 caractères:

+.>+.[<[>+>+<<-]>.[<+>-]>[<+>-]<]

Answer 8

22 caractères avec dc:

1[pdd5**v1++2/lxx]dsxx

Invoquer avec soit:

dc -e'1[pdd5**v1++2/lxx]dsxx'

Ou:

echo '1[pdd5**v1++2/lxx]dsxx' | dc

Remarque: ce n'est pas mon travail, extrait de perlmonks .

Answer 9

J , 27 caractères pour une fonction non récursive:

f=:3 :'{:}.@(,+/)^:y(0 1x)'

+/ somme sur une liste.
(,+/) ajoute la somme d'une liste à sa queue.
}.@(,+/) additionne une liste, ajoute un élément à sa queue et supprime le premier élément.
}.@(,+/)^:y itère la fonction ci-dessus y fois.
}.@(,+/)^:y(0 1x) applique la fonction ci-dessus à la liste (0,1) (le x en fait un entier).
{:}.@(,+/)^:y(0 1x) prend le dernier élément de la liste de sortie de ce qui précède.
f=:3 :'{:}.@(,+/)^:y(0 1x)' définit f comme étant une fonction sur une variable <=>.

Answer 10

Pour mémoire:

• Lua (66 caractères): function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end
• JavaScript (41 caractères): function f(n){return n<2?n:f(n-1)+f(n-2)}
• Java (41 caractères): int f(int n){return n<2?n:f(n-1)+f(n-2);}

Je ne suis pas un grand adepte des langages super concis ... :-P

Chris a raison, je viens de prendre l’algorithme simple et récursif. En réalité, le linéaire est encore plus court en Lua (grâce aux assignations multiples)! JavaScript n’est pas si chanceux et Java est pire, il faut déclarer des vars ...

• Lua (60 caractères): function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end
• JavaScript (60 caractères): function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b}
• Java (71 caractères): int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}

J'écrirais le code de Lua avec local a,b=1,0 mais il est plus long, alors polluons _G! ;-) Idem pour JS.

Pour être complet, voici les versions récursives du terminal. Celui de Lua, en utilisant l'appel final, est aussi rapide que le linéaire (mais 69 caractères, il est le plus long!) - il faut les appeler avec trois paramètres, n, 1,0.

• Lua (69 caractères, plus long!): function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end
• JavaScript (44 caractères): function f(n,a,b){return n<1?b:f(n-1,b,a+b)}
• Java (52 caractères): int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}

Answer 11

Corrigé après les commentaires (merci Sebastian), ce n'était pas une solution de séquence, alors allons-y avec 42 caractères (inclut le \ n):

def f(a=0,b=1):
 while 1:yield a;a,b=b,a+b

Ancien message ci-dessous

Python, 38 caractères.

f=lambda n:n if n<2 else f(n-1)+f(n-2)

Pas si court mais le plus lisible à mon avis: P

EDIT: Voici le moyen analytique (si quelqu'un a besoin de le voir en python: -)

f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)

Answer 12

Script de traitement par lots de Windows XP (et versions ultérieures). Cette fonction de traitement par lots lorsqu'un seul argument - montant, génère un montant + 1 nombre Fibonacci et les renvoie sous forme de chaîne (BATCH n'a pas vraiment d'ensembles) dans la variable% r% (369 caractères ou 347 caractères - si nous supprimons l'indentation) :

:f
    set i=0
    set r=1
    set n=1
    set f=0
    :l
        if %n% GTR %~1 goto e
        set f=%f% %r%
        set /A s=%i%+%r%
        set i=%r%
        set r=%s%
        set /A n+=1
        goto l
    :e
    set r=%f%
    exit /B 0

Et voici le script complet, pour le voir en action (copiez-le simplement dans un fichier CMD ou BAT et exécutez-le):

@echo off
call :ff 0
call :ff 1
call :ff 2
call :ff 3
call :ff 5
call :ff 10
call :ff 15
call :ff 20
exit /B 0

:ff
    call :f "%~1"
    echo %~1: %r%
    exit /B 0

:f
    set i=0
    set r=1
    set n=1
    set f=0
    :l
        if %n% GTR %~1 goto e
        set f=%f% %r%
        set /A s=%i%+%r%
        set i=%r%
        set r=%s%
        set /A n+=1
        goto l
    :e
    set r=%f%
    exit /B 0

Answer 13

Microsoft Batch - 15 caractères

Ancien défi, mais le monde doit savoir que c'est possible:

%1
%0 %1%2 %1 #

La sortie est stderr en unaire, en ne comptant que les caractères #. Selon les restrictions d'espace du système hôte, il se peut que seuls les 14 premiers chiffres soient générés.

Answer 14

Langue: dc, Nombre de caractères: 20

Solution de courant continu plus courte.

dc -e'1df[dsa+plarlbx]dsbx'

Answer 15

F #:

(0,1)|>Seq.unfold(fun(a,b)->Some(a,(b,a+b)))

44 caractères

Answer 16

Voici mon meilleur schéma d'utilisation, composé de 45 caractères:

(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))

Answer 17

MS Excel: 11 caractères:

=SUM(A1:A2)

Tapez 1 dans les 2 premières cellules, puis placez la formule ci-dessus dans la cellule A3. Copiez la formule dans la feuille de calcul.

Commence à perdre de la précision en raison de l'arrondissement des nombres en virgule flottante à la ligne 74.
Dépasse 10 ^ 307 et déborde sur une #NUM! erreur à la ligne 1477.

Answer 18

Générez la séquence de Fibonacci. séquence SEQUENCE!

Answer 19

C #

Je vois beaucoup de réponses qui ne génèrent pas réellement la séquence, mais vous donnent uniquement le nombre fibonacci à la position * n en utilisant la récursion, qui, une fois en boucle pour générer la séquence, devient de plus en plus lent à des valeurs plus élevées de < em> n .

using System;
static void Main()
{
  var x = Math.Sqrt(5);
  for (int n = 0; n < 10; n++)
    Console.WriteLine((Math.Pow((1 + x) / 2, n) - Math.Pow((1 - x) / 2, n)) / p) ;
}

Answer 20

let rec f l a b =function 0->a::l|1->b::l|n->f (a::l) b (a+b) (n-1) in f [] 1 1;;

80 caractères, mais génère réellement la séquence, en temps linéaire.

Answer 21

Ruby (30 caractères):

def f(n)n<2?n:f(n-1)+f(n-2)end

Answer 22

@Andrea Ambu

Une version pythonique itérative fibonacci() devrait ressembler à ceci:

def fibonacci(a=0, b=1):
    while True:
        yield b
        a, b = b, a+b

Answer 23

Lua - 49 caractères

function f(n)return n<2 and n or f(n-1)+f(n-2)end

Answer 24

Befunge-93

31 caractères

Générera une liste infinie des nombres de Fibonacci, à partir de 0, séparés par des tabulations (pourrait être réduit à 29 caractères en supprimant 9, dans la première ligne, au détriment des espaces entre les nombres).

Malheureusement, tous les interprètes de Befunge-93 que j'ai essayés semblent déborder après 65k, de sorte que la sortie n'est correcte que jusqu'à 46368 (qui est F ₂₄ . ).

#v::1p1>01g:.\:01p+9,#
 >     ^

Confirmation de travailler (avec l'avertissement ci-dessus) avec l'interprète Befunge-93 en Javascript et à la l'applet Visual Befunge Full .

Je suis fier de dire qu'il s'agit d'un travail complètement original (c'est-à-dire que je n'ai pas copié ce code), et qu'il est beaucoup plus court que la solution Befunge actuellement disponible sur Rosetta Code .

Answer 25

BrainF ** k:

>+++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]

Cela va générer le premier 5. Pour générer plus, remplacez le 5 + au début par plus: par exemple:

>++++++++++++++++++++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]

Answer 26

Pas le plus court, mais le plus rapide au moment de la publication. : -)

float f(float n) {
    return (pow(1+sqrt(5.0))/2.0),n) - pow(1+sqrt(5.0))/2.0),n)/sqrt(n));
}

Answer 27

33 caractères en C:

F(n){return n<2?n:F(n-1)+F(n-2);}

Answer 28

Prisme Delphi (Delphi pour .net)

f:func<int32,int32>:=n->iif(n>1,f(n-1)+f(n-2),n)

49 caractères

Answer 29

L'exemple précédent de Ruby ne fonctionnera pas, ni point-virgule, ni nouvelle ligne, c'est donc 32 caractères. Voici le premier exemple de sortie de la séquence, pas seulement la valeur d'un index spécifié.

Ruby:
53 caractères, y compris les nouvelles lignes:

def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}

ou si vous souhaitez une fonction générant une structure de données utilisable, 71 caractères:

def f(n);n<2?1:f(n-1)+f(n-2);end
def s(n);(0..n).to_a.map {|n| f(n)};end

ou en acceptant les arguments de ligne de commande, 70 caractères:

def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}

Answer 30

Assembleur PDP-11 ( source )

    .globl  start
    .text
start:
    mov $0,(sp)
    mov $27,-(sp)
    jsr pc, lambda
print_r1:
    mov $outbyte,r3
div_loop:
    sxt r0
    div $12,r0
    add $60,r1
    movb    r1,-(r3)
    mov r0,r1
    tst r1
    jne div_loop
    mov $1,r0
    sys 4; outtext; 37
    mov $1,r0
    sys 1
lambda:
    mov 2(sp),r1
    cmp $2,r1
    beq gottwo
    bgt gotone
    sxt r0
    div $2,r0
    tst r1
    beq even
odd:
    mov 2(sp),r1
    dec r1
    sxt r0
    div $2,r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r3,r4
    mul r2,r4
    mov r5,r1
    mov r3,r4
    add r2,r4
    mul r2,r4
    add r5,r1
    mul r3,r3
    mov r3,r0
    mul r2,r2
    add r3,r0
    rts pc
even:
    mov 2(sp),r1
    sxt r0
    div $2,r0
    dec r0
    mov r0,-(sp)
    jsr pc,lambda
    add $2,sp
    mov r0,r3
    mov r1,r2
    mov r2,r4
    mul r2,r4
    mov r5,r1
    mov r2,r4
    add r3,r4
    mul r4,r4
    add r5,r1
    mov r2,r4
    add r3,r4
    mul r2,r4
    mov r5,r0
    mul r2,r3
    add r3,r0
    rts pc
gotone:
    mov $1,r0
    mov $1,r1
    rts pc
gottwo:
    mov $1,r0
    mov $2,r1
    rts pc

    .data
outtext:
    .byte 62,63,162,144,40,106,151,142,157,156
    .byte 141,143,143,151,40,156,165,155
    .byte 142,145,162,40,151,163,40
    .byte 60,60,60,60,60
outbyte:
    .byte 12