Código de Fibonacci Golf
https://stackoverflow.com/questions/232861
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Genera la secuencia de Fibonacci en la menor cantidad de caracteres posible. Cualquier idioma está bien, excepto uno que defina con un operador, f, que imprime los números de Fibonacci.
Punto de partida: 25 14 caracteres en Haskell :
f=0:1:zipWith(+)f(tail f)
f=0:scanl(+)1f
Solución
REPeNt, 9 , 8 caracteres
1↓[2?+1]
O 10 caracteres con impresión:
1↓[2?+↓£1]
Ejecutar usando:
RePeNt "1↓[2?+1]"
RePeNt es un lenguaje de juguete basado en pila que escribí (y sigo mejorando) en el que todos los operadores / funciones / bloques / bucles usan la notación polaca inversa (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 respuesta está en la pila que se acumula como:
1 1
1 1 2
1 1 2 3
1 1 2 3 5
Nunca termina (tiene el privilegio de un bucle C # / JAVA do { } while(true)) porque la secuencia nunca terminará, pero una solución de terminación puede escribirse así:
N_1↓nI{2?+}
que son 12 caracteres.
Me pregunto si alguien alguna vez leerá esto :(
Otros consejos
18 caracteres de inglés ..
" Secuencia de Fibonacci "
ok, fallo. :)
13 caracteres de Golfscript :
2,~{..p@+.}do
Actualización para explicar el funcionamiento del script:
-
2,crea una matriz de[0 1] -
~pone esa matriz en la pila - Entonces, en el momento en que ejecutamos el
do, comenzamos la pila con0 1(1 en la parte superior de la pila)
El bucle .:
- Cada
0 1 1 1duplica el elemento superior de la pila; aquí, hacemos esto dos veces (dejándonos conpen la ejecución inicial) -
0 1 1imprime el valor más alto (dejándonos con@) -
1 1 0gira los 3 elementos superiores en la pila, de modo que el tercero más alto esté en la parte superior (+) -
1 1agrega los 2 elementos principales en la pila (dejando <=>) - <=> duplica el valor superior, para que el bucle <=> pueda verificar su veracidad (para determinar si continúa)
Rastreando esto mentalmente, un par de bucles serán suficientes para decirle que esto hace la suma necesaria para generar los valores de secuencia de Fibonacci.
Dado que GolfScript tiene bignums, nunca habrá un desbordamiento de enteros, por lo que el valor de la parte superior de la pila al final del bucle <=> nunca será 0. Por lo tanto, el script se ejecutará para siempre.
Lenguaje: Errores del compilador C ++
Caracteres: 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 caracteres:
sub f{1,1...{$^a+$^b}}
modo real x86 (invocable en C), 14 bytes.
La entrada es & Nbsp; & Nbsp; n & Nbsp; & Nbsp; en la pila, devuelve & Nbsp; & Nbsp; F n & Nbsp ; & nbsp; en AX.
59 31 C0 E3 08 89 C3 40 93 01 D8 E2 FB C3
Brainfuck , 33 caracteres:
+.>+.[<[>+>+<<-]>.[<+>-]>[<+>-]<]
22 caracteres con CC:
1[pdd5**v1++2/lxx]dsxx
Invocar con:
dc -e'1[pdd5**v1++2/lxx]dsxx'
O:
echo '1[pdd5**v1++2/lxx]dsxx' | dc
Nota: no es mi trabajo, furtivamente de perlmonks .
J , 27 caracteres para una función no recursiva:
f=:3 :'{:}.@(,+/)^:y(0 1x)'
+/ sumas sobre una lista.
(,+/) agrega la suma de una lista a su cola.
}.@(,+/) suma una lista, agrega un elemento a su cola y suelta el primer elemento.
}.@(,+/)^:y itera la función anterior y veces.
}.@(,+/)^:y(0 1x) aplica la función anterior a la lista (0,1) (el x lo convierte en un entero).
{:}.@(,+/)^:y(0 1x) toma el último elemento de la lista de resultados de lo anterior.
f=:3 :'{:}.@(,+/)^:y(0 1x)' define f como una función en una variable <=>.
Para el registro:
- Lua (66 caracteres):
function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end - JavaScript (41 caracteres):
function f(n){return n<2?n:f(n-1)+f(n-2)} - Java (41 caracteres):
int f(int n){return n<2?n:f(n-1)+f(n-2);}
No soy muy experto en lenguajes súper concisos ... :-P
Chris tiene razón, acabo de tomar el algoritmo simple y recursivo. En realidad, el lineal es aún más corto en Lua (gracias a la asignación múltiple). JavaScript no es tan afortunado y Java es peor, tener que declarar vars ...
- Lua (60 caracteres):
function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end - JavaScript (60 caracteres):
function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b} - Java (71 caracteres):
int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}
Escribiría el código de Lua con local a,b=1,0 pero es más largo, ¡así que vamos a contaminar _G! ;-)
Idem para JS.
Para completar, aquí están las versiones recursivas de terminal. El de Lua, que usa la llamada de cola, es tan rápido como el lineal (pero 69 caracteres, ¡es el más largo!). Necesita llamarlos con tres parámetros, n, 1,0.
- Lua (¡69 caracteres, más!):
function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end - JavaScript (44 caracteres):
function f(n,a,b){return n<1?b:f(n-1,b,a+b)} - Java (52 caracteres):
int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}
Corregido después de los comentarios (gracias Sebastian), no era una solución de secuencia, así que aquí vamos con 42 caracteres (incluye el \ n):
def f(a=0,b=1):
while 1:yield a;a,b=b,a+b
ANTIGUA publicación a continuación
Python, 38 caracteres.
f=lambda n:n if n<2 else f(n-1)+f(n-2)
No tan corto pero el más legible en mi opinión: P
EDITAR: Aquí está la forma analítica (si alguien necesita verlo en Python :-)
f=lambda n:int(.5+(.5+5**.5/2)**n/5**.5)
Script por lotes de Windows XP (y versiones posteriores). Esta función de lote cuando se le da un argumento único: cantidad, genera cantidad + 1 números de Fibonacci y los devuelve como una cadena (BATCH realmente no tiene conjuntos) en la variable% r% (369 caracteres o 347 caracteres, si eliminamos la sangría) :
: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
Y aquí está la secuencia de comandos completa, para verla en acción (simplemente cópiela en un archivo CMD o BAT y ejecútela):
@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 caracteres
Viejo desafío, pero el mundo debe saber que es posible:
%1
%0 %1%2 %1 #
La salida es stderr en unario, contando solo los # caracteres. Dependiendo de las restricciones de espacio del sistema host, puede producir solo los primeros 14 números más o menos.
Idioma: dc, recuento de caracteres: 20
Solución de CC más corta.
dc -e'1df[dsa+plarlbx]dsbx'
F #:
(0,1)|>Seq.unfold(fun(a,b)->Some(a,(b,a+b)))
44 caracteres
Aquí está mi mejor esquema de uso, en 45 caracteres:
(let f((a 0)(b 1))(printf"~a,"b)(f b(+ a b)))
MS Excel: 11 caracteres:
=SUM(A1:A2)
Escriba 1 en las 2 celdas superiores, luego coloque la fórmula anterior en la celda A3. Copie la fórmula en la hoja de cálculo.
Comienza a perder precisión debido al redondeo de coma flotante en la fila 74.
Supera 10 ^ 307 y se desborda a un #NUM! error en la fila 1477.
Genera la secuencia de Fibonacci. secuencia SECUENCIA!
C#
Veo muchas respuestas que en realidad no generan la secuencia, sino que solo le dan el número de Fibonacci en la posición * n usando la recursión, que cuando se enlaza para generar la secuencia se vuelve cada vez más lenta a valores más altos 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) ;
}
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 caracteres, pero realmente genera la secuencia, en tiempo lineal.
Ruby (30 caracteres):
def f(n)n<2?n:f(n-1)+f(n-2)end
@Andrea Ambu
Una versión iterativa de pitón fibonacci() debería verse así:
def fibonacci(a=0, b=1):
while True:
yield b
a, b = b, a+b
Lua - 49 caracteres
function f(n)return n<2 and n or f(n-1)+f(n-2)end
Befunge-93
31 caracteres
Producirá una lista infinita de los números de Fibonacci, de 0 en adelante, separados por pestañas (podría reducirse a 29 caracteres eliminando 9, en la primera fila, a expensas de que no haya espacios en blanco entre los números).
Desafortunadamente, todos los intérpretes de Befunge-93 que he intentado parecen desbordar después de 65k, por lo que la salida solo es correcta hasta 46368 (incluido F 24 ).
#v::1p1>01g:.\:01p+9,# > ^
Confirmado para trabajar (con la advertencia anterior) con el intérprete Befunge-93 en Javascript y el Visual Befunge Applet Full .
Estoy orgulloso de decir que este es un trabajo completamente original (es decir, no copié este código de nadie), y es mucho más corto que la solución Befunge actualmente en Rosetta Code .
BrainF ** k:
>+++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
Eso generará los primeros 5. Para generar más, reemplace el 5 + al principio con más: por ejemplo:
>++++++++++++++++++++++>+>+<[[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]>-]
No es el más corto, pero sí el más rápido al momento de la publicación. :-)
float f(float n) {
return (pow(1+sqrt(5.0))/2.0),n) - pow(1+sqrt(5.0))/2.0),n)/sqrt(n));
}
33 caracteres en C:
F(n){return n<2?n:F(n-1)+F(n-2);}Prisma de Delphi (Delphi para .net)
f:func<int32,int32>:=n->iif(n>1,f(n-1)+f(n-2),n)
49 caracteres
El ejemplo anterior de Ruby no funcionará sin punto y coma ni líneas nuevas, por lo que en realidad son 32 caracteres. Aquí está el primer ejemplo para generar realmente la secuencia, no solo devolver el valor de un índice especificado.
Ruby:
53 caracteres, incluidas las nuevas líneas:
def f(n);n<2?1:f(n-1)+f(n-2);end
0.upto 20 {|n|p f n}
o si desea una función que genere una estructura de datos utilizable, 71 caracteres:
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 aceptar argumentos de línea de comando, 70 caracteres:
def f(n);n<2?1:f(n-1)+f(n-2);end
p (0..$*[0].to_i).to_a.map {|n| f(n)}
Ensamblador PDP-11 ( fuente )
.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
