使用欧几里得算法实现求两个数的最大公约数。
算法:
1.较大的数除以较小的数,若余数为零,则较小的数是这两个数的最大公约数。
2.否则将除数换为被除数,余数换为除数,转到1继续执行至余数为零。
201111621302
1.算法实现:
class Gys{ //递归实现 public int gcd(int m,int n){ if(m<n){ int tmp = m; m = n; n = tmp; } if(n == 0) return m; else return gcd(n,m%n); } //非递归实现 public int gcd2(int m,int n){ if(m<n){ int tmp = m; m = n; n = tmp; } if(n == 0) return m; while(n>0){ int tmp = m%n; m = n; n = tmp; } return m; } }
2.测试上述算法:
import java.util.Scanner; public class Marking { public static void main(String[] args) { //测试上述欧几里得算法 System.out.println("请依次输入两个整数:"); int n=0,m=0; Scanner scan = new Scanner(System.in); try { n = scan.nextInt(); m = scan.nextInt(); Gys g = new Gys(); System.out.println("递归实现测试:"+n+"和"+m+"的最小公约数是:"+g.gcd(n,m)); System.out.println("非递归实现测试:"+n+"和"+m+"的最小公约数是:"+g.gcd2(n,m)); } catch (Exception e) { System.out.println("输入有误,请重新输入!"); Marking.main(null); } } }
3.测试结果:
4.总结:
算法经测试求两数最大公约数正确。