6　欧几里得游戏和最大公约数的求法

【本章摘要】

数学内容：求最大公约数的两个算法（辗转相减法和辗转相除法），博弈论简单启蒙。

编程内容：函数，if/else，条件判断，递归函数。

科尔（Cole）和戴维（Davie）是好朋友，两人都喜欢同班的一个女同学，为了不影响两人的友谊，他们决定玩一个称为欧几里得的游戏，谁输谁退出。玩法是这样的：游戏开始时，有两堆棋子，分别有a和b颗棋子（假定a>b），两人轮流从较多一堆棋子中按规定取子，规定每次取子数目必须是较少的一堆棋子数量的正整数倍，取走的棋子数不限，只要数量够就可以取。这样轮流取子以后，率先将任何一堆棋子取光的人获胜。于是他们两人各抓了一把棋子，一堆33个，一堆7个，他们又通过抛硬币的方式决定科尔首先取子。表6-1记录了这次游戏过程。

科尔痛不欲生，但愿赌服输，他回家以后好好研究了一下这个数学游戏，发现了诀窍，信心满满地知道自己下次不会再输了。我们等会儿再揭秘一下他的发现，现在我们先来学习一下这个游戏中的数学知识，为解密做准备。

表6-1　欧几里得游戏过程

最大公约数也称最大公因数，指两个或多个整数共有约数中最大的一个，比如35和21的最大公约数是7。a，b的最大公约数记为（a，b），a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

求最大公约数有多种方法，常见的有质因数分解法、辗转相除法、辗转相减法（也叫更相减损法，后面这个名字出自《九章算术》，约成书于公元1世纪，作者不详，西汉时期张苍、耿寿昌对这本书曾经做过增补和整理，是中国最早的一部数学专著）。这里主要介绍用计算机程序求两个数的最大公约数（Greatest Common Divisor）的方法。