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 语句，但是由于还没有掌握，便放弃了。只进行了简单的异常处理，达不到完全符合要求。程序的模块化也做得不够好，争取在接下来的时间里填补空缺，下次做得更好。