6　歐幾里得游戲和最大公約數(shù)的求法

【本章摘要】

數(shù)學內(nèi)容：求最大公約數(shù)的兩個算法（輾轉(zhuǎn)相減法和輾轉(zhuǎn)相除法），博弈論簡單啟蒙。

編程內(nèi)容：函數(shù)，if/else，條件判斷，遞歸函數(shù)。

科爾（Cole）和戴維（Davie）是好朋友，兩人都喜歡同班的一個女同學，為了不影響兩人的友誼，他們決定玩一個稱為歐幾里得的游戲，誰輸誰退出。玩法是這樣的：游戲開始時，有兩堆棋子，分別有a和b顆棋子（假定a>b），兩人輪流從較多一堆棋子中按規(guī)定取子，規(guī)定每次取子數(shù)目必須是較少的一堆棋子數(shù)量的正整數(shù)倍，取走的棋子數(shù)不限，只要數(shù)量夠就可以取。這樣輪流取子以后，率先將任何一堆棋子取光的人獲勝。于是他們兩人各抓了一把棋子，一堆33個，一堆7個，他們又通過拋硬幣的方式?jīng)Q定科爾首先取子。表6-1記錄了這次游戲過程。

科爾痛不欲生，但愿賭服輸，他回家以后好好研究了一下這個數(shù)學游戲，發(fā)現(xiàn)了訣竅，信心滿滿地知道自己下次不會再輸了。我們等會兒再揭秘一下他的發(fā)現(xiàn)，現(xiàn)在我們先來學習一下這個游戲中的數(shù)學知識，為解密做準備。

表6-1　歐幾里得游戲過程

最大公約數(shù)也稱最大公因數(shù)，指兩個或多個整數(shù)共有約數(shù)中最大的一個，比如35和21的最大公約數(shù)是7。a，b的最大公約數(shù)記為（a，b），a，b，c的最大公約數(shù)記為（a，b，c），多個整數(shù)的最大公約數(shù)也有同樣的記號。

求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、輾轉(zhuǎn)相除法、輾轉(zhuǎn)相減法（也叫更相減損法，后面這個名字出自《九章算術(shù)》，約成書于公元1世紀，作者不詳，西漢時期張蒼、耿壽昌對這本書曾經(jīng)做過增補和整理，是中國最早的一部數(shù)學專著）。這里主要介紹用計算機程序求兩個數(shù)的最大公約數(shù)（Greatest Common Divisor）的方法。