Hogyan oldanátok meg az alábbi feladatot?

JAVÍTÁS:

Most akkor már csak lnko2 függvény megírása van hátra, vagyis két adott szám legNAGYobb közös OSZTÓjának kiszámítása.

Nem, ez a feladat nagyon is érdekes egy más szempontból.

Próbáljuk meg *funkcionális programnyelven megoldani. Úgy máris megvan a maga nem-triviális érdekessége. Íme pl. Haskell nyelven:

------------------------

-- Legnagyobb közös osztó

------------------------

-- Két számra:

gcd2 :: Integral n => n -> n -> n

gcd2 a 0 = a

gcd2 a b = gcd2 b $ a `rem` b

-- N db számra:

gcdN :: Integral n => [n] -> n

gcdN = foldr gcd2 0

-----------------------------

-- Legkisebb közös többszörös

-----------------------------

-- Két számra:

lcm2 :: Integral n => n -> n -> n

lcm2 _ 0 = 0

lcm2 0 _ = 0

lcm2 a b = (a * b) `div` gcd2 a b

-- N db számra:

lcmN :: Integral n => [n] -> n

lcmN = foldr lcm2 1

Ez így önmagában is lefut, de ha valaki, ha nem is bebizonyítva, de legalábbis hathatósan szemléltetve szeretné látni, hogy a kód helyes, az hozzáadhatja az alábbi tulajdonságteszteket:

-- Property tests:

prop_gcd2AsFromLib :: NonNegative Int -> NonNegative Int -> Bool

prop_gcd2AsFromLib (NonNegative a) (NonNegative b) = gcd2 a b == gcd a b

prop_gcdAsCommonDivisor :: NonNegative Int -> NonNegative Int -> Bool

prop_gcdAsCommonDivisor (NonNegative a) (NonNegative b) = isCommonDivisor a b $ gcd2 a b

prop_gcdAsGreaterThanAnyCommonDivisor :: NonNegative Int -> NonNegative Int -> NonNegative Int -> Property

prop_gcdAsGreaterThanAnyCommonDivisor (NonNegative a) (NonNegative b) (NonNegative d) = isCommonDivisor a b d ==> d `divides` gcd2 a b

prop_gcdAsCommonDivisorN :: [NonNegative Int] -> Bool

prop_gcdAsCommonDivisorN ns' = let ns = getNonNegative <$> ns' in isCommonDivisorN ns (gcdN ns)

prop_gcdAsGreaterThanAnyCommonDivisorN :: [NonNegative Int] -> NonNegative Int -> Property

prop_gcdAsGreaterThanAnyCommonDivisorN ns' (NonNegative d) = let ns = getNonNegative <$> ns' in isCommonDivisorN ns d ==> d `divides` gcdN ns

-- Tuajdonságtesztek segédfüggvényei:

isCommonDivisor :: Int -> Int -> Int -> Bool

isCommonDivisor a b d = d `divides` a && d `divides` b

isCommonDivisorN :: [Int] -> Int -> Bool

isCommonDivisorN ns d = all (d `divides`) ns

divides :: Integral n => n -> n -> Bool

divides _ 0 = True

divides 0 n = False

divides d n = n `rem` d == 0

Ezek az alábbi matematikai tulajdonságokat ellenőrzik le, rendre 100-100 véletlenszerűen generált mintára:

- a legnagyobb közös osztó tényleg közös osztó: osztója az összes megadott számnak

- a legnagyobb közös osztó tényleg ,,legnagyobb'': az összes létező közös osztónál ,,nagyobb'', pontosobban szólva mindegyiknek a többszöröse.

Az automata, véletlenszerűen generált tesztmintákhoz dologhoz csak a QuickCheck könyvtárat kell betölteni:

import Test.QuickCheck