基本問題(3)
[ edit ]
Contents
概要
[ edit ]
フィボナッチ数列 (長さを指定する)
$$ フィボナッチ数列: f_0=0,\ f_1=1,\ f_{n+2}=f_{n+1}+f_{n} $$
$$ フィボナッチ数列: \left\{ \begin{array}{ll} f_0 =0 & \\ f_1 =1 & \\ f_{n+2} = f_{n} + f_{n+1} & (n >= 0) \end{array} \right. $$
ヒント
この課題で使うPythonの機能 (学習のヒント)
[ edit ]
この課題の解き方 (問題解決のヒント)
[ edit ]
- この課題の解き方 (問題解決のヒント) ....
- フィボナッチ数の数列を求めるとき
- 単独でフィボナッチ数を求める関数を，何度も呼び出すのは，計算時間の無駄となる
- 数列で，先に計算した値から，次のフィボナッチ数を計算できるので，それを使えばよい．
- フィボナッチ数の数列を求めるとき
おまけ
[ edit ]
- おまけ ....
- 自然界でしばしば見かけられる
Wikipedia(フィボナッチ数)を参照してください
- 元々，フィボナッチは，1つがい（オス/メス一羽ずつ）のウサギが1年後にどれくらい増えるかという「兎の問題」として提示したらしい
(私は確認していませんが...)1202年にイタリアのレオナルド・フィボナッチが書いた「算盤の書」に記載があるとのこと．同書は，アラビア数学を紹介したもの．
- ちなみに，1年後の「兎の『つがい』の数」は，12番目のフィボナッチ数である233対となるとされている
- 問題設定は，
- (1) 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む，
- (2)兎が死ぬことはない。
- 問題設定は，
- 花びらの数や，ヒマワリ(向日葵)のらせん(螺旋)状に並ぶ種の数などに，フィボナッチ数が現れることが多いらしい
- 自然界でしばしば見かけられる
隣り合ったフィボナッチ数の比は，黄金比に収束することが知られています．
- 後日，グラフ(折れ線グラフ)の描き方を授業で取り上げたら，収束の様子を眺めてみましょう
$$ 黄金比: \frac{1+\sqrt{5}}{2} $$
- フィボナッチ数の一般項
$$ フィボナッチ数列の一般項: a_n=\dfrac{1}{\sqrt{5}} \left\{ \left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n \right\} $$
実行例
*
プログラム例: 本質的な部分 (授業中に順次公開します)
[ edit ]
- 解答例の核心部分，下記 10 行の関数です．
- 先に計算したフィボナッチ数をリストに保管していますので，再計算せずにそれを利用しています．
# ===== 【関数定義】 0～nまで(nを含む)のフィボナッチ数列を求める
def fibonacci_sequence( n ):
if n == 0:
return( [0] )
elif n == 1:
return( [0,1] )
else:
sequence = [0,1]
for i in range( 2, n + 1 ):
sequence.append( sequence[i-2] + sequence[i-1] )
return( sequence )
プログラム例: 配布コード (授業中に順次公開します)
[ edit ]
- 以下の解答例を配布します．
- 本質部分は替えませんが，コメントや，メインプログラム部分の実行例を，後々，分かり易く書き換える可能性はあります．
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# * (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[03] 基本課題[03]-(003a) BP_03_003a_fibonacci_sequence.py
# BP(Basic Problem) 03-003a: フィボナッチ数列 (長さを指定する)
# 2018-10-17 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# ===== 【関数定義】 0～nまで(nを含む)のフィボナッチ数列を求める
def fibonacci_sequence( n ):
if n == 0:
return( [0] )
elif n == 1:
return( [0,1] )
else:
sequence = [0,1]
for i in range( 2, n + 1 ):
sequence.append( sequence[i-2] + sequence[i-1] )
return( sequence )
# ==============================================================================
# ===== 【メイン・プログラム】 =====
# ----- オープニングメッセージ -----
print( "フィボナッチ数列(: " )
print( " ※0～指定した整数nまでのフィボナッチ数の長さn+1のリスト" )
print()
# ----- パラメータの入力 -----
length = int( input( " 系列の長さを入力して下さい(与えられたnに対しn+1個生成します)>>> " ) )
print()
# ----- 結果の表示 ----
print( "長さ", length, "のフィボナッチ数列: ", fibonacci_sequence(length), sep="" )
# ==============================================================================