GCF/LCM в Haskell

Мен Haskell үшін өте жаңа.

Хаскеллде GCF немесе LCM (ең аз жалпы көпше) табудың қарапайым жолы бар ма?

5

4 жауаптар

GCF бойынша сіз ең үлкен ортақ фактор немесе ең көп таралған дивизор дегенді білдіресіз бе? Бұл gcd , lcm сияқты ең алдымен, ең қарапайым көпше болуы мүмкін.

12
қосылды

Мен LCF дегеніміз не екенін білмеймін, бірақ GCF - Хаскеллдің сүйіктісі. Евклид алгоритмін пайдалану арқылы Сіз Хаскеллдің қалай жұмыс істейтінін біле аласыз. http://en.wikipedia.org/wiki/Euclidean_algorithm Үлкен түсініктеме алгоритм осында орнатылған http://en.literateprograms.org/Euclidean_algorithm_(Haskell) .

Рекурсияның бұл түрі Хаскеллде жиі кездеседі және ол тілдің мағыналы екенін көрсетеді.

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

Бұл кез келген санның ең үлкен жалпы коэффициентін айту үшін аргументтерде үлгі сәйкестігін қолданады және 0 - бірінші сан. Егер сандар нөлге тең болмаса, онда екінші және бірінші режимнің ең үлкен жалпы коэффициентін іздеңіз. Ақыр соңында бұл екінші дәлелде 0 болады. Бұл бірінші үлгісін іске қосып, жауап беретін бірінші дәлелді қайтарады.

[EDIT]

Функция нақты болуы керек:

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

Бұл бұрынғы рекурсиялық қадамдардың (a mode b) бағалауын күшейтеді және үлкен термінің еске салынуына кедергі келтіреді, егер айталық, сіз GCD-ке 1243235452 және 6095689787662 болып отырсыз. Seq оның дәлелін « Әлсіз Қалыпты Қалыпты Пішін «немесе дәлелдің сыртқы деректер құрылымын бағалайды.

7
қосылды
Tbh Менің ойымша, сіз seq қосқаныңыздың түсініктемесі FP немесе Haskell-ге жаңа адамдарға көмек емес. Мысалы: әлсіз қалпақ қалыпты пішіні деген не? сыртқы деректер құрылымы деген не? Қандай? Осылай етіп қойыңыз, бұл Haskell сияқты seq жазбасаңыз, мүлдем ақымақ нәрсе жасайды. Неге ештеңе жоқ where бар?
қосылды автор Zelphir, көзі
Мүлдем. ОС Хаскелл үшін жаңа болғанымен, мұны білетін кез келген уақыт.
қосылды автор Erik Hinton, көзі
ОП бұл біледі, бірақ lcm a b = let g = gcd a b in (div a g) * b
қосылды автор Sumudu Fernando, көзі
Мүмкін, мұнда seq қосыңыз.
қосылды автор alternative, көзі
seq қажет емес, өйткені b 0-ге тең болғанын білу үшін бағаланған.
қосылды автор Mike Spivey, көзі

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
қосылды

Немесе сіз жасай аласыз

euclid(n,m) =
  if n == m then n
  else if n < m then euclid(n, m-n)
    else euclid(n-m, m)
0
қосылды