Haskell'de GCF/LCM

Haskell için son derece yeni.

Haskell'de GCF veya LCM'yi (En Az Ortak Çoklu) bulmak için basit bir yol var mı?

5

4 cevap

GCF tarafından, en yaygın ortak faktör mi, yoksa en büyük ortak bölen mi? Bu, lcm olduğu gibi, en az ortak çoklu olan gcd seçeneğidir.

12
katma

LCF'nin ne olduğundan emin değilim ama GCF bir Haskell favori. Öklid Algoritması'nı kullanarak gerçekten Haskell'in nasıl çalıştığını anlayabilirsiniz. http://en.wikipedia.org/wiki/Euclidean_algorithm Nasıl büyük bir açıklama var algoritma burada ayarlanır http://en.literateprograms.org/Euclidean_algorithm_(Haskell) .

Bu tür özyineleme, Haskell'de yaygındır ve dilin ne kadar etkileyici olabileceğini gösterir.

gcd a 0 = a
gcd a b = gcd b (a `mod` b)

Bu, herhangi bir sayının en büyük ortak faktörünü söylemek için argümanlarda şablon eşleştirmesi kullanır ve 0 ilk sayıdır. Sayılar her ikisi de sıfır değilse, o zaman ikincinin en büyük ortak etkeni ve ikincinin ilk modunu arayın. Sonunda bu ikinci argümanda 0'a ulaşacaktır. Bu, ilk modeli tetikleyecek ve cevap olan ilk argümana dönecektir.

[DÜZENLE]

Fonksiyon aslında olmalıdır:

gcd a 0 = a
gcd a b = b `seq` gcd b (a `mod` b) where

Bu, önceki yineleme basamağının (bir mod b) değerlendirmesini zorlar ve büyük bir parçanın belleğe inşa edilmesini önler (eğer 1243235452 ve 6095689787662 GCD'leri iseniz). Zayıf Kafa Normal Formu "veya argümanın en dış veri yapısını değerlendirir.

7
katma
Tbh, neden seq eklemenizin nedeninin gerçekten FP ya da Haskell için yeni insanlar için çok fazla bir yardım olmadığını düşünüyorum. Örneğin: Zayıf Kafa Normal Formu nedir? <İ> En fazla veri yapısı nedir? Neyin dışında? Bunun gibi, Haskell'in, seq 'i yazmazsanız, tamamen aptalca bir şey yaptığını göreceksiniz. Ve neden takip etmeyen bir nerede var?
katma yazar Zelphir, kaynak
Kesinlikle. OP, Haskell'e yeni olsa da, bunu öğrenmek için iyi bir zaman.
katma yazar Erik Hinton, kaynak
OP muhtemelen bunu biliyor, ama lcm a b = let g = gcd a b in (div a g) * b
katma yazar Sumudu Fernando, kaynak
Muhtemelen burada seq eklemeniz gerekir.
katma yazar alternative, kaynak
seq gerekli değildir, çünkü b , 0'a eşit olup olmadığını öğrenmek için değerlendirilmiştir.
katma yazar Mike Spivey, kaynak

gcd is imported in the prelude. That means that you can use it whenever you want without going anything. Erik Hinton shows a simple version of the Euclidean algorithm, if you are interested in implementing your own. One thing though: / is used only for floating point division, use div and mod to find the quotient and remainder when you want to do "integer division." The prelude also defines a lcm function for least common multiple.

3
katma

Ya da yapabilirsin

euclid(n,m) =
  if n == m then n
  else if n < m then euclid(n, m-n)
    else euclid(n-m, m)
0
katma