如何使用Euclid算法來計算gcd，分割數和不同商數的數量？

我是Python的初學者。我正在試圖用歐幾里德的算法做一個程序。問題是我不知道如何製作這個程序：該程序受以下觀察的啓發。由歐幾里得算法產生的用於計算GCD（a，b）的形式a = b * q + r的線的數量不遵循可預測的模式。我們要說的是，如果計算出的GCD大於1，需要更多的分割並且產生的中間商是高度可變的，那麼算法的執行比另一個更有趣。例如，在計算GCD（13，8）得到：如何使用Euclid算法來計算gcd，分割數和不同商數的數量？

13 = 8 * 1 + 5 
    8 = 5 * 1 + 3 
    5 = 3 * 1 + 2 
    3 = 2 * 1 + 1 
    2 = 1 * 2 + 0 
    gcd (13, 8) = 1 
    5 Steps required 
There are only 2 different quotients: 1 and 2 
It is not a very interesting example. 
Instead, calculating the MCD (455, 355): 
455 = 355 * 1 + 100 
355 = 100 * 3 + 55 
100 = 55 * 1 + 45 
55 = 45 * 1 + 10 
45 = 10 * 4 + 5 
10 = 5 * 2 + 0 
gcd (455, 355) = 5 
6 steps (or lines or divisions) are required 
4 different quotients: 1, 3, 4, 2 
So, this case is more interesting than the last.

我想找到在由用戶給定的自然數區域有趣的情況。要做到這一點，程序會詢問區域的最小範圍的值，該值應該大於等於2，該區域的最大範圍的值必須大於等於3，即GCD的最小值是期望的，也是最小期望的分割數和不同商的最小數目。所以總而言之，我想寫一個實現函數ngcd（a，b）的程序，該程序通過歐幾里德算法計算a和b的最大公約數。另外，這個函數在執行期間計算其他度量。具體而言，該函數計算a和b的gcd，分割數（形式爲a = b * q + r的線）以及在調用期間生成的不同商數的數量。

的什麼，我試圖做一個例子是其中之一：

Enter the minimum value range >=2: 100 
    Enter the maximum value range >=3: 200 
    Enter the minimum value of GCD: 3 
    Enter the minimum number of divisions: 5 
    Enter minimum number of different quotients: 4 
    GCD (156, 129) = 3, divisions: 5, different quotients: 4 
    GCD (159, 126) = 3, divisions: 5, different quotients: 4 
    GCD (171, 141) = 3, divisions: 5, different quotients: 4 
    GCD (177, 135) = 3, divisions: 5, different quotients: 4 
    GCD (177, 144) = 3, divisions: 5, different quotients: 4 
    GCD (183 , 126) = 3 , divisions: 5 , different quotients: 4 
    GCD (183 , 135) = 3 , divisions: 5 , different quotients: 4 
    GCD (183 , 141) = 3 , divisions: 5 , different quotients: 4 
    GCD (183 , 144) = 3 , divisions: 5 different quotients: 4 
    GCD (183, 156) = 3 , divisions: 5 different quotients: 4 
    GCD (186, 129) = 3 , divisions: 5 , different quotients: 4 
    GCD (189, 150) = 3, divisions: 5 different quotients: 4 
    GCD (192, 141) = 3, divisions: 5, different quotients: 4

感謝您的幫助！

來源

2016-05-08 Zentraleinheit

，如果你被允許使用我不知道內置from fractions import gcd，如果你是它應該是很簡單image

有兩種方法可以做到這一點，遞歸迭代和通常遞歸函數更乾淨並有更好的表現，因此可以作爲這個工具：

遞歸：

def gcd(u, v): 
return gcd(v, u % v) if v else abs(u)

它應該給你的想法在數學至少部分。

來源

2016-05-08 05:03:04

如何使用Euclid算法來計算gcd，分割數和不同商數的數量？

回答

相關問題