フィボナッチコードゴルフ

https://stackoverflow.com/questions/232861

04-07-2019
|

質問

可能な限り少ない文字数でフィボナッチ数列を生成します。フィボナッチ数を出力する1つの演算子fで定義した言語を除き、どの言語でも構いません。

開始点： Haskell の 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)ループと同等です）が、次のように終了ソリューションを記述できます。

N_1↓nI{2?+}

これは12文字です。

誰もこれを読むことはないだろうか：（

他のヒント

英語の18文字..

<！> quot;フィボナッチ数列<！> quot;

OK、失敗しました。：）

ゴルフスクリプトの13文字：

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

スクリプトの動作を説明するための更新：

2,は[0 1]
~はその配列をスタックに置きます
つまり、doを実行するとき、0 1（スタックの先頭に1）でスタックを開始します

.ループ：

各0 1 1 1は、スタックの一番上のアイテムを複製します。ここでは、これを2回実行します（最初の実行時にpのままにします）
0 1 1は最上位の値を出力します（@のままにしておきます）
1 1 0は、スタック内の上位3アイテムを回転させ、3番目の最上位が最上位（+）
1 1は、スタックの上位2項目を追加します（<=>を残します）
<=>は最上位の値を複製するため、<=>ループは（続行するかどうかを判断するために）真実性をチェックできます

これをメンタルにたどると、フィボナッチ数列値を生成するために必要な追加が行われることを伝えるのに2、3ループで十分です。

GolfScriptにはbignumがあるため、整数オーバーフローが発生することはありません。したがって、<=>ループの最後のスタックの値は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呼び出し可能）リアルモード、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を1つの変数<=>の関数として定義します。

記録用：

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のIdem。

完全を期すために、ここに端末の再帰バージョンがあります。テールコールを使用したLuaのコードは、線形のコードと同じくらい高速です（ただし、69文字、最長です！）-3つのパラメーター、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);}

コメントの後に修正（セバスチャンに感謝）、これはシーケンスソリューションではなかったため、ここでは42文字（\ nを含む）を使用します。

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

下の古い投稿

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フィボナッチ数を生成し、変数％r％（369文字、または347文字-インデントを削除する場合）の文字列（BATCHには実際にセットはありません）としてそれらを返します：

: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 #

出力は、＃文字のみをカウントして、単項形式でstderrに出力されます。ホストシステムのスペース制限に応じて、最初の14個程度の数字しか生成されない場合があります。

言語：dc、文字数：20

短いDCソリューション。

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

F＃：

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

44文字

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!エラーにオーバーフローします。

フィボナッチ数列を生成します。シーケンスシーケンス！

C＃

実際にシーケンスを生成しない多くの回答がありますが、代わりに再帰を使用して位置* nのフィボナッチ数のみを提供します。これはループを生成するためにループすると、< 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文字ですが、線形時間で実際にシーケンスを生成します。

ルビー（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文字

タブで区切られたフィボナッチ数の無限リストを0から上に出力します（最初の行の9,を削除することで29文字に減らすことができますが、数字の間に空白はありません）。

残念なことに、私が試したすべてのBefunge-93インタープリターは65k後にオーバーフローするようです。そのため、出力は46368（ F ₂₄まで））。

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

JavascriptのBefunge-93インタープリターで動作することを確認（上記の警告付き） >および Visual BefungeアプレットFull 。

これは完全にオリジナルの作品であると自負しています（つまり、このコードを誰からもコピーしなかった）。現在Rosetta CodeにあるBefungeソリューション。

BrainF ** k：

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

最初の5を生成します。さらに生成するには、先頭の5 +をmoreに置き換えます。例：

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

最短ではなく、投稿時の最速。：-）

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（.netのDelphi）

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