java 获取n个数字的gcd
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25890293/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Get the gcd of n numbers
提问by Alberto Miola
This could seem an easy question but I cannot find a solution. I must find the gcd of n numbers.
这似乎是一个简单的问题，但我找不到解决方案。我必须找到 n 个数字的 gcd。
public int getGCD(int a, int b) {
if (b == 0) { return a; }
else { return getGCD(b, a%b); }
}
This is the popular recursive way that calculates the gcd of twonumbers. But if I need to get the gcd of 3, 4, 5... n numbers? I was thinking to do something like this:
这是计算两个数字的 gcd 的流行递归方法。但是如果我需要得到 3、4、5...n 个数字的 gcd 呢？我正在考虑做这样的事情：
public int getGCD(int[] a) {
//the code
}
There is an array of integer as parameter, but I have no idea about the code. Do you have any suggestion?
有一个整数数组作为参数，但我不知道代码。你有什么建议吗？
回答by Sirko
The GCD of a multiple numbers gcd( n1, n2, .... nx )can be computed by incrementally computing the GCD of two numbers:
多个数的 GCDgcd( n1, n2, .... nx )可以通过增量计算两个数的 GCD 来计算：
gcd( n1, n2, .... nx ) == gcd( n1, gcd( n2, gcd( ... , nx ) ) )
Every divisor for all numbers, has to be a divisor for any subset of these numbers. Which in turn leads to the above formula.
所有数字的每个除数都必须是这些数字的任何子集的除数。这反过来又导致了上述公式。
By reusing your given getGCD(int, int)function for two numbers, we can create an additional overload that takes a list of one or more numbers:
通过getGCD(int, int)对两个数字重用给定的函数，我们可以创建一个额外的重载，它接受一个或多个数字的列表：
public int getGCD(int a, int b) {
// implementation for two numbers goes here
}
public int getGCD(int[] a) {
// the GCD of a number with itself is... itself
int gcd = a[0];
// compute incrementally
for( int i=1; i<a.length; i++ ) {
gcd = getGCD( gcd, a[i] );
}
// return result
return gcd;
}
回答by codebot
Try with this,
试试这个，
public static void main(String[] args) {
System.out.println(" GDC: " + getGdc(12, 48, 24, 5));
System.out.println(" GDC: " + getGdc(12, 48, 24));
}
public static int getGdc(int... x) {
// get the smallest of all number no need to check for higher values
int smallest = getSmallest(x);
for(int i = smallest; i >= 1; i--) {
int j;
for(j = 0; j < x.length; ++j) {
if(x[j] % i != 0)
break;
}
// if we pass through the array with all % == 0 return the value
if(j == x.length)
return i;
}
// so the only possible is 1
return 1;
}
// return smallest number of an array of int
public static int getSmallest(int[] x) {
int smallest = x[0];
for(int i = 1; i < x.length; ++i) {
if(x[i] < smallest)
smallest = x[i];
}
return smallest;
}
Refer thisalso for more. Hope this helps
有关更多信息，请参阅此内容。希望这可以帮助
回答by Teepeemm
Java's latest features can come in handy here. The idea is that we take the first two numbers from a, find their gcd, and put that back in a. This is exactly what a reduceoperation does (although I'll use the reduce for an intStream).
Java 的最新特性在这里可以派上用场。这个想法是我们从 中取出前两个数字a，找到它们的 gcd，然后把它放回a. 这正是reduce操作所做的（尽管我将使用reduce 作为intStream）。
You then have:
然后你有：
public int getGCD(int[] a) {
Arrays.stream(a).reduce( (b,c) -> getGCD(b,c) ).getAsInt();
}
You may be able to replace the lambda expression with a method reference:
您可以使用方法引用替换 lambda 表达式：
Arrays.stream(a).reduce(ClassName::getGCD).getAsInt();
(Although I'm assuming the compiler will know you're referring to getGCD(int,int). If it complains, you'd have to rename a method.)
（虽然我假设编译器会知道你指的是getGCD(int,int)。如果它抱怨，你必须重命名一个方法。）
回答by ram kumar
package may23;
/**
*
* @author Ramkumar Raja
*
*/
public class GcdofArrayNumbers {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={8,16,80};
int temp=0;
for(int i =0;i<arr.length;i++)
{
if(i==0)
{
temp=gcdArray(arr[i+1], arr[i]);
i++;
}
else
{
temp=gcdArray(temp, arr[i]);
}
}
System.out.println("Gcd"+temp);
}
public static int gcdArray(int a,int b)
{
int gcd=0;
for(int i=1;i<=a && i<=b;i++)
{
if(a%i==0 && b%i==0)
{
gcd=i;
}
}
return gcd;
}
}
