{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2023年度計算機演習A・B\n",
    "\n",
    "# 第5回：フィボナッチ数列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. フィボナッチ数列とは\n",
    "\n",
    "**フィボナッチ数列（Fibonacci sequence）**は、イタリアの数学者レオナルド・フィボナッチの名前に因んだ有名な数列であり、次の漸化式で定義されます。\n",
    "\n",
    "$$\n",
    "\\begin{gathered}\n",
    "F_1=1,\\\\\n",
    "F_2=1,\\\\\n",
    "F_n=F_{n-2}+F_{n-1}\\quad (n\\geq 3)\n",
    "\\end{gathered}\n",
    "$$\n",
    "\n",
    "（※初項を $0$ にする場合もあります。）\n",
    "\n",
    "フィボナッチ数列を実際に書き下すと、次の通りです。\n",
    "\n",
    "$$\n",
    "1,1,2,3,5,8,13,21,34,55,\\ldots\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習1\n",
    "\n",
    "フィボナッチ数列の第1項から第20項までを要素に持つリストを作成し、そのグラフを描画してください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習1のコード\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "N = 20  #最後の項の番号\n",
    "F_list = [1,1]  #フィボナッチ数列のリスト\n",
    "\n",
    "#ここで、for文を使ってF_listに要素を追加する\n",
    "#Pythonでリストの要素の番号は0から始まることに注意（現状ではF_list[0]とF_list[1]を作成済み）\n",
    "\n",
    "n_list = range(1,N+1)\n",
    "\n",
    "#ここで、n_listとF_listを使ってグラフを描画する"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 関数の再帰的定義\n",
    "\n",
    "第3回の授業では、Pythonにおける関数定義の方法について説明しました。\n",
    "\n",
    "次のコードに示すように、関数定義の中では別の関数を呼び出して利用することができます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_sum(num_list):  #リストの要素の和を計算する関数\n",
    "    result = 0\n",
    "    for n in num_list:\n",
    "        result = result+n\n",
    "    return result\n",
    "\n",
    "def my_average(num_list):  #リストの要素の平均を計算する関数\n",
    "    result = my_sum(num_list)/len(num_list)  #上で定義した関数my_sumを呼び出す\n",
    "    return result\n",
    "\n",
    "print(my_average([1,2,3,4,5,6]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "関数定義の中では、自分自身を呼び出して利用することもできます。これを**関数の再帰的定義（recursive definition）**と呼びます。\n",
    "\n",
    "例えば、\n",
    "\n",
    "$$\n",
    "\\begin{gathered}\n",
    "1!=1,\\\\\n",
    "n!=n\\times(n-1)!\\quad (n\\geq 2)\n",
    "\\end{gathered}\n",
    "$$\n",
    "\n",
    "を用いることで、自然数 $n$ に対して階乗 $n!$ を返す関数`factorial`を次のように定義することができます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n == 1:  #関数をwell-definedにするために重要な意味を持つ\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorial(n-1)  #n-1に対して自分自身を呼び出す\n",
    "\n",
    "print(factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習2\n",
    "\n",
    "関数の再帰的定義によって、自然数 $n$ に対してフィボナッチ数列の第 $n$ 項を返す関数`fibonacci`を定義してください。定義した関数を呼び出す例も付けてください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習2のコード\n",
    "def fibonacci(n):\n",
    "    #ここに、関数の処理を書く\n",
    "    pass  #passはエラーを防ぐための「何もしない文」なので、消す\n",
    "\n",
    "#関数を呼び出す例を付ける"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. フィボナッチ数列と黄金比の関係\n",
    "\n",
    "**黄金比（golden ratio）**は、「人間が最も美しく感じる」と考えられている比率であり、\n",
    "\n",
    "$$\n",
    "1:\\frac{1+\\sqrt{5}}{2}\n",
    "$$\n",
    "\n",
    "あるいは、ここに現れる数\n",
    "\n",
    "$$\n",
    "\\varphi=\\frac{1+\\sqrt{5}}{2}=1.618\\cdots\n",
    "$$\n",
    "\n",
    "のことです（$\\varphi$ を黄金数と呼ぶ場合もあります）。\n",
    "\n",
    "フィボナッチ数列と黄金比の間には、深い関係があります。\n",
    "\n",
    "その関係を示す一つの性質として、次の式が成り立つことが知られています。\n",
    "\n",
    "$$\n",
    "\\lim_{n\\to\\infty}\\frac{F_{n+1}}{F_n}=\\varphi\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習3\n",
    "\n",
    "次の式で定まる数列 $\\{Q_n\\}$ に対して第1項から第19項までを用いてグラフを描画することによって、上記の性質を確認してください。\n",
    "\n",
    "$$\n",
    "Q_n=\\frac{F_{n+1}}{F_n}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習3のコード\n",
    "\n",
    "#演習1で作成したF_listを利用するとよい"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習4（オプション）\n",
    "\n",
    "フィボナッチ数列に関する上記以外の性質をインターネット等で一つ調べ、プログラミングによってその性質を確認してください。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（調べた性質の内容をMarkdownとして書く）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習4のコード"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第5回レポート課題\n",
    "\n",
    "演習1～演習4に取り組んでください。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}