Practice_GCD_B2App.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 輾轉相除法（高中數學第二冊附錄）\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理：設 $a$ 和 $b$ 都是正整數，我們將 $a$ 除以 $b$，得到商數 $q$ 和餘數 $r$，即 $a＝bq＋r\\ (0\\le r<b)$，那麼 $a$ 與 $b$ 的最大公因數（Greatest Common Divisor, GCD）等於 $r$ 與 $b$ 的最大公因數，即被除數與除數的最大公因數等於除數與餘數的最大公因數。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "輾轉相除演算法流程：\n",
    "1. 給定兩個正整數 a,b\n",
    "2. 計算 a 除以 b 的餘數 r (利用 r=a(mod b) )\n",
    "3. 檢查 r 有沒有等於 0 ，如果有就輸出 b；如果沒有，將 b 指定為 a ，將 r 指定為 b，重複以上流程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按編：\n",
    "$r\\equiv a\\pmod{b}$ 為 $a$ 除以 $b$ 的餘數\n",
    "\n",
    "例：\n",
    "1. $10\\equiv50\\pmod{20}\\Rightarrow 50\\div20=\\cdots 10$\n",
    "2. $0\\equiv8\\pmod{4}\\Rightarrow 8\\div4=\\cdots 0$\n",
    "\n",
    "而在多數程式語言中，mod是基本的運算子。例如在 Python 中就用 a%b 來處理 $a\\pmod{b}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 將以上流程，利用遞迴方法寫成 Python function <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mygcd(a,b):\n",
    "    r=a%b\n",
    "    if r==0:\n",
    "        return b\n",
    "    else:\n",
    "        return mygcd(b,r)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mygcd(54,24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 以下為直算法的虛擬碼，請試著將其翻譯為 Python Code <br>\n",
    "``\n",
    "function mygcd1(a,b)\n",
    "    while a≠b\n",
    "        if a > b\n",
    "            a <= a-b\n",
    "        else\n",
    "            b <= b-a    \n",
    "    return a\n",
    "``\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mygcd1(a,b):\n",
    "    while a!=b:\n",
    "        if a > b:\n",
    "            a = a-b\n",
    "        else:\n",
    "            b = b-a    \n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mygcd1(54,24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}