エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
【競プロ】フィボナッチ数列と再帰関数(メモ化再帰) | なかけんの数学ノート
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
【競プロ】フィボナッチ数列と再帰関数(メモ化再帰) | なかけんの数学ノート
フィボナッチ数列 次のように数が並んでいるとします。\[ 0,1,1,2,3,5,8,13,21,\cdots \]1つ前と2つ前の... フィボナッチ数列 次のように数が並んでいるとします。\[ 0,1,1,2,3,5,8,13,21,\cdots \]1つ前と2つ前の数を足して新しい数を計算する、というルールです。例えば、 $21$ の次は、 $13+21=34$ になる、ということです。 初めの2つの数 $0,1$ を決めれば、その後の数は、次々と確定していきます。このようにして決まる数の列を、フィボナッチ数列(Fibonacci sequence) といいます。フィボナッチ数列は、競プロをはじめ、様々な分野で出てきます。 ここでは、フィボナッチ数列の $n$ 番目の数を求める fibonacci(n) という関数を、再帰関数で書くことを考えましょう。なお、先頭の $0$ を $0$ 番目とします。つまり、fibonacci(0) = 0, fibonacci(1) = 1 ということです。 1つ前の数と2つ前の数を足せ