算法:理解“扩展欧几里得算法”

这个算法还是有点意思的,需要一些思考量和理解。

如何理解?

欧几里得算法没扩展之前,计算的两个数的最大公约数,比如计算144和24的最大公约数,计算的过程如下:
最开始:144 24
第一次:24 144 % 24 即 24 0
发现直接整数了,说明24就是144的公约数,所以计算结果就是:24
如果用a,b来表示,变为一般形式的话:
给定两个数(a, b),现在想计算两者的最大公约数,那么可以那b来模a,如果结果为0,那说明b就是两者的最大公约数,如果有余数,比如:
最开始:14 6
第一次:6 14 % 6 即6 2
第二次:2 6 % 2 即2 0
反过来看:2是2、6的最大公约数,而6不是6、14的最大公约数,但是K * 6 + 2能够得到14,且6能被2整除,说明2是14的公约数。

扩展之后

如果将欧几里得算法进行扩展,就是这样,比如:
144 24,我们知道两者的最大公约数是24,那么144x + 24y = 24,这个x、y分别是什么呢?显然是x = 0,y = 1;但如果是14x + 6y = 2呢?通过上面求最大公约数的过程,我们能够知道,最后一步的2x1 + 6y1 = 2是很容易的得到结果的,但是怎么样从这个结果推回来,得到一开始的y呢?——这个就是扩展欧几里得算法。

这样来理解:
14x + 6y
6x2 + (14 % 6)y2
2x1 + (6 % 2)y1
一步一步往前推,14 % 6 == 2,说明y2 = x1,那么6x2 == (6 % 2)y1 == (6 - 6 / 2 * 2)y1(这里的是整除,用7 % 4来看,会更清晰,即等于7 - 7 / 4 * 4)
通过这样的递推,即从后往前推(或者用递归的思想,一直归到最底,然后再计算回来)就能实现这一算法了。

上一篇:LeetCode-144 二叉树的前序遍历


下一篇:144. 二叉树的前序遍历