實現擴展歐幾里得算法

-4

我想做一個函數組合，給定兩個整數n和m，返回一個整數的三元組：（a，b，gcd（n，m）），使得： am + bn = gcd（ n，m）不應該認爲整數總是正數。實現擴展歐幾里得算法

gcd :: Int -> Int -> Int 
gcd n m 
| n == m = n 
| n > m = gcd (n-m) m 
| n < m = gcd n (m-n) 

combine :: Int ->Int -> (Int,Int,Int) 
x1=1; y1=0; x2=0; y2=1 
while (m /=0) 
( q=div n m ; r=mod n m ; n=m ; m=r 
    t=x2 ; x2=x1-q*x2 ; x1=t 
    t=y2 ; y2=y1-q*y2 ; y1=t ) 
combine n m = (x1,y1,gcd(n,m))

您將找到一個屏幕截圖圖片鏈接。點擊我--->！[鏈接] http://prikachi.com/images.php?images/238/8749238o.png請如果有人有一個解決方案，並有想法我可以取代創造的功能，將不勝感激。測試的功能：結合3 2應該給這樣的結果=>（1，-1,1）

來源

2016-04-12 Nikolay Ivanov

我想你可能會尋找這樣的事情：

combine :: Int ->Int -> (Int,Int,Int) 
combine n m = (x1, y1, gcd n m) where 
    (x1, y1) = gcdext n m 

gcdext :: Int -> Int -> (Int, Int) 
gcdext n m = gcdexthelper n m 1 0 0 1 where 
    gcdexthelper n m x1 y1 x2 y2 
    | m == 0 = (x1, y1) 
    | otherwise = gcdexthelper m r x1p y1p x2p y2p where 
    q = div n m 
    r = mod n m 
    x1p = x2 
    y1p = y2 
    x2p = x1 - q * x2 
    y2p = y1 - q * y2

當然你也可以實現與while循環一樣，但我相信在Haskell中遞歸更具可讀性，所以我在這裏使用它。

順便說一下，GCD是Haskell中的標準庫函數，所以不需要編寫自己的。

來源

2016-04-12 20:17:00

哦，我明白了！我試了一下，結果發現它已經在裏面了。但是，我糾正了你的一個錯誤，在哪裏 - >合併n m =（x1，y1，gcdx n m）gcd **。無論如何，Haskell是一種不尋常的語言，我還不知道它的庫。感謝您的快速響應，解釋和幫助！ P.S [Idk爲什麼我已經得到-3率]：D –

您也可以使用'（q，r）= divMod n m'。 – chepner

實現擴展歐幾里得算法

回答

相關問題