description.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最大値，最大公約数，平方根のアルゴリズム"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python（バージョン3）で，最大値を見つけるアルゴリズム，ユークリッドの互除法，2分探索による平方根の見積もりを実装してみる．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大値を見つけるアルゴリズム"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "まず，最大値を見つけるアルゴリズムを関数maximumとして以下に定義する．\n",
    "なお，Pythonには最大値を返す組込み関数maxがある．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum(x):\n",
    "    y = x[0]\n",
    "    for i in range(1, len(x)):\n",
    "        if x[i] > y:\n",
    "            y = x[i]\n",
    "    return y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "試しに，てきと〜に作った数値のリストを引数として関数maximumをよびだしてみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [3, 1, 4, 1, 5, 9, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximum(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "確かに最大値を返してくれることを確認した．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大公約数（ユークリッドの互除法）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ユークリッドの互除法を関数euclidとして以下に定義する．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclid(x, y):\n",
    "    x, y = maximum([x, y]), min(x, y)\n",
    "    while y > 0:\n",
    "        x, y = y, x % y\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この関数定義では，同時に複数の代入をする命令を2回使っている．\n",
    "同時に複数の代入をできると入れ替え（スワップ）の際には便利である．\n",
    "また，せっかくなので上で定義した関数maximumを使った．\n",
    "\n",
    "試しに，10807と10403の最大公約数を求めてみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euclid(10807, 10403)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "確かに最大公約数を返してくれることを確認した．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2分探索による平方根の見積もり"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2分探索による平方根の見積もりを関数square_root_binary_searchとして以下に定義する．\n",
    "なお，アルゴリズムの途中経過を観察するための表示命令も加える．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def square_root_binary_search(x, p):\n",
    "    a, b = 0, x\n",
    "    while b - a > p:\n",
    "        print('[a, b] = [{0:4.3f}, {1:4.3f}]'.format(a, b)) # アルゴリズムの途中経過を観察する．\n",
    "        m = (a + b) / 2 # このコードはPython3用なので，この商は小数部分切り捨てではない．\n",
    "        if m ** 2 > x:\n",
    "            b = m\n",
    "        else:\n",
    "            a = m\n",
    "    return a, b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "試しに，$\\sqrt{2}$を精度0.1で見積もってみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[a, b] = [0.000, 2.000]\n",
      "[a, b] = [1.000, 2.000]\n",
      "[a, b] = [1.000, 1.500]\n",
      "[a, b] = [1.250, 1.500]\n",
      "[a, b] = [1.375, 1.500]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1.375, 1.4375)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square_root_binary_search(2, 0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "見積もりとしては甘く感じるが，$\\sqrt{2}$は1.375と1.4375の間にあるとわかる．\n",
    "\n",
    "もう少し精度を上げて，$\\sqrt{2}$を精度0.0001で見積もってみる．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[a, b] = [0.000, 2.000]\n",
      "[a, b] = [1.000, 2.000]\n",
      "[a, b] = [1.000, 1.500]\n",
      "[a, b] = [1.250, 1.500]\n",
      "[a, b] = [1.375, 1.500]\n",
      "[a, b] = [1.375, 1.438]\n",
      "[a, b] = [1.406, 1.438]\n",
      "[a, b] = [1.406, 1.422]\n",
      "[a, b] = [1.414, 1.422]\n",
      "[a, b] = [1.414, 1.418]\n",
      "[a, b] = [1.414, 1.416]\n",
      "[a, b] = [1.414, 1.415]\n",
      "[a, b] = [1.414, 1.415]\n",
      "[a, b] = [1.414, 1.414]\n",
      "[a, b] = [1.414, 1.414]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1.4141845703125, 1.41424560546875)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square_root_binary_search(2, 0.0001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2分探索を用いると，目標を含む区間が毎回半分になる．\n",
    "よって探索範囲が狭まるのは意外と早い．"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}