java Java中数组中所有数字的LCM
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17689529/
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
LCM of all the numbers in an array in Java
提问by Anindya Guha
I have an array of ints, and I'm trying to find the LCM (least common multiple) of all the values in the array. I've written an lcmmethod separately; it takes two values as input, and returns the lcm. My lcmmethod works perfectly fine, but when I use it to find the LCM of all the values I get a wrong answer.
我有一个整数数组，我试图找到数组中所有值的 LCM（最小公倍数）。我lcm单独写了一个方法；它需要两个值作为输入，并返回 lcm。我的lcm方法工作得很好，但是当我使用它来查找所有值的 LCM 时，我得到了错误的答案。
Here are my gcdand lcmmethods:
这是我的gcd和lcm方法：
public static int gcd(int a, int b){
if (a<b) return gcd(b,a);
if (a%b==0) return b;
else return gcd(a, a%b);
}
public static int lcm(int a, int b){
return ((a*b)/gcd(a,b));
}
This is what I have for the lcm of the array values:
这是我对数组值的 lcm 所拥有的：
public static int lcmofarray(int[] arr, int start, int end){
if ((end-start)==1) return lcm(arr[start],arr[end-1]);
else return (lcm (arr[start], lcmofarray(arr, start+1, end)));
}
When I put in an array that has the numbers 1 to 5 as arr, 0 as startand the length of the array as end, I get 30 as the answer, while I want 60. When I put in an array containing all the numbers from 1 to 10, I get 840 instead of 2520. I really can't explain that.
当我放入一个数组，该数组的数字为 1 到 5 arr，start数组的长度为end30，而我想要 60。当我放入一个包含从 1 到 0 的所有数字的数组时10，我得到的是 840 而不是 2520。我真的无法解释。
The algorithm should work--I've worked it out in my head. Can't figure out what the problem is with my code.
算法应该可以工作——我已经在脑海中计算出来了。无法弄清楚我的代码有什么问题。
Any help will be appreciated.
任何帮助将不胜感激。
回答by user2514440
If you change your gcd function to
如果您将 gcd 功能更改为
public static int gcd(int a, int b){
if (a<b) return gcd(b,a);
if (a%b==0) return b;
else return gcd(b, a%b);
}
it should work okay.
它应该可以正常工作。
回答by Akanksha
The above method looks good but it is getting stack overflow error because of recursive calls:
上面的方法看起来不错，但是由于递归调用，它会出现堆栈溢出错误：
Please find the below solution:
请找到以下解决方案：
public int findHCF(int a, int b) {
if (b>a){
return findHCF(b, a);
}
while(a%b!=0){
int temp = b;
b=a%b;
a=temp;
}
return b;
}
回答by Hirak JD
Brief idea about the logic behind the code-
LCM(a,b)=a*b/HCF(a,b)
关于代码背后逻辑的简要想法-
LCM(a,b)=a*b/HCF(a,b)
You can do this using the following code-
您可以使用以下代码执行此操作 -
package hackerrank;
/*
* Author Hirak JD
*/
import java.util.Arrays;
public class LCM {
public static void main(String args[]) {
int[] set= {2,3,6,8};
int lcm=1;
for(int each:set) {
lcm=calculateLcm(lcm,each);
}
System.out.println("LCM for "+Arrays.toString(set)+" is : "+lcm);
}
private static int calculateLcm(int lcm, int each) {
return lcm*each/gcd(lcm,each);
}
private static int gcd(int val1, int val2) {
if(val1==0||val2==0)
return 0;
if(val1==val2)
return val1;
if(val1>val2)
return gcd(val1-val2,val2);
return gcd(val1,val2-val1);
}
}
