黑马程序员技术交流社区

标题: 欧几里得算法的问题！ [打印本页]

---

作者: 田建    时间: 2012-6-24 10:54
标题: 欧几里得算法的问题！


今天写了下欧几里得算法，求两个数的最大公约数,代码写得出来，但是不是十分明白为什么这样求出来的是它们的最大公约数：

1. import java.util.*;
   
2. class Example0408
   
3. {
   
4. public static void main(String[] args)
   
5. {
   
6. Random random=new Random();
   
7. float x=random.nextFloat();
   
8. int m=Math.round(999*x+2);
   
9. float y=random.nextFloat();
   
10. int n=Math.round(999*y+2);
    
11. System.out.println("m="+m+"\t\tn"+n);
    
12. while(m>0)
    
13. {
    
14. if(m<n)
    
15. {
    
16. int temp=m;
    
17. m=n;
    
18. n=temp;
    
19. System.out.println("m="+m+"\t\tn="+n);
    
20. }
    
21. m-=n;
    
22. }
    
23. System.out.println("Theg.c.d of m and n is"+n);
    
24. }
    
25. 
    
26. }

复制代码

---

作者: 黑马_张佳超    时间: 2012-6-24 13:45
两个数的最大公约数，就是能整除这两个数的最大数。
例如：
28和8的最大公约数，大家都知道是4。用其中较大的数减去较小的数得到的数不为零的话同样也可以被这个最大公约数整除掉。也就是28-8之后同样也可以被4整除。
红色字体部分就是代码的核心执行内容。
首先判断m和n的大小，如果m<n就把m和n的值互换。这样做是让m变量始终存储的是这两个数中较大的数。
然后就执行m-=n，还是那个原理，假设z为最大公约数，m-n执行后m>0，这个时候m得到的值同样还可以被z整除，这个地方有那么一点儿绕，再举个小例子：18和8，最大公约数为2,18相当于9个2，8就相当于4个2，用18减去8就是用9个2减去4个2，同样还能被2整除掉。

---

作者: 田建    时间: 2012-6-24 14:23

黑马_张佳超 发表于 2012-6-24 13:45
两个数的最大公约数，就是能整除这两个数的最大数。
例如：
28和8的最大公约数，大家都知道是4。用其中较大 ...

恩恩   想明白了，多谢点拨！

---

作者: 黑马_张佳超    时间: 2012-6-24 14:25

田建 发表于 2012-6-24 14:23
恩恩   想明白了，多谢点拨！

:handshake不客气

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2