問題
問題文中の(1)、(2)に当てはまるものとして、適切なものはどれか。
フィボナッチ数列とは初項と第2項を1とし、それ以降の項については、前の2つ項の和とったものとして得られる数列である。数式として表現すると次のようになる。
$$ a_1=1, a_2=1, a_{n+2}=a_{n+1}+a_{n} (n=1,2,3,...) $$
このフィボナッチ数列の第n項の値を求めるプログラムをPythonで実装したものが、以下である。
def fibonacci(n): #フィボナッチ数列を計算する再帰関数 if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(300))
これを実行した例は次のようになり、フィボナッチ数列を正しく実装できていることがわかる。
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
しかしながらこのプログラムには、引数として与えるnの値が大きくなっていくにつれて、ある重大な問題が起こる可能性がある。その問題とは「(1)」ということであり、これを解決するために「(2)」という手法が用いられる。
空欄(1) | 空欄(2) | |
ア | スタックオーバーフローを引き起こす可能性がある | メモ化再帰 |
イ | スタックオーバーフローを引き起こす可能性がある | 統治分割法 |
ウ | 並列実行数が急増するため、スレッド数の限界値を超えてしまう可能性がある。 | メモ化再帰 |
エ | 並列実行数が急増するため、スレッド数の限界値を超えてしまう可能性がある。 | 統治分割法 |
選択肢
(a) ア
(b) イ
(c) ウ
(d) エ
- a
- b
- c
- d
Python フィボナッチ数列
答え
(a)
解説
フィボナッチ数列のプログラムに与えるnの大きさを徐々に大きくしていって、処理がどうなるのかをみていきましょう。
call_count = 0 def fibonacci(n): #フィボナッチ数列を計算する再帰関数 global call_count call_count += 1 if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) a = fibonacci(10) print(a, call_count)
このプログラムは、問題文中のフィボナッチ数列を求めるプログラムを改変したもので、第n項の値と、それと同時に関数が実行された回数をカウントして出力します。
fibonacci(10)の場合 値:55 実行回数:177
fibonacci(20)の場合 値:6765 実行回数:21891
fibonacci(30)の場合 値:832040 実行回数:2692537
fibonacci(100)の場合 → タイムアウトが発生
fibonacci(1000)の場合 → RecursionErrorが発生
このようにnの値を増やしていくと、関数の実行回数が急速に増えていき、PCの性能や設定にもよりますが、n=100くらいになるとほとんどの場合でタイムアウトやRecursionErrorが発生してしまいます。RecursionErrorとは、以下のようなものです。
Traceback (most recent call last): File "Main.py", line 20, in <module> a = fibonacci(1000) File "Main.py", line 17, in fibonacci return fibonacci(n-1) + fibonacci(n-2) File "Main.py", line 17, in fibonacci return fibonacci(n-1) + fibonacci(n-2) File "Main.py", line 17, in fibonacci return fibonacci(n-1) + fibonacci(n-2) [Previous line repeated 995 more times] File "Main.py", line 14, in fibonacci if n <= 1: RecursionError: maximum recursion depth exceeded in comparison
なぜこのようなことが起こるかというと、このまま大量に関数を実行し続けると、コンピュータのコールスタック領域の限界を超えてしまい、スタックオーバーフローとなってしまう可能性が高いからです。これを未然に防ぐために、コンピュータやPythonの設定には最大再帰深度(再帰の最大値)が設定されており、この値を超えるとRecursionErrorなどが発生するわけです。したがって、空欄(1)については「スタックオーバーフローを引き起こす可能性がある」が正解です。
この問題を解決するための手段として「nの値と、それに対応する結果を記録しておいて、過去にnが同じ値で関数が実行されていた場合には、記録からその値を取得する」というものがあります。
例えば、fibonacci(6)を実行する場合を見てみましょう。(簡単のため、fibonacciをfiと表記しています。)
fi(6)
→ fi(5) + fi(4)
→ fi(4) + fi(3) + fi(3) + fi(2)
→ fi(3) + fi(2) + fi(2) + fi(1) + fi(2) + fi(1) + fi(2)
→ fi(2) + fi(1) + fi(2) + fi(2) + fi(1) + fi(2) + fi(1) + fi(2)
→ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8
となります。ここで気づいた方もいるかもしれませんが、第6項を計算するために、第3項を3回も求めてしまっています。例えば第100項を計算しようとすると、計算量が膨大な第90, 80, 70項などを、何度も実行する必要があるのです。
これが、スタックオーバーフローを引き起こす原因となっています。この問題を解決する方法は非常に簡単で、一度計算したものは記録やメモ(つまりリストなどの変数)に保存しておくことです。第3項の実行結果をメモしておけば、fibonacci(6)を求める際には、fibonacci(3)を一回実行するだけで済みます。この手法を「メモ化再帰」と言います。したがって、空欄(2)は「メモ化再帰」が正解です。
メモ化再帰を適応したプログラム:
memo = {} def fibonacci(n): #メモ化を適用したフィボナッチ数列を計算する関数 if n in memo: return memo[n] if n <= 1: memo[n] = n return n else: result = fibonacci(n-1) + fibonacci(n-2) memo[n] = result return result
このプログラムならば、nが大きくなっても値を求めることができます。
fibonacci(100):
354224848179261915075
fibonacci(200):
280571172992510140037611932413038677189525
fibonacci(300):
222232244629420445529739893461909967206666939096499764990979600
テスト一覧
スキルテストが提供しているテストの一覧です。ぜひ学習や実力チェックに役立ててください。
- Pythonテスト
- ビジネス基礎力診断テスト
- 英語会計 理解度テスト(USCPA FAR対応)
- 世界の国旗当てクイズ
- アメリカ合衆国の州旗当てクイズ
- 金融リテラシーテスト
- Pythonテスト【初級者向け】
- 論理力レベルチェック
- HTMLタグ理解度チェック
- 天文宇宙テスト
- Linux理解度チェック
- 関西弁テスト
- 魚の漢字クイズ検定
- 元素記号テスト・検定
- 四字熟語テスト
- 日本歴史テスト
- 山手線検定
- 北海道弁テスト
- 博多弁テスト
- 京都弁テスト
- 神奈川の方言テスト
- 長野県方言・信州弁テスト
- 沖縄弁(うちなーぐち) テスト
- 広島弁テスト
- 青森の方言(津軽弁)テスト
- Pythonテスト【本番モード】
- 猫種検定
- 日本の方言テスト
- 犬種検定
- 仮想通貨スキル診断
- 寺院・神社当て検定
- うさぎ当て検定
- 寺院・神社当て検定 <関東版>
- Pythonスキルチェック<組み込み関数編>
- Python3×データサイエンス試験
- 化学物質検定
- 花クイズ
- ディズニーテスト
- 現代建築物検定
- ドメインテスト
- 日本の偉人クイズ
- 素数テスト
- Japanese Famous Kanji Exam
- Japanese Animal Kanji Exam
- 富山弁テスト
- 八丈方言クイズ
- 讃岐弁クイズ(香川県)
- 英語クイズ 国名
- 国コードテスト (2文字版)
- 国コードテスト (3文字版)
- 魚の英語クイズ
- 英語(花)クイズ
- 英語(植物)クイズ
- 英語(宇宙)クイズ
- 地名読み方クイズ(市区町村)
- 英語(料理名)クイズ
- 英語(元素名)クイズ
- 鹿児島方言テスト
- 英文読解問題 中学生レベル
- 英語クイズ 感染症
- 英語クイズ 不動産
- 日本の方言 大分弁クイズ