求N个数的最小公倍数及 Hankson问题
题目一
求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
要求： 1.程序风格良好(使用自定义注释模板)
2.提供友好的输入输出，并进行输入数据的正确性验证。
分析：用辗转相除法能得到两个数的最大公约数；
把N个数存入数组，依次对数组类的两个数进行辗转相除
程序流程图：
代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class MutilDivisor {
List<Integer> list = null;
public int divisor (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{ temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return (a); /*返回最大公约数到调用函数处*/
}
public int gcd (int a,int b)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
//求多个数据的最大公约数
public int muti() {
int temp = list.get(0);
for(int i=1;i<list.size();i++)
{
temp = divisor(list.get(i), temp);
}
return temp;
}
//带参构造
public MutilDivisor(List<Integer> list) {
this.list = list;
}
//无参构造
public MutilDivisor() {
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for(int i=0;i<20;i++)
{ Random rd = new Random();
list.add(rd.nextInt(100)+1);
}
MutilDivisor md = new MutilDivisor(list);
System.out.println(list);
System.out.println("最大公约数为"+md.muti());
}
}
结果：
题目二
已知正整数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的个数；
分析：由于x和a0的最大公约数是a1，所以x最小是a1;
由于x和b0的最小公倍数是b1，所以x最大是b1;
用for循环对x进行遍历，并判断条件是否满足；如果满足两个条件，计数器加一，直到循环结束。
程序流程图：
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Hankson {
private int[][] data = null;
private int[] result = null;
private int size = 0;
//无参构造函数
public Hankson() {
}
//有参构造函数
public Hankson(int size) {
int[][] dt = new int[size][4];
int [] r = new int[size];
this.size = size;
result = r;
data = dt;
}
//从控制台读取数据
public boolean readData () {
BufferedReader bd = new BufferedReader(new InputStreamReader(System.in));
try {
for(int i=0;i<size;i++)
{
String str = bd.readLine();
String[] strings =str.split(" ");
//检查输入...
for (int j = 0; j < strings.length; j++) {
data[i][j] = Integer.parseInt(strings[j]);
}
}
} catch (IOException e) {
e.printStackTrace();
}
return true;
}
public int divisor (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{ temp=a;a=b;b=temp;} /*设置中间变量进行两数交换*/
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return (a); /*返回最大公约数到调用函数处*/
}
//计算最小公倍数
public int multiple(int a,int b) /*自定义函数求两数的最小公倍数*/
{
int temp;
temp=divisor(a,b); /*再次调用自定义函数，求出最大公约数*/
return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
}
//进行计算
public boolean count() {
int temp;
temp = 0;
for (int i = 0; i < data.length; i++) {
result[i]=0;
for(temp = data[i][1];temp<=data[i][3];)
{
if ((divisor(temp, data[i][0])==data[i][1])&&(multiple(temp, data[i][2])==data[i][3])) {
//System.out.println(temp);
result[i]++;
}
temp++;
}
}
return true;
}
public boolean showResult() {
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
return true;
}
public static void main(String[] args) {
Hankson hk = new Hankson(2);
hk.readData();
hk.count();
hk.showResult();
}
}
结果：
总结
通过完成这次作业，加深了我对算法的了解；通过两次对求最大公约数的作业，让我感受到了算法的魅力，由于多次对质数的处理，也让我感受到了质数的强大；对于N个数，求它的最大公约数，其实只要其中有一个质数，那么这N个数的最大公约数就是一，当然要排除全是相同质数的情况；这样就不用依次进行两个数的辗转相除或用其它求两个数最大公约数的算法去进行处理了。
通过对Hankson的“逆问题”的求解，我能从逆向思维来考虑，求最大公约数的问题。这种正向与逆向对同一问题的思考方式值得，更值得我去学习和应用到对算法的学习中去。