フィボナッチ数列は数のシーケンスであり、すべての数がシーケンス内には、その前にある2つの数値の合計があります。シーケンスの最初の2つの数字は両方とも1です。
最初のいくつかの用語は次のとおりです
1 1 2 3 5 8 13 21 34 55 89 ...
最短のコードを記述します
-
フィボナッチ数列を終わりなく生成します。
-
与えられた
n
シーケンスのn
番目の項を計算します。 (インデックスが1またはゼロのいずれか)
標準形式の入力と出力を使用できます。
(どちらかが簡単な場合に備えて、両方のオプションを指定しました。選択した言語で他の言語よりも実行してください。)
n
を受け取る関数の場合、かなり大きな戻り値(最大のフィボナッチ数コンピュータの通常のワードサイズに少なくとも適合します)をサポートする必要があります。
リーダーボード
/* Configuration */ var QUESTION_ID = 85; // Obtain this from the url // It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 3; // This should be the user ID of the challenge author. /* App */ var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(";") + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = "<h1>" + c.body.replace(OVERRIDE_REG, "") + "</h1>"; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery("<a>"+lang+"</a>").text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1; if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }
body { text-align: left !important; display: block !important; } #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f"> <div> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody> </tbody> </table> </div> <div> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody> </tbody> </table> </div> <table style="display: none"> <tbody> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>
コメント
- " f "、1バイト、数学ベースのゴルフ言語。
回答
Perl 6、10文字:
匿名の無限フィボナッチ数列リスト:
^2,*+*...*
同じ:
0, 1, -> $x, $y { $x + $y } ... Inf;
したがって、配列に割り当てることができます:
my @short-fibs = ^2, * + * ... *;
または
my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;
次のコマンドで最初の11個の値(0〜10)を取得します:
say @short-fibs[^11];
または次のコマンド:
say @fibs[^11];
待ってください。匿名リスト自体から最初の50個の数字を取得することもできます:
say (^2,*+*...*)[^50]
戻り値:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049
そしていくつかの簡単なベンチマーク:
real 0m0.966s user 0m0.842s sys 0m0.080s
使用:
$ time perl6 -e "say (^2, *+* ... *)[^50]"
EOF
コメント
- 私は'とは思わない
^2
の0,1
の代わりに使用します。 +1 - これは無効になりました。
|^2,*+*...*
と記述する必要があります。これは。 - Perlはとても奇妙です。
- この回答はどのバージョンのPerl6で書かれましたか?
- @CalculatorFeline大きな変更がありました。 2015年12月25日に行われた最初の公式リリースの直前に発生したGLR(Great List Refactor)として知られています。このコードはそれまでは機能していました。
回答
Brainfuck、22ストローク
+>++[-<<[->+>+<<]>>>+]
メモリテープ上を徐々に移動するフィボナッチ数列を生成します。
コメント
- 美しい!文字通り美しい!または、そうではないかもしれません…とにかくこれは+1です:)
- これは圧縮されたbrainfuckの3.344または 4 バイトです。 (6 ln(22))/ ln(256)
- 16バイト:
+[[<+>->+>+<<]>]
- 14バイト:
+[.[>+>+<<-]>]
- @Stefnotchもちろん、短い方が破壊的です。上記のソリューションは、テープ上のフィボナッチ数列で終了します。これは、16バイトのソリューションでも実行されます。
回答
Haskell、 17 15 14文字
f=1:scanl(+)1f
コメント
-
f=0:scanl(+)1 f
? - @Martinho:編集しました。ありがとうございます。
- うわー、'は通常の
f@(_:x)=0:1:zipWith(+)f x
!覚えておく必要があります。 - 別のスペースを削除することもできます:
f=0:scanl(+)1f
。
回答
C#4、58バイト
ストリーム(69; IEnumerable
)
(iv id = “のusing
ディレクティブを想定d02d48a48f “>
。)
IEnumerable<int>F(){int c=0,n=1;for(;;){yield return c;n+=c;c=n-c;}}
単一値(58)
int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}
コメント
- 与えられた
n
はuint
であり、n==0
はn<1
に短縮できます。また、ストリームは、ジェネリック型の後にスペースを捨て、必要以上に広いスコープでx
を宣言することで、数文字を節約できます。実際、溝x
全体:n+=c;c=n-c;
- @Peter:ありがとうございます。時間があれば編集します。
- 単一値バージョンは、再帰的なラムダ式が答える限りです…いいですね!
- @ wizzwizz4 if I ' m not間違って、
!n
が機能する場合、条件を反転するとn
が機能するはずです。 - @JonSkeetAw。そして、ここで私は' C#でジョンスキートを倒したと思っていました… 🙂
回答
GolfScript、12
これで12文字になりました!
1.{[email protected]+.}do
コメント
- +1いい仕事。 13文字より短くすると、'すぐに回答を受け入れます(もちろん、誰かがさらに短い回答をしない限り)。 😛
- チャレンジが大好きです。完了! 😉
- いいですね、あなたが勝ちます。少なくとも、誰かが何かをさらに短くするまで('可能であれば)。 😛
- その定義は、'フィボナッチ'自体の名前とほぼ同じくらい短いです。 +1
回答
J、10文字
組み込みの計算を使用テイラー級数係数なので、少し安っぽいかもしれません。 ここで学習しました。
(%-.-*:)t. (%-.-*:)t. 0 1 2 3 4 5 10 100 0 1 1 2 3 5 55 354224848179261915075
コメント
- @aditsu
(q:^-^:p) 6
は64 729
で、pは偶数です。 Jはおそらくそれが何をするのかのなぞなぞに適しています。 🙂 - さらに良い:
(<:^-^:>) 4
は81
および<:^-^:> 4
ですは53.5982
です。 - ここで示す絵文字は、すべてのJコードが目指すべきものです。ちなみに、もう1つの方法は、9バイトを使用する
+/@:!&i.-
です。 - @milesとてもいいです!自分のものとはまったく違うので投稿してください。
回答
> < > -15文字
0:nao1v a+@:n:<o
コメント
- ただし、
0:nao1v LF a+@:n:<o
必要に応じて。 15を与えます:)実際、これにより出力が少し読みやすくなります… - 13文字:
01r:nao$:@+$r
回答
六角形、 18 14 12
マーティンに6バイトありがとう!
1="/}.!+/M8;
拡張:
1 = " / } . ! + / M 8 ; . . . . . . .
古い、答えてください。画像と説明が新しいヘキサゴニーユーザーに役立つ可能性があるため、これは残されています。
!).={!/"*10;$.[+{]
拡張:
! ) . = { ! / " * 1 0 ; $ . [ + { ] .
これにより、改行で区切られたフィボナッチ数列が出力されます。
オンラインで試してください!ただし、オンラインでは注意してください。インタプリタは「無限の出力を本当に好きではありません。
説明
このプログラムには2つの「サブルーチン」があり、それぞれが2つの使用されるIPの1つによって実行されます。最初のルーチンは改行を出力します。 、2番目はフィボナッチ計算と出力を行います。
最初のサブルーチンは最初の行から始まり、常に左から右に移動します。最初にメモリポインタ(ゼロに初期化)で値を出力します。次に、メモリポインタの値を1
だけインクリメントします。no-opの後、IPは3行目にジャンプし、最初に別のメモリセルに切り替わり、次に改行を出力します。改行は正の値(その値は10)を持ち、th eコードは常に次の5行目にジャンプします。 5行目は、メモリポインタをフィボナッチ数に戻し、他のサブルーチンに切り替えます。このサブルーチンから戻ると、no-opを実行した後、IPは3行目に戻ります。
2番目のサブルーチンは右上隅から始まり、南東に移動し始めます。ノーオペレーションの後、私たちは2番目のラインに沿って西に移動するためにバウンスされます。この行は、メモリポインタを次の場所に移動する前に、現在のフィボナッチ数を出力します。次に、IPは4行目にジャンプし、前の2行を使用して次のフィボナッチ数を計算します。次に、最初のサブルーチンに制御を戻しますが、プログラムの制御を取り戻すと、ジャンプに遭遇するまで続行します。ジャンプが発生すると、元々西を指すために使用されていたミラー上で跳ね返り、2行目に戻ります。
予備のきれいな写真!
画像の左側はプログラムで、右側はメモリを表しています。青いボックスは最初のIPであり、両方のIPが次に実行される命令を指しています。
注:写真は画像編集プログラムのスキルが同様に限られている人にのみきれいに見えます:PIは、*
演算子の使用がより明確になるように、少なくとも2回の反復を追加します。
注2:このほとんどを書いた後、 alephalphaの答えを見ただけでしたが、分離されているため、それでも価値があると思いましたが、実際のフィボナッチ私たちのプログラムの一部は非常に似ています。さらに、これは私が複数のIPを使用しているのを見た中で最小のヘキサゴニープログラムなので、とにかく保持するのが良いかもしれないと思いました:P
コメント
- きれいな写真を作成するために使用したものにリンクしてから、そのリンクを esolangs.org/wiki/に配置する必要があります。六角形。
- @ mbomb007 gimpを使用して各フレームを手動で作成し、画像をいくつかのgiにアップロードしましたfウェブサイトを作る。しかし、このプロセス中に何度か、それがどれほど退屈であったかを考慮して、それを行うためのツールを作ることを検討しました。
- @FryAmTheEggman印象的です!それを挑戦してください。 '誰かが答えを投稿すると確信しています。 :D fish 'のオンライン通訳に似たウェブサイトを作成できればさらに良いでしょう。
- @ mbomb007このサイトでの挑戦には少し野心的かもしれません。言うまでもなく、それはおそらく本当に広いことから多くの苦しみを味わうでしょう。 '投稿するつもりはありませんが、良い表現方法があると思われる場合は、ご自身で投稿してください。また、Timwiは六角形のC#ideを作成したと思いますが、'モノに悩まされたことがないため、これを使用したことはありません。
- @ mbomb007 ideはここに住んでいますちなみに、前回リンクするのを忘れていました。
回答
COW 、108
MoO moO MoO mOo MOO OOM MMM moO moO MMM mOo mOo moO MMM mOo MMM moO moO MOO MOo mOo MoO moO moo mOo mOo moo
回答
Python 2、34バイト
Python、再帰を使用…ここStackOverflowが登場します!
def f(i,j):print i;f(j,i+j) f(1,1)
回答
ゼリー、3バイト
+¡1
仕組み
+¡1 Niladic link. No implicit input. Since the link doesn"t start with a nilad, the argument 0 is used. 1 Yield 1. + Add the left and right argument. ¡ For reasons‡, read a number n from STDIN. Repeatedly call the dyadic link +, updating the right argument with the value of the left one, and the left one with the return value.
‡ ¡
左側の2つのリンクをのぞきます。 1つしかないため、ループの本体である必要があります。したがって、数値は入力から読み取られます。コマンドライン引数がないため、その番号はSTDINから読み取られます。
回答
六角形、6バイト
言語が質問よりも新しいため、競合しません。
1.}=+!
Ungolfed:
1 . } = + ! .
区切り文字なしでフィボナッチ数列を出力します。
コメント
- これには、'数値の間に区切り文字が出力されないという小さな問題があります。ただし、これはチャレンジで完全に指定されているわけではありません'。 (そして、私は'誰かがヘキサゴニーを使用していることを本当に嬉しく思います。:))
回答
Golfscript-単一の数値-12/11/10
stdinから入力を取得するための12文字:
~0 1@{.@+}*;
すでにスタックにある入力用の11文字:
0 1@{.@+}*;
1を0番目のフィボナッチ数としてさらに定義するための10文字:
1.@{.@+}*;
コメント
- オプションは" nを指定すると、n番目のフィボナッチ数を計算します"。したがって、
~
を捨てると、スタックにn
を取り、F_n
スタック上。
回答
ルビー
29 27 25 24文字
p a=b=1;loop{b=a+a=p(b)}
編集:無限ループにしました。 ;)
コメント
-
b=a+a=b
が回文であることに気付いた人はいますか? 🙂 - はいst0leはしました:)
- 私は'パーティーに遅れていることを知っていますが、誰かが
b=a+a=b
の部分は機能しますか? '頭を包み込むことができないようです。 - @GigaWatt、このように考えてください。命令は左から右に実行されます…したがって、
newb=olda+(a=oldb)
-
loop
を使用すると2文字節約できます:p 1,a=b=1;loop{p b=a+a=b}
回答
DC(20バイト)
ボーナスとして、 「難読化されている;)
zzr[dsb+lbrplax]dsax
編集:フィボナッチ数列のすべての数値を 出力することを指摘するかもしれません。十分長く待ちます。
コメント
- 難読化されたとは言いません'難読化されたコード理解するのは難しいはずであり、dcに関する限り、ここでのコードは完全に単純です。
回答
Mathematica、9文字
Fibonacci
If組み込み関数は許可されていません。明示的な解決策は次のとおりです。
Mathematica、 33 32 31文字
#&@@Nest[{+##,#}&@@#&,{0,1},#]&
コメント
-
#&@@Nest[{#+#2,#}&@@#&,{0,1},#]&
32文字 - @chyanog 31:
#&@@Nest[{+##,#}&@@#&,{0,1},#]&
- @ Mr.Wizard 24文字(26バイト):
Round[GoldenRatio^#/√5]&
- または23文字(27バイト):
Round[((1+√5)/2)^#/√5]&
回答
プレリュード、12バイト
プレリュードが実際にかなり競争力のある数少ない課題の1つ:
1(v!v) ^+^
これには、値を文字ではなく10進数として出力する Pythonインタープリターが必要です。
説明
プレリュードでは、すべての行は並列に実行され、命令ポインタはプログラムの列をトラバースします。各行には、ゼロに初期化される独自のスタックがあります。
1(v!v) ^+^ | Push a 1 onto the first stack. | Start a loop from here to the closing ). | Copy the top value from the first stack to the second and vice-versa. | Print the value on the first stack, add the top two numbers on the second stack. | Copy the top value from the first stack to the second and vice-versa.
最初のスタックの上部に0
が表示されることはないため、ループは永久に繰り返されます。
これにより、フィボナッチ数列が0
から開始されることに注意してください。
回答
TI-BASIC、11
伝説的なTI-BASICゴルファーのケネスハモンド(「Weregoose」)による、このサイトから。 O(1)時間で実行され、0をフィボナッチ数列の0番目の項と見なします。
int(round(√(.8)cosh(Anssinh‾¹(.5
使用方法:
2:int(round(√(.8)cosh(Anssinh‾¹(.5 1 12:int(round(√(.8)cosh(Anssinh‾¹(.5 144
これはどのように機能しますか?計算すると、sinh‾¹(.5)
はln φ
と等しいことがわかります。したがって、「Binetの修正版」の式は次のようになります。 (1/φ)^n
補正項を使用する代わりに切り捨てます。丸め誤差を防ぐには、round(
(小数点以下第9位に四捨五入)が必要です。
回答
K-12
n
とn-1
フィボナッチ数を計算します。
{x(|+\)/0 1}
nth
フィボナッチ数だけ。
{*x(|+\)/0 1}
コメント
- +1悪くない! 1文字だけ縮小できる(そしてテストする方法を提供してくれる)場合は、'回答を受け付けます。 🙂
- 縮小する唯一の方法は、関数を既知の番号への呼び出しに置き換えることです:n(| + \ ) / 0 1 このインタプリタを使用してテストします。
回答
Java、55
ここではほとんどの言語の簡潔さに匹敵することはできませんが、n番目の数値を計算するための大幅に異なる、おそらくはるかに高速な(一定の時間)方法を提供できます。
Math.floor(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))
n
は、n = 1から始まる入力(intまたはlong)です。
ビネットの式と減算の代わりに丸めます。
コメント
- 大好きですこの解決策
- これは'うまくいかないようですが、'早いので、何かが足りません!
0
がシーケンスの最初の番号であるとすると、これにより、最初の番号に0, 0, 1, 1, 3, 4, 8, 12, 21, 33
が与えられます。 t10個の数字 - @Shaggy Oops!申し訳ありませんが、バグを導入しました。現在修正されています。
回答
ジュリア、18バイト
n->([1 1;1 0]^n)[]
回答
ドドス、26バイト
dot F F F dip F dip dip
仕組み
関数 F はすべての面倒な作業を行います。これは、次のように再帰的に定義されます。
F(n) = ( F(|n - 1|), F(||n - 1| - 1|) )
n> 1 の場合は常に、 | n-1 | = n-1 < n および || n-1 | -1 | = | n-1 –1 | = n-2 < n なので、関数は(F(n -1)、F(n-2))。
n = 0
、次に | n-1 | = 1> 0 ; n = 1 の場合、 || n-1 | -1 | = | 0-1 | = 1 = 1 。どちらの場合も、試行された再帰呼び出し F(1)は降伏例外を発生させるため、 F(0)は 0 および F(1)は 1 。
たとえば、 F(3)=(F(1)、F(2))=(1 、F(0)、F(1))=(1、0、1)。
最後に、 main 関数は次のように定義されます
main(n) = sum(F(n))
したがって、返されるベクトルのすべての座標を合計します作成者 F 。
たとえば、 main (3)= sum(F(3))= sum(1、0、1)= 2 。
コメント
- 私はあなたのREADME(DODOS)を読み、非常に興味をそそられました。それは本当に素晴らしいコンセプトです!しかし、私はそれをEsolangsや他のどこにも見つけることができません。思いついたのですか?
回答
ルビー、25文字
st0le 「回答が短縮されました。
p 1,a=b=1;loop{p b=a+a=b}
コメント
- 実際には、
- それであなたは彼の答えを止めますか?:P
答え
FAC:機能的なAPL、4文字(!!)
私のものではないため、コミュニティwikiとして投稿されています。FACはAPLの方言であり、Hai-ChenTuが博士論文として提案したようです。 1985年に彼は後にAlanJ.Perlisと一緒に「 FAC:機能的なAPL言語」という記事を書きました。このAPLの方言は、「レイジーアレイ」と無限の長さの配列を許可します。これは、演算子 “iter”(⌼
)を定義して、いくつかの再帰シーケンスのコンパクトな定義を可能にします。
モナディック( “unary “)⌼
の場合は、基本的にHaskellのであり、(F⌼) A ≡ A, (F A), (F (F A)), …
として定義されています。二項(「バイナリ」)の場合は、A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …
という2つの変数に対していくぶん類似して定義されます。なぜこれが便利なのですか?実は、これはまさにフィボナッチ数列の再発のようなものです。実際、その例の1つは、
1+⌼1
おなじみのシーケンス1 1 2 3 5 8 …
を生成することです。
さて、これで、おそらく、斬新でないプログラミング言語での可能な限り最短のフィボナッチ実装になります。 :D
コメント
- ああ、私は誤ってあなたの投稿を(手動の)一括非ウィキの一部として非コミュニティウィキしました。しかたがない。 😉
回答
回答
回答
GolfScript、13文字
2,~{..p@+.}do
(
前のスタックオーバーフローの質問。)