基本問題(3)

[ edit ]

*


概要

[ 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 ]

  • 実行例(1) ... クリックすると拡大します

fig-01

*


プログラム例: 本質的な部分 (授業中に順次公開します)

[ 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=""  )
# ==============================================================================
*
*

SoftEng: Python/Prog/Practice/Basic/03/BP_003a (last edited 2018-10-21 12:42:24 by TadashiIijima)