java中的Euler Project 5，爲什麼會有不同的結果？

/* Smallest multiple */ 
/* 
* 2520 is the smallest number that can be divided by each 
* of the numbers from 1 to 10 without any remainder.What 
* is the smallest positive number that is evenly divisible 
* by all of the numbers from 1 to 20? 
*/ 
public class SmallestMultiple { 
    public static int gcd(int m, int n){ 
     if(n>m){ 
      int temp = m; 
      m = n; 
      n = temp; 
     } 
     int gcdNum = m; 
     while(m != 0){ 
      m = gcdNum%n; 
      gcdNum = n; 
      n = m; 
     } 
     return gcdNum; 
    } 
    private static int lcm(int m, int n){ 
     return m*n/gcd(m,n); 
    } 
    static int multiple(int start, int end){ 
     if(start > end){ 
      int temp = end; 
      end = start; 
      start = temp; 
     } 
     else if(start == end) 
      return start; 
     else 
      return lcm(end, multiple(start, end-1)); 
     return multiple(start, end); 
    } 
    public static void main(String[] args) { 
     System.out.println(multiple(11,19)); // line a--Which is equal to multiple(1,19) 
     System.out.println(multiple(11,20)); // line b--Which is equal to multiple(1,20) 
    } 
}

我認爲答案倍數（1,19）和倍數（1,20）會得到相同的結果。但與我的代碼，他們是不同的，倍數（1,19）= 232792560（正確答案）和倍數（1,20）= 18044195這是錯誤的答案！我知道有很多更簡單的算法，但我只想知道我的問題在哪裏... 誰能告訴我這個問題？java中的Euler Project 5，爲什麼會有不同的結果？

來源

2013-04-18 mitcc

你有int溢出，當你計算

Prelude> 232792560 * 20 
4655851200 
Prelude> it `quotRem` (2^32) 
(1,360883904)

因此你獲得360883904/20 = 18044195。

可以

使用long或
計算m * (n/gcd(n,m))

避免溢出（第二種方法不會佔用你太多的更遠，如果上限爲23，int太小而無法保持結果）。

來源

2013-04-18 15:02:46

非常感謝，我從你的答案中得到了原因！感謝agin !!!由於我是一個新手，我無法投票給其他人（名聲低於15 -.- !!!），這樣的可惜~ – mitcc

@mitcc你不能贊成，但你可以接受一個答案，並通過這樣標記這個問題就解決了。 – Sirko

你的問題幾乎只是一個整數溢出。

Java中最大的int號碼是Integer.MAX_VALUE = 2147483647。

在某些時候，您嘗試運行lcm(20, 232792560)。後者是multiplay(1,19)的結果。

在函數內部，您嘗試計算m*n/gcd(m,n)。

與m == 20,n == 18044195和gcd(m,n) == 20，這得到20 * 18044195/20。

第一個產品實際上是20 * 18044195 == 4655851200，它大於Integer.MAX_VALUE，因此會發生溢出並導致總體結果不佳。

一個解決方案是切換到long類型的地方，其最大值爲Long.MAX_VALUE == 9223372036854775807。

來源

2013-04-18 15:04:45 Sirko

非常感謝〜 – mitcc

java中的Euler Project 5，爲什麼會有不同的結果？

回答

相關問題