找到n個數字的GCD

我在寫一個簡單的程序，要求輸入5個數字並輸出他們的GCD。我已經發現瞭如何用兩個數字用一個簡單的方法做到這一點：找到n個數字的GCD

private static int gcd(int number1, int number2) //Finds GCD of 2 numbers. 
{ 
    if(number2 == 0) 
    { 
     return number1; 
    } 
    return gcd(number2, number1%number2); 
}

在return語句的實際是什麼題混淆了我，雖然我不知道我怎麼會寫了這一點，5甚至更多的數字。我聽說用gcd（a，b，c）= gcd（gcd（a，b），c）遞歸地執行這種方法是最好的方法，但我想我遇到了麻煩有問題的數學邏輯。我只需要一個很好的起點，真的，如何返回3個數字，然後是4，然後是5等等。我想，一旦我獲得了邏輯部分，我就會明白如何做到這一點更容易。

來源

2013-03-12 Hydlide

這似乎已經問過，請參閱http://stackoverflow.com/a/4887702/477522 – ajmartin 2013-03-12 00:42:29

這在任何搜索過程中都沒有出現。感謝您的發現。 – Hydlide 2013-03-12 00:47:49

您應該將您現有的gcd(int, int)方法視爲「黑匣子」;您的新gcd(int, int, int, int, int)方法可以在不知道工作原理的情況下調用它。你可以這樣寫：

private static int gcd(int a, int b, int c, int d, int e) 
{ 
    return gcd(gcd(a, b), gcd(gcd(c, d), e)); 
}

或者，一個較爲普遍的解決方案，你可以寫一個方法gcd(int, int...)這需要任何的爭論正數，通過使用Java 5的變種，ARGS支持：

private static int gcd(int number1, int... otherNumbers) 
{ 
    int result = number1; 
    for(int number: otherNumbers) 
     result = gcd(result, number); 
    return result; 
}

（注意在這兩種情況下，這個函數在編程意義上並不是「遞歸」的，前一種方法遞歸嵌套調用gcd(int, int)，但這並不是程序員通過「遞歸」所表達的意思，原來的gcd(int, int)函數，然而，是遞歸，因爲它實際上是自己調用它自己的。）

來源

2013-03-12 00:39:43 ruakh

好吧，是的，我有類似的東西，但它給了我錯誤，所以我假設我的問題只是在返回語句中對整數進行排序。我現在就玩一下。謝謝。 :) – Hydlide 2013-03-12 00:43:13

下面是關於最大公因子的材料透視圖。想想一個矩形的地板，尺寸是m和n。 m和n的GCD是最大的正方形瓷磚的尺寸，它將完美地貼合在該地板上。

所以在你使用的算法中，你從兩個數字開始，例如8和10.然後你的程序用一個數字（比如8）和兩個數字的模數重複這個過程，即2。相當於砍掉一個8x8的部分，因爲我們知道無論哪個瓷磚進入剩餘的位都會適合該區域。我們剩下一個2x8部分。重複這個過程，我們將得到2作爲GCD。我希望能夠清楚你正在使用的算法的實際含義。因此，將這個概念擴展到三個數的GCD，我們可以說m，n和p的GCD是最大的立方塊，其將適合於尺寸爲m x n x p的矩形棱柱。爲了找到這個GCD，我們首先找到適合於棱鏡的一個面的方形瓷磚。然後，我們可以用這個維度來切割棱鏡的橫截面，並截取該橫截面的GCD。當然，這可以擴展到更高的維度，我們無法準確觀察！

來源

2013-03-12 00:45:00 architectpianist

這是一個非常出色的可視化。非常感謝。 – Hydlide 2013-03-12 00:48:25

找到n個數字的GCD

回答

相關問題