GGT.hs
Ausführbarer Haskell-Code aus der Vorlesung am 18.05.2016 zum erweiterten euklidischen Algorithmus.
GGT.hs
—
Haskell source code,
1 KB (1839 bytes)
Dateiinhalt
{- Haskell Code zur Vorlesung "Logik und Diskrete Strukuren" am 18.05.2016, ausführbar mit GHCI, siehe www.haskell.org Lehrstuhl TCS, LMU München Verwendungsbeispiel: linux-machine:~/S16_LDS> ghci GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Prelude> :l GGT.hs [1 of 1] Compiling GGT ( GGT.hs, interpreted ) Ok, modules loaded: GGT. *GGT> ggT(24,15) =ggT(24,15) =ggT(15,9) =ggT(9,6) =ggT(6,3) =ggT(3,0) 3 *GGT> eggT(24,15) 3 = 0*6 + 1*3 3 = 1*9 + -1*6 3 = -1*15 + 2*9 3 = 2*24 + -3*15 (3,2,-3) *GGT> -} module GGT where import Debug.Trace -- damit man sieht, wie gerechnet wird --ggT(a,b) = trace ("=ggT("++(show a)++","++(show b)++")") $ ggT'(a,b) -- Variante ohne Vertauschung ggT(a,b) = trace ("=ggT("++(show a)++","++(show b)++")") $ ggTs(a,b) -- Variante mit Vertauschung ggT'(a,b) | a == 0 = b | b == 0 = a | b > a = ggT(b,a) | otherwise = ggT(a `mod` b, b) -- "a `mod` b" ist ad-hoc Infix-Schreibweise für "mod a b" -- Mit integrierter Vertauschung: ggTs (a,b) | a == 0 = b | b == 0 = a | b > a = ggT(b,a) | otherwise = ggT(b,a `mod` b) -- Erweiterter Euklidischer Algorithmus: -- ohne Ausdruck der Berechnung eggT' (a,b) | a == 0 = (b,0,1) | b == 0 = (a,1,0) | b > a = (d,t,s) where (d,s,t) = eggT'(b,a) eggT' (a,b) = (d,s,t-s*(a `div` b)) where (d,t,s) = eggT'(b,a `mod` b) -- mit Ausdruck der Berechnung eggT (a,b) | a == 0 = (b,0,1) | b == 0 = (a,1,0) | b > a = (d,t,s) where (d,s,t) = eggT(b,a) eggT (a,b) = let r@(d',s',t') = (d,s,t-s*(a `div` b)) in trace ((show d') ++ " = " ++ (show s')++"*"++(show a)++" + "++(show t')++"*"++(show b)) $ r where (d,t,s) = eggT(b,a `mod` b)
Artikelaktionen