三种算法求两个正整数的最大公约数和最小公倍数 求三个数的最大公约数和最小公倍数

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

第二次作业

题目:求两个正整数的最大公约数和最小公倍数。

基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。

提高要求:1.三种以上算法解决两个正整数最大公约数问题。

                   2.求3个正整数的最大公约数和最小公倍数。

一. 算法分析

        已知结论:a,b的最大公约数 * 其最小公倍数 = a * b;

如下介绍的三个算法只针对于求解最大公约数,最小公倍数就由上面结论可以得出。

求解两个数的最大公约数算法流程图:

求两个数最小公倍数的算法流程图:

 

1.辗转相除法(两个数)

用辗转相除法求两个数的最大公约数的步骤如下:

1.先用小的一个数除大的一个数,得第一个余数;

2.再用第一个余数除小的一个数,得第二个余数;

3.又用第二个余数除第一个余数,得第三个余数;

4.逐次用后一个数去除前一个余数,直到余数是0为止。那么,最后一个除数就是所求的最大公约数;

5. 输出最大公约数和最小公倍数。

2.辗转相除法(三个数)

如果求三个数的最大公约数,可以先求两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数。这样依次下去,直到最后一个数为止。最后所得的一个最大公约数,就是所求的几个数的最大公约数。

3.穷举法(两个数)

用穷举法求解两个数的最大公约数步骤如下:

1. 输入两个正整数;

2. i = a(或b);

3. 若a,b能同时被i整除,则i即为最大公约数,即max = i,结束;

4. 否则i–,再回去执行2;

5.输出最大公约数和最小公倍数。

4.相减法(两个数)

1.输入两个正整数a和b;

2.如果a > b,则a = a – b;

3.如果a < b,则 b = b – a;

4.如果a = b,则a(或b)即为两数的最大公约数

5.如果a ≠ b,则重复执行1;

6.输出最大公约数和最小公倍数。

二.源代码

