|
文章目录
一、题目要求二、算法分析三、代码实现四、总结
一、题目要求
求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。 1.程序风格良好(使用自定义注释模板) 2.提供友好的输入输出，并进行输入数据的正确性验证。
二、算法分析
注：遵循一条数学定理：两数之积等于两数的最大公约数与最小公倍数之积
n个数的最大公约数和最小公倍数的求法是基于两个数的求法之上的：
1、先求两个数的最大公约数和最小公倍数
2、再用所求的最小公约数哥最小公倍数与下一个数求最大公约数和最小公倍数
3、依次类推，重复1,2步知道求完所有数的最大公约数和最小公倍数
三、代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 题目要求:
* 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
* 1.程序风格良好(使用自定义注释模板)
* 2.提供友好的输入输出，并进行输入数据的正确性验证
* 类方法:
* 方法public static int gcd(int x, int y)是求两个数的最大公约数
* 方法public static int ngcd(List target , int z) 是求n个数的最大公约数
* 方法public static int lcm (int x , int y)是求两个数的最小公倍数
* 方法public static int nlcm (List target , int z)是自n个数的最小公倍数
*
* 完成时间:2019年3月20日
* @author 包海金
* @version 1.0.0
*/
class Solution {
/**
* 辗转相除法的递归调用求两个数的最大公约数
* @param x 其中一个数
* @param y 其中另一个数
* @return 递归调用，最终返回最大公约数
*/
public static int gcd(int x, int y) {
return y == 0 ? x : gcd(y , x % y);
}
/**
* 求n个数的最大公约数
* @param Listlist n个数的集合
* @param z 数据个数
* @return 递归调用，最终返回最大公约数
*/
public static int ngcd(List target , int z) {
if(z == 1) {
return target.get(0);//真正返回的最大公约数
}
//递归调用，两个数两个数的求
return gcd(target.get(z - 1) , ngcd(target , z - 1));
}
/**
* 辗转相除法的递归调用求两个数的最小公倍数
* @param x 其中一个数
* @param y 其中另一个数
* @return 递归调用，最终返回最小公倍数
*/
public static int lcm (int x , int y) {
return (x * y) / gcd(x , y);
}
/**
* 求n个数的最小公倍数
* @param Listlist n个数的集合
* @param z 数据个数
* @return 递归调用，最终返回最小公倍数
*/
public static int nlcm (List target , int z) {
if (z == 1) {
return target.get(z - 1);//真正返回的最小公倍数
}
//递归调用，两个数两个数的求
return lcm(target.get(z - 1) , nlcm(target , z-1));
}
public static void main(String [] args) {
Scanner scanner = new Scanner(System.in);
int num = 0;//数据个数
List target = new ArrayList();//数据集合
System.out.println("------------------------------------------------------------");
System.out.println("请输入需要计算最大公约数和最小公倍数的个数:");
try {
num = scanner.nextInt();
System.out.println("请输入需要计算最大公约数和最小公倍数的数组:");
for (int i = 0; i |