N个数的最大公约数，最小公倍数求解及hankson问题
1.java实现最大公约数最大公倍数求解
2.hankson问题求解
一． 题目要求
基本要求： 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
1.程序风格良好(使用自定义注释模板)
2.提供友好的输入输出，并进行输入数据的正确性验证。
提高要求：
Hanks博士是BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：
1、 x和a0的最大公约数是a1；
2、 x和b0的最小公倍数是b1。
Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。请你帮助他编程求解这个问题。
输入格式
输入第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。
输出格式
输出共n行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；
样例输入
2
41 1 96 288
95 1 37 1776
样例输出
6
2
二．算法设计思路
1． 多个数据的最大公约数和最小公倍数
根据两个数据的算法，采用迭代法实现多个数据的计算。先计算出前两个数的最大公约数及最小公倍数，递归代入先前定义的计算函数。从而达到计算N个的目的。
2 . hankson.通过数学推算x的取值在a0~b1间，用循环代入题目要求，达到计算x 个数的目的。
三． 代码实现（java）
import java.util.Scanner;
/*
* 1.实现多整数最大公约数，最大公倍数求解
* 2.实现hankson问题x个数的计数*/
public class Ngdc {
static int gcds (int a,int b)//递归调用//两个数的最大公约数求解
{
if(a%b==0)
return b;
else
return gcds(b,a%b);
}
static int multiple(int x,int y)//两个数的最小公倍数求解
{
return(x*y/gcds(x,y));
}
private static int ngcd(int []a)//n个数的最大公约数求解
{
int i=0;
int temp=gcds(a[i],a[i+1]);
i+=2;
while(i<a.length)
{
gcds(temp,a[i]);
i++;
}
return temp;
}
private static int nlcm(int []a)//n个数的最小公倍数求解
{
int i=0;
int temp=multiple(a[i],a[i+1]);
i+=2;
while(i<a.length)
{
multiple(temp,a[i]);
i++;
}
return temp;
}
private static int[][] setArray()//放置数据 函数
{
Scanner sc = new Scanner(System.in);
System.out.println("请输入您想输入数据的组数:");
int n=sc.nextInt();
if(n<1)
{System.out.println("请重新输入");}
int[][] array = new int[n][4];
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < 4; j++) {
array[i][j] = sc.nextInt();
}
}
sc.close();
return array;
}
private static int judgecount(int array[][])//x个数计算函数
{
int count=0;
for(int e=0;e<array.length;e++) {
if(array[e][0]%array[e][1]!=0&&array[e][3]%array[e][2]!=0)
{System.out.println("输入非法，重新输入 （使每一行第一个数被第二个整除，第四个被第二个整除）"); }
else {
for(int i=array[e][0];i<=array[e][3];i++) {
if(gcds(i,array[e][0])==array[e][1]&&multiple(i,array[e][2])==array[e][3])
{count++;
}
}
System.out.println("x个数 "+count*2);}}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请选择您想要的操作方式：1.N个数的最大公约数 2.Hankson");
int s=sc.nextInt();
switch (s) {
case 1:
System.out.println("请输入您想输入的数据个数N:");
int n=sc.nextInt();
int[] array=new int[n];
if(n<2)
{System.out.println("输入有误，请输入大于2的整数");
}else
for(int i=0;i<n;i++)
{
array[i]=sc.nextInt();
}
System.out.println("这N个数的最大公约数是："+ngcd(array));
System.out.println("这N个数的最小公倍数是："+nlcm(array));
sc.close();
break;
case 2:
int arr[][]=setArray();//接收setArray()返回值
judgecount(arr);//调用 x 计数函数
}
}}
四.测试截图
五.个人总结
此次程序设计基本要求算法较为简单，在上次的算法基础上变通，复用即可实现。所以差距现在代码的简洁和高效性上。提高要求中Hankson 算法将题目要求变成代码需要进行对X 的变通。经过数学归纳得出X 值所在范围后，问题得到简化。
虽然本学期开了java课，但用java写一个正真具有功能的代码还是第一次，本次程序设计进一步熟悉了java语法及函数之间的调用，也认识到了java语言的强大。不足之处很多，如在编码的时候经常遇到语法及算法问题，编程实践能力欠缺，时间也拖得有些长。另外，在数据的异常处理方面，也做得不够好，想用try catch 语句，但是由于还没有掌握，便放弃了。只进行了简单的异常处理，达不到完全符合要求。程序的模块化也做得不够好，争取在接下来的时间里填补空缺，下次做得更好。