/** * 第二次作业        题目:求两个正整数的最大公约数和最小公倍数。        基本要求:1.程序风格良好(使用自定义注释模板),两种以上算法解决最大公约数问题,提供友好的输入输出。        提高要求:1.三种以上算法解决两个正整数最大公约数问题。          2.求3个正整数的最大公约数和最小公倍数。        三种方法:相减法;  穷举法;  辗转相除法        利用穷举法计算三个数的最小公倍数和最大公约数 */package program;import java.util.Scanner; class Calculate{	private int num1;   //需要求解的第一个数据	private int num2;   //需要求解的第二个数据		//构造方法	public Calculate() {}		//相减法计算两个数的最大公约数和最小公倍数	void sub(int num1, int num2) {		int x, y;  //用于保存num1,num2初始数据		x = num1;  		y = num2;		while(num1 != num2) {           //循环条件为两数不相等			if(num1 > num2)             //如果第一个数大于第二个数				num1 = num1 - num2;     //两数相减			else				num2 = num2 - num1;		}		System.out.println("---------------------------------");		System.out.println("利用相减法计算所得的最大公约数为:"+ num1);     //最大公约数		System.out.println("利用相减法计算所得的最小公倍数为:"+ x*y/num1);    //最小公倍数		System.out.println("---------------------------------");	}		//穷举法求解两个数的最大公约数和最小公倍数	void exp(int num1, int num2) {		int  x, y, i;		x = num1;		y = num2;		int max = 0;    //最大公约数		for(i=1; i<=num1; i++) 			if(num1%i == 0 && num2%i == 0) 				max = i;		System.out.println("---------------------------------");		System.out.println("利用穷举法计算所得最大公约数为:"+max);		System.out.println("利用穷举法计算所得最小公倍数为:"+ x*y/max);	//最小公倍数		System.out.println("---------------------------------");	}		//辗转相除法求解两个数的最大公约数和最小公倍数	void divide(int num1, int num2) {		int r,x,y;    //r表示两个数的余数		x = num1;		y = num2;		//如果两个数前者<后者,则互换两个数		if(num1 < num2) {			r = num1;			num1 = num2;			num2 = r;		}		while(num2 != 0) {   //逐次用后一个数去除前一个余数			r = num1;			num1 = num2;			num2 = r%num2;		}		System.out.println("---------------------------------");		System.out.println("利用辗转相除法计算所得的最大公约数为:"+num1);		System.out.println("利用辗转相除法计算所得的最小公倍数为:"+ x*y/num1);		System.out.println("---------------------------------");	}		//方法的重载	//利用穷举法计算三个数的最大公约数和最小公倍数	void exp(int num1, int num2,int num3) {		int max, min;   		int i, j;             //保存最终的最大公约数和最小公倍数		if(num1 < num2) {       			min = num1;			max = num2;		}		else {			min = num2;			max = num1;		}		if(min > num3) {			min = num3;           //计算三个数中的最小数		}		if(max < num3) {          //求三个数中的最大数			max = num3;		}		for(i=min; i<=min; i--) {			if(num1%i==0 && num2%i==0 && num3%i==0) {      //当三个数同时被i整除,此时i为三个数对的最大公约数				break;			}		}		for(j=max;;j++) {			if(j%num1==0 && j%num2==0 && j%num3==0) {      //当j能被三个数同时整除,j为三个数的最小公倍数				break;			}		}		System.out.println("计算三个数所得的最大公约数为:"+i);		System.out.println("计算三个数所得的最小公倍数为:"+j);	}}public class TestNum {	public static void main(String[] args) {		Scanner s = new Scanner(System.in);		System.out.println("请输入需要计算的数据的个数(2 or 3):");     //从键盘输入需要计算的数据的个数,两个数或者三个数		int type = s.nextInt();		switch (type) {            		case 2:			twoNum();      //计算两个数的最大公约数和最小公倍数			break;         		case 3:			threeNum();    //计算三个数的最大公约数和最小公倍数			break; 		}	} 	//利用三种方法计算两个数的最大公约数和最小公倍数	static void twoNum() {		Scanner s = new Scanner(System.in);		System.out.println("请输入需要计算的正整数:");     //从键盘输入两个数a, b		int a = s.nextInt();		int b = s.nextInt();		Calculate c1 = new Calculate();             //创建一个Calculate的对象 c1		c1.divide(a, b);                       //调用divide方法(辗转相除法)计算		c1.sub(a, b);                          //调用sub方法(相减法)计算		c1.exp(a, b);                          //调用exp方法(穷举法)计算	}		//利用穷举法计算三个数的最大公约数和最小公倍数,效率不高    static void threeNum() {    	Scanner s = new Scanner(System.in);		System.out.println("请输入需要计算的正整数:");     //从键盘输入两个数a, b		int a = s.nextInt();		int b = s.nextInt();		int c = s.nextInt();		Calculate c2 = new Calculate();      //创建一个Calculate的对象 c2		c2.exp(a, b, c);                     //调用exp方法(穷举法)计算	} 	} 

三.运行结果

1. 当计算两个数的最大公倍数和最小公倍数的结果,由三种算法得出的结果

2. 利用穷举法计算三个数的最大公约数和最小公倍数的结果

四.学习心得

1.深入学习了利用不同的算法来解决求解两个正整数的最大公约数和最小公倍数,还掌握了利用穷举法计算三个数的最大公约数和最小公倍数,利用穷举法计算的效率比较低,本来自己试着尝试用递归的方法调用divide()方法来求解三个数的问题,尝试了利用数组进行输入信息的保存,同时利用Array.sort()函数进行排序,但是由于参数调用的问题始终无法得到正确的结果。以后可以进行深入的学习。

2.通过解决此问题让我更加深刻的理解了代码规范的重要性,很多次错误都是出在多或者少“{}”上面,浪费了大量的时间。

3.我是利用Java来编写代码的,最开始一股脑全部写在了main方法中,没有充分体现Java语言的特点,慢慢自己也注意到了,对部分代码进行了封装,比之前的程序看起来好看一些,可读性也相对好一些,不过还是要不断完善和学习。

点这里可以跳转到人工智能网站