Fibonacci Code Golf
https://stackoverflow.com/questions/232861
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Genera la sequenza di Fibonacci nel minor numero di caratteri possibile. Qualsiasi lingua è OK, ad eccezione di quella definita con un operatore, f, che stampa i numeri di Fibonacci.
Punto di partenza: 25 14 caratteri in Haskell :
f=0:1:zipWith(+)f(tail f)
f=0:scanl(+)1f
Soluzione
REPeNt, 9 , 8 caratteri
1↓[2?+1]
O 10 caratteri con la stampa:
1↓[2?+↓£1]
Esegui utilizzando:
RePeNt "1↓[2?+1]"
RePeNt è un linguaggio giocattolo basato su stack che ho scritto (e sto ancora migliorando) in cui tutti gli operatori / funzioni / blocchi / loop usano Reverse Polish Notation (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 risposta è nello stack che si accumula come:
1 1
1 1 2
1 1 2 3
1 1 2 3 5
Non termina mai (ha l'eqivilent di un ciclo C # / JAVA do { } while(true)) perché la sequenza non si chiuderà mai, ma una soluzione di terminazione può essere scritta così:
N_1↓nI{2?+}
ovvero 12 caratteri.
Mi chiedo se qualcuno leggerà mai questo :(
Altri suggerimenti
18 caratteri dell'inglese ..
" Sequenza di Fibonacci "
ok, non ci riesco. :)
13 caratteri di Golfscript :
2,~{..p@+.}do
Aggiornamento per spiegare il funzionamento dello script:
-
2,crea una matrice di[0 1] -
~mette quell'array nello stack - Quindi, quando eseguiamo
do, iniziamo lo stack con0 1(1 in cima allo stack)
Il ciclo .:
- Ciascuno
0 1 1 1duplica l'elemento in cima alla pila; qui, lo facciamo due volte (lasciandoci conpalla prima esecuzione) -
0 1 1stampa il valore più alto (lasciandoci con@) -
1 1 0ruota i primi 3 elementi nella pila, in modo che il terzo più in alto sia in cima (+) -
1 1aggiunge i primi 2 elementi nello stack (lasciando <=>) - <=> duplica il valore più alto, in modo che il ciclo <=> possa verificarne la veridicità (per determinare se continuare)
Tracciando mentalmente un paio di loop sarà sufficiente per dirti che questo fa l'aggiunta richiesta per generare i valori della sequenza di Fibonacci.
Dato che GolfScript ha i bignum, non ci sarà mai un overflow di numeri interi, e quindi il valore top-of-stack alla fine del ciclo <=> non sarà mai 0. Quindi, lo script verrà eseguito per sempre.
Lingua: errori del compilatore C ++
Personaggi: 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; }
Perl 6 - 22 caratteri:
sub f{1,1...{$^a+$^b}}
x86 (callable) realmode, 14 byte.
L'input è & Nbsp; & Nbsp; n & Nbsp; & Nbsp; in pila, restituisce & Nbsp; & Nbsp; F n & Nbsp ; & nbsp; in AX.
59 31 C0 E3 08 89 C3 40 93 01 D8 E2 FB C3
Brainfuck , 33 caratteri:
+.>+.[<[>+>+<<-]>.[<+>-]>[<+>-]<]
22 caratteri con dc:
1[pdd5**v1++2/lxx]dsxx
Richiamare con:
dc -e'1[pdd5**v1++2/lxx]dsxx'
o
echo '1[pdd5**v1++2/lxx]dsxx' | dc
Nota: non sono lavori miei, presi in giro da perlmonks .
J , 27 caratteri per una funzione non ricorsiva:
f=:3 :'{:}.@(,+/)^:y(0 1x)'
+/ somma su un elenco.
(,+/) aggiunge la somma di un elenco alla sua coda.
}.@(,+/) somma un elenco, aggiunge un elemento alla coda e rilascia il primo elemento.
}.@(,+/)^:y ripete la funzione sopra y volte.
}.@(,+/)^:y(0 1x) applica la funzione sopra all'elenco (0,1) (il x lo rende un numero intero).
{:}.@(,+/)^:y(0 1x) accetta l'ultimo elemento dell'elenco di output di cui sopra.
f=:3 :'{:}.@(,+/)^:y(0 1x)' definisce f di essere una funzione su una variabile <=>.
Per la cronaca:
- Lua (66 caratteri):
function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end - JavaScript (41 caratteri):
function f(n){return n<2?n:f(n-1)+f(n-2)} - Java (41 caratteri):
int f(int n){return n<2?n:f(n-1)+f(n-2);}
Non sono molto esperto di linguaggi super concisi ... :-P
Chris ha ragione, ho appena preso l'algoritmo semplice e ricorsivo. In realtà, quello lineare è ancora più breve in Lua (grazie ad assegnazioni multiple)! JavaScript non è così fortunato e Java è peggio, dover dichiarare vari ...
- Lua (60 caratteri):
function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end - JavaScript (60 caratteri):
function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b} - Java (71 caratteri):
int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}
Scriverei il codice di Lua con local a,b=1,0 ma è più lungo, quindi inquiniamo _G! ;-)
Idem per JS.
Per completezza, ecco le versioni ricorsive del terminale. Quello di Lua, usando la coda, è veloce come quello lineare (ma 69 caratteri, è il più lungo!) - è necessario chiamarli con tre parametri, n, 1,0.
- Lua (69 caratteri, più a lungo!):
function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end - JavaScript (44 caratteri):
function f(n,a,b){return n<1?b:f(n-1,b,a+b)} - Java (52 caratteri):
int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}
Corretto dopo i commenti (grazie Sebastian), non era una soluzione di sequenza, quindi eccoci con 42 caratteri (include il \ n):
def f(a=0,b=1):
while 1:yield a;a,b=b,a+b
VECCHIO post qui sotto
Python, 38 caratteri.
f=lambda n:n if n<2 else f(n-1)+f(n-2)
Non così breve ma il più leggibile secondo me: P
EDIT: Ecco il modo analitico (se qualcuno ha bisogno di vederlo in Python :-)
f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)
Script batch di Windows XP (e versioni successive). Questa funzione batch quando viene fornito un singolo argomento - quantità, genera quantità + 1 numeri di Fibonacci e li restituisce come una stringa (BATCH non ha davvero set) nella variabile% r% (369 caratteri o 347 caratteri - se rimuoviamo il rientro) :
: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
Ed ecco lo script completo, per vederlo in azione (basta copiarlo e incollarlo in un file CMD o BAT ed eseguirlo):
@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
Microsoft Batch - 15 caratteri
Vecchia sfida, ma il mondo deve sapere che è possibile:
%1
%0 %1%2 %1 #
L'output è stderr in unario, contando solo i # caratteri. A seconda delle restrizioni di spazio del sistema host, può produrre solo i primi 14 numeri circa.
Lingua: dc, Conteggio caratteri: 20
Soluzione cc più breve.
dc -e'1df[dsa+plarlbx]dsbx'
F #:
(0,1)|>Seq.unfold(fun(a,b)->Some(a,(b,a+b)))
44 caratteri
Ecco il mio schema di utilizzo migliore, in 45 caratteri:
(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))
MS Excel: 11 caratteri:
=SUM(A1:A2)
Digita 1 nelle prime 2 celle, quindi inserisci la formula sopra nella cella A3. Copia la formula nel foglio di calcolo.
Inizia a perdere la precisione a causa dell'arrotondamento in virgola mobile sulla riga 74.
Supera 10 ^ 307 e trabocca in un errore #NUM! nella riga 1477.
Genera la sequenza di Fibonacci. sequenza SEQUENZA!
C #
Sto vedendo molte risposte che in realtà non generano la sequenza, ma invece ti danno solo il numero di fibonacci in posizione * n usando la ricorsione, che quando si esegue il ciclo per generare la sequenza diventa sempre più lento a valori più alti di < 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) ;
}
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 caratteri, ma genera veramente la sequenza, in tempo lineare.
Ruby (30 caratteri):
def f(n)n<2?n:f(n-1)+f(n-2)end
@Andrea Ambu
Una versione iterativa di Pythonic fibonacci() dovrebbe assomigliare a questa:
def fibonacci(a=0, b=1):
while True:
yield b
a, b = b, a+b
Lua - 49 caratteri
function f(n)return n<2 and n or f(n-1)+f(n-2)end
Befunge-93
31 caratteri
Produrrà un elenco infinito di numeri di Fibonacci, da 0 in su, separati da tabulazioni (potrebbe essere ridotto a 29 caratteri cancellando 9, nella prima riga, a scapito di uno spazio bianco tra i numeri).
Sfortunatamente, tutti gli interpreti di Befunge-93 che ho provato sembrano traboccare dopo 65k, quindi l'output è corretto solo fino al 46368 incluso (che è F 24 ).
#v::1p1>01g:.\:01p+9,# > ^
Confermato di funzionare (con avvertenza sopra) con l'interprete Befunge-93 in Javascript e Visual Befunge Applet Full .
Sono orgoglioso di dire che questo è un lavoro completamente originale (cioè non ho copiato questo codice da nessuno), ed è molto più breve di la soluzione Befunge attualmente sul codice Rosetta .
Brainf ** k:
>+++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
Questo genererà il primo 5. Per generare di più, sostituisci 5 + all'inizio con more: ad esempio:
>++++++++++++++++++++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
Non il più breve, ma il più veloce al momento della pubblicazione. : -)
float f(float n) {
return (pow(1+sqrt(5.0))/2.0),n) - pow(1+sqrt(5.0))/2.0),n)/sqrt(n));
}
33 caratteri in C:
F(n){return n<2?n:F(n-1)+F(n-2);}Delphi Prism (Delphi per .net)
f:func<int32,int32>:=n->iif(n>1,f(n-1)+f(n-2),n)
49 caratteri
Il precedente esempio di Ruby non funzionerà senza punti e virgola o newline, quindi in realtà sono 32 caratteri. Ecco il primo esempio per generare effettivamente la sequenza, non solo per restituire il valore di un indice specificato.
Rubino:
53 caratteri, comprese le nuove righe:
def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}
o se si desidera una funzione che genera una struttura dati utilizzabile, 71 caratteri:
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
o accettando args da riga di comando, 70 caratteri:
def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}
Assemblatore 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
