2022年度計算機演習A・B

第5回レポート課題の解説

演習1

フィボナッチ数列の第1項から第20項までを要素に持つリストを作成し、そのグラフを描画してください。

演習2

関数の再帰的定義によって、自然数 $n$ に対してフィボナッチ数列の第 $n$ 項を返す関数fibonacciを定義してください。定義した関数を呼び出す例も付けてください。

(注意)

関数の再帰的定義を利用するとコードを簡潔に書くことができる反面、上のfibonacciのように関数の一回の処理の中で自身を二回以上呼び出す場合には、引数が大きくなるほどに計算効率が悪くなります。これは、同じ引数に対する計算を何度も行うことで無駄が生じるからです。

演習3

フィボナッチ数列 $\{F_n\}$ と黄金比 $\varphi$ の関係を示す一つの性質として、次の式が成り立つことが知られています。

$$ \lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi $$

次の式で定まる数列 $\{Q_n\}$ に対して第1項から第19項までを用いてグラフを描画することによって、上記の性質を確認してください。

$$ Q_n=\frac{F_{n+1}}{F_n} $$

演習4(オプション)

フィボナッチ数列に関する上記以外の性質をインターネット等で一つ調べ、プログラミングによってその性質を確認してください。

ゼッケンドルフの定理(Zeckendorf's theorem)

任意の自然数は、一つ以上の連続しない相異なるフィボナッチ数列の項の和として一意に表現できる。

ここでは、この定理における「表現の一意性」以外の主張についてプログラミングで確認してみる。

フィボナッチ数列を $\{F_n\}$、任意の $m\in\mathbb{N}$ に対して $m$ 以下の最大のフィボナッチ数列の項の番号を $n_m$ とするとき、

$$ \begin{gathered} \mathrm{Zeckendorf}(m)=F_{n_m}+\mathrm{Zeckendorf}\left(m-F_{n_m}\right)\quad (m\in\mathbb{N})\\ \mathrm{Zeckendorf}(0)=0 \end{gathered} $$

により定まる $\mathrm{Zeckendorf}(m)$ が $m\in\mathbb{N}$ に対する上記の表現(ゼッケンドルフ表現)を与えることを利用する。

(※以下のコードはかなり難しいため、無理に理解しなくて大丈夫です。)