算法-辗转相除法
1个回答
展开全部
算法：辗转相除法（欧几里得算法）
对于两个数的最大公约数的求解，在我们的笔算过程中，通常是使用一个短除法，本质上其实也就是进行一个质因数分解的过程，但对于一个较大的数来说，将其进行质因数分解是一件非常耗时的过程，这显然不是一个好的做法，因此基于数论基础，我们有了辗转相除法，也叫做欧几里得算法。
在叙述该算法之前，先了解辗转相除法的实现前提也就是GCD递归定理：
基于上面的GCD递归定理，我们便可以知道可以采用递归的方式，对两个整数的最大公约数进行相对较为高效的计算。
下面我们采用递归方式实现辗转相除法。
(以下引用自《算法导论》)
GCD(a, b)
对于两个数的最大公约数的求解，在我们的笔算过程中，通常是使用一个短除法，本质上其实也就是进行一个质因数分解的过程，但对于一个较大的数来说，将其进行质因数分解是一件非常耗时的过程，这显然不是一个好的做法，因此基于数论基础，我们有了辗转相除法，也叫做欧几里得算法。
在叙述该算法之前，先了解辗转相除法的实现前提也就是GCD递归定理：
基于上面的GCD递归定理，我们便可以知道可以采用递归的方式，对两个整数的最大公约数进行相对较为高效的计算。
下面我们采用递归方式实现辗转相除法。
(以下引用自《算法导论》)
GCD(a, b)
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
|
广告 您可能关注的内容 |
