6.2　辗转相除法

辗转相除法也叫欧几里得算法，是一种非常古老的求解两个数的最大公约数的算法。其基本的原理：两个正整数a和b（设a>b），它们的最大公约数（英文简写为gcd）等于a除以b的余数r和b之间的最大公约数。我们举个具体的例子来看一下。

例子：求（319，377），注意下面算式中的“÷”号为整除的意思。

因为319÷377=0（余319）

所以（319，377）=（377，319）；

因为377÷319=1（余58）

所以（377，319）=（319，58）；

因为319÷58=5（余29）

所以（319，58）=（58，29）；

因为58÷29=2（余0）

所以（58，29）=29；

所以（319，377）=29。

根据上面的原理，辗转相除法的算法流程可以如下：

步骤1：计算a与b的余数r。

步骤2：如果r为0，则返回gcd（a，b）=b，否则，转到步骤3。

步骤3：使用b的值更新a的值，使用余数r更新b的值，转到步骤1。

代码如下：

等等，程序中为什么不对a和b的大小进行判断呢？上面的算法原理中不是要求a大于b吗？如果调用时a值大于b值，比如a为51，b为21，那么情况跟上述算法原理是相符的。如果调用时a值小于b值，比如a为21，b为51，那么，21除以51的余数r为21，不为0，于是接着调用gcd（51，21），发现了吗？这就和a>b的情况一样了。也就是说我们根本无须判断a和b的大小，当a值小于b值时，算法的下一次调用就能够将a和b的值交换过来。

“a%b”是什么运算？a%b就是a整除b以后的余数，比如5%3为2，3%5为3，8%4为0，4%8为4。

以上两种算法都可以计算任意两个数的最大公约数。在什么条件下，哪一种算法的速度更快，大家可以用如下的代码来验证一下，然后自己分析结果。

注意：这个代码中用到了time.perf_counter（）函数，这个函数的功能就相当于高精度计时器的启／停开关，并把时间读数返回，显然我们需要在代码的最初import time。

学习了求最大公约数的方法以后，我们发现，欧几里得游戏的过程恰好是用辗转相减法求最大公约数的过程。回到前面的故事，科尔研究出的这个游戏的必杀技是怎样的呢？

科尔研究的结论有以下3点：

（1）这个游戏不是碰运气，胜负中含有数学规律。

（2）两个棋子的个数确定以后，必须仔细分析最后决定胜负的那一次选择会在什么条件下出现，一定要想法把最后控制胜负的那一次选择权掌握在自己手中，否则必输。

（3）推演出决定胜负的那一个局面之后的两条路线，选择必胜的那条路线。

我们以科尔输的例子（33，7）来说明，因为33=4×7+5，所以无论怎么取子，最后一定会出现（5，7）这个局面，用前面学过的最大公约数的符号来描述就是：（33，7）=（5，7），出现（5，7）这个局面时，接下去要取子的这个人没有选择，他只能从7中取5，那么就会出现（5，2）这个局面，用数学符号描述就是：（33，7）=（5，7）=（5，2），出现（5，2）这个局面以后，本轮掌握选择权的人，就有两种选择：

（1）取2个子，剩下（3，2），接下去的局面就是对手只能取2个子，剩下（1，2），自己最终获胜。

（2）取4个子，接下去的局面就是（1，2），则对手胜。

很显然，谁掌握最后的（5，2）这个局面，谁就具有选择权。因此再往前推演，就是如何取子可以迫使对手把（5，2）这个局面剩下来留给自己。

掌握了这个诀窍以后，我们来尝试一下，（64，5）如何取子可以导向胜利呢？

容易知道（64，5）=（4，5）=（4，1），谁被迫选择（4，5）谁就输，那么取子时，就要想办法迫使对手选择（4，5）。怎么取子你会了吗？

作业

1．用程序实现从键盘接收用户输入的一个数字n，并以这个数字为起点，构造一个等差数列，如果输入数字n是奇数，等差数列之间的差为3；如果n是偶数，则等差数列之间的差是4。从n开始，连续加100项，求这100项之和。

2．用递归函数求20的阶乘，注意讲解阶乘的数学意义。

3．巴什游戏，一堆石子有n个，两人轮流取子，规定每人每次至少取一个，最多取m个（m<n），最后取完石子的人获胜，请问应该如何取子？