斐波那契代码高尔夫

https://stackoverflow.com/questions/232861

04-07-2019
|

题

用尽可能少的字符生成斐波那契数列。任何语言都可以，除了您用一个运算符定义的语言， f, ，打印斐波那契数列。

初始点： 25 14 个字符 在 哈斯克尔:

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

f=0:scanl(+)1f

解决方案

RePeNt， 9 ，8个字符

1↓[2?+1]

或10个打印字符：

1↓[2?+↓£1]

使用：

运行

RePeNt "1↓[2?+1]"

RePeNt是我编写的基于堆栈的玩具语言（并且仍在改进），其中所有运算符/函数/块/循环都使用反向波兰表示法（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.

答案是在堆栈上构建起来像：

它永远不会终止（它具有C＃/ JAVA do { } while(true)循环的eqivilent），因为序列永远不会终止，但是可以写出终止解决方案：

N_1↓nI{2?+}

这是12个字符。

我想知道是否有人会读到这个：（

其他提示

18个字符的英文..

<！>“Fibonacci序列<！>

好吧，我失败了。：）

Golfscript 的13个字符：

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

更新以解释脚本的操作：

2,生成一个[0 1]
~将该数组放入堆栈
所以，当我们运行do时，我们用0 1（堆栈顶部的1）启动堆栈

.循环：

每个0 1 1 1复制堆栈的顶部项目;在这里，我们这样做两次（在初始运行中留下p）
0 1 1打印最上面的值（留下我们@）
1 1 0旋转堆栈中的前3项，以便第三个顶部位于顶部（+）
1 1添加堆栈中的前2项（离开<=>）
<=>复制最高值，以便<=>循环可以检查其真实性（以确定是否继续）

在精神上跟踪几个循环将足以告诉您这是生成Fibonacci序列值所需的补充。

由于GolfScript有bignums，因此永远不会有整数溢出，因此<=>循环结尾处的堆栈顶部值永远不会为0.因此，脚本将永远运行。

语言：C ++编译器错误
人物：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个字符：

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

x86（C-callable）realmode，14个字节。
输入<！> nbsp; <！> nbsp; n <！> nbsp; <！> nbsp;在堆栈上，返回<！> nbsp; <！> nbsp; F _n <！> nbsp; nbsp; ; <！>在AX。中

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

Brainfuck ，33个字符：

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

带有dc的22个字符：

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

使用以下任一方式调用：

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

或者：

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

注意：不是我的工作，而是从 perlmonks 挖走。

J ，非递归函数有27个字符：

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

+/对列表求和。
(,+/)将列表的总和附加到其尾部。
}.@(,+/)对列表求和，在其尾部附加一个元素，并删除第一个元素 }.@(,+/)^:y迭代上述函数y次。
}.@(,+/)^:y(0 1x)将上述函数应用于列表(0,1)（x使其成为整数）。
{:}.@(,+/)^:y(0 1x)获取上面输出列表的最后一个元素。
f=:3 :'{:}.@(,+/)^:y(0 1x)'将f定义为一个变量<=>的函数。

作为记录：

Lua（66 个字符）： function f(n)if n<2 then return n else return f(n-1)+f(n-2)end end
JavaScript（41 个字符）： function f(n){return n<2?n:f(n-1)+f(n-2)}
Java（41 个字符）： int f(int n){return n<2?n:f(n-1)+f(n-2);}

我不太擅长超级简洁的语言......:-P

克里斯是对的，我只是采用了简单的递归算法。实际上，Lua 中的线性更短（多亏了多重赋值）！JavaScript 就没那么幸运，Java 更糟糕，必须声明变量......

Lua（60 个字符）： function f(n)a=1;b=0;for i=1,n do a,b=b,a+b end return b end
JavaScript（60 个字符）： function f(n){a=1;b=i=0;for(;i++<n;){x=a+b;a=b;b=x}return b}
Java（71 个字符）： int f(int n){int a=1,b=0,i=0;for(;i++<n;){int x=a+b;a=b;b=x;}return b;}

我会用以下方式编写Lua的代码 local a,b=1,0 但它更长，所以让我们污染_G！;-)同上JS。

为了完整起见，这里是终端递归版本。Lua 的使用尾调用，与线性调用一样快（但有 69 个字符，它是最长的！） - 需要用三个参数 n、1、0 来调用它们。

Lua（69 个字符，更长！）： function f(n,a,b)if n<1 then return b else return f(n-1,b,a+b)end end
JavaScript（44 个字符）： function f(n,a,b){return n<1?b:f(n-1,b,a+b)}
Java（52 个字符）： int f(int n,int a,int b){return n<1?b:f(n-1,b,a+b);}

在评论后更正（感谢Sebastian），这不是一个序列解决方案，所以这里我们使用42个字符（包括\ n）：

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

OLD帖子

Python，38个字符。

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

不是那么短，但在我看来最具可读性：P

编辑：这是分析方式（如果有人需要在python中看到它： - ）

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

Windows XP（及更高版本）批处理脚本。当给定单个参数时，此批处理函数 - 金额，生成金额+ 1个斐波那契数并将它们作为字符串返回（BATCH实际上没有集合）在变量％r％中（369个字符，或347个字符 - 如果我们删除缩进）：

: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

这是完整的脚本，可以看到它的实际效果（只需将其复制到CMD或BAT文件并运行它）：

@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个字符

旧的挑战，但世界必须知道它是可能的：

%1
%0 %1%2 %1 #

输出是staryr in anary，只计算＃个字符。根据主机系统的空间限制，它可能只产生前14个数字左右。

语言：dc，字数：20

更短的直流解决方案。

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

F＃：

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

44 Chars

这是我最好的使用方案，有45个字符：

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

MS Excel：11个字符：

=SUM(A1:A2)

在前2个单元格中键入1，然后将上述公式放在单元格A3中。将公式复制到电子表格中。

由于第74行浮点舍入而开始失去准确性。
超过10 ^ 307并溢出到第1477行的#NUM!错误。

生成斐波纳契数列。序列 SEQUENCE！

<强> C＃

我看到很多答案实际上并没有产生序列，而是只使用递归给你位置* n的斐波纳契数，当循环生成序列时，在更高的值< EM>名词的

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个字符，但在线性时间内真正生成序列。

Ruby（30个字符）：

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

@Andrea Ambu

迭代pythonic fibonacci()的版本看起来应该是这样的：

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

Lua - 49个字符

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

Befunge-93

31个字符

将输出无限的Fibonacci数字列表，从0开始，由制表符分隔（通过删除第一行中的9,，可以减少到29个字符，代价是数字之间没有空格）。

不幸的是，我尝试过的所有Befunge-93解释器似乎都在65k后溢出，所以输出只有正确才能包括46368（ F ₂₄ ）。

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

使用 Javascript中的Befunge-93解释器确认工作（上面有警告）和 Visual Befunge Applet Full 。

我很自豪地说这是一个完全原创的作品（即我没有从任何人复制此代码），它比目前使用Rosetta Code的Befunge解决方案。

BrainF ** K：

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

那将生成第一个5.要生成更多，请将更多的5 +替换为更多：例如：

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

不是最短的，但在发布时最快。： - ）

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

C中的33个字符：

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

Delphi Prism（Delphi for .net）

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

49个字符

以前的Ruby示例无法使用分号或换行符，因此它实际上是32个字符。这是实际输出序列的第一个示例，而不仅仅是返回指定索引的值。

红宝石：结果 53个字符，包括换行符：

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

或者如果你想要输出可用数据结构的函数，71个字符：

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

或接受命令行参数，70个字符：

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

PDP-11汇编程序（来源）

    .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

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow