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

【本章摘要】

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

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

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

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

表6-1　歐幾里得游戲過(guò)程

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

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