Algorithms4th 1.1.25 欧几里得算法——数学归纳法证明

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Algorithms4th 1.1.25 欧几里得算法——数学归纳法证明，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1535字，纯文字阅读大概需要3分钟。

内容图文

欧几里得算法的自然语言描述

计算两个非负整数p和q的最大公约数：

若q是0，则最大公约数为p。否则将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。

 

数学归纳法证明

基础步骤：

若q = 0，则 gcd(p, q) = gcd(p, 0) = p。

归纳步骤：

令 p = a * q + r， 其中 p、a、q、r 均为非负整数。

设 d 整除 p 和 q， 则 d 可以整除 p - a * q = r，即 p / d = a*q / d + r / d 。

此时， d 为 p，q 的公约数，且 d 为 q，r 的公约数，即 p 和 q 的公约数 = q 和 r 的公约数 = d 。

也即 gcd(p, q) = gcd(q, r) ,  其中 r 为 p 除以 q 的余数。

不断归纳，直至函数 gcd 的第二个参数为0，此时得到基础步骤。

此时我们已经证明了最终的结果是 p 和 q 的一个约数。

 

然而这还没完，因为我们只证明了最终结果是一个公约数，但没有证明它是最大的公约数。

 

因为 d 整除 p 和 q，可得 d 整除 p - a * q = r, 因此 p 和 q 的任意约数也为 q 和 r 的约数；

同理，d整除 q 和 r， 可得 d 整除 a * q + r  = p， 因此q 和 r 的任意约数也为 p 和 q 的约数。

综上，p 和 q 的约数集等于 q 和 r 的约数集。

 

接下来由递推法：

假定当函数gcd()的第二个参数为0时，第一个参数为m，可得 p 和 q 的约数集与 m 和 0 的约数集相同。

由数学归纳法的基础情况知， 而 m 和 0 的最大公约数为 m， 即 m 和 0 的约数集的最大值为 m，

由此可得 p 和 q 的约数集的最大值也为 m 。

 

综上，欧几里得算法得证。

 

献上Java代码：

 1 public class Euclid
 2 {
 3     public static int Euclid(int p, int q) {
 4     　　if(q == 0)
 5         　　return p;
 6     　　int r = p % q;
 7     　　return Euclid(q,r);
 8     }
 9 
10     public static void main(String[] args) {
11         int result = Euclid(16, 24);
12         System.out.println(result);
13　　　}
14　}    

 

内容总结

以上是互联网集市为您收集整理的Algorithms4th 1.1.25 欧几里得算法——数学归纳法证明全部内容，希望文章能够帮你解决Algorithms4th 1.1.25 欧几里得算法——数学归纳法证明所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---