Haskell : Fonction PGCD

Correction :

pgcd :: Int -> Int -> Int
pgcd a b
| b == 0 = a
| otherwise = pgcd b (a `mod` b)

Explications :

La fonction pgcd prend en entrée deux entiers positifs (a et b) et retourne leur PGCD.

Dans cette implémentation, on utilise la notation des motifs pour déterminer le cas de base de la récursivité : lorsque le deuxième paramètre b est égal à zéro, le PGCD est égal au premier paramètre a. Sinon, on applique la récursivité en appelant la fonction pgcd avec b comme premier paramètre et le reste de la division euclidienne de a par b comme deuxième paramètre (a mod b).

Le modulo (mod) est l'opération qui renvoie le reste de la division euclidienne de a par b. Ainsi, a mod b est égal à zéro si a est divisible par b et non zéro sinon.

Ainsi, la fonction pgcd retourne le PGCD des deux entiers a et b.

Notez que cette implémentation est efficace et utilise la récursivité pour trouver le PGCD en un temps logarithmique par rapport aux valeurs des entrées. De plus, elle gère les cas où l'un des deux entiers est égal à zéro, où les deux entiers sont égaux, ou où l'un des deux entiers est négatif en renvoyant un PGCD absolu.

Autre Solution :

Voici une autre façon d'implémenter la fonction pgcd en Haskell en utilisant une fonction récursive qui calcule toutes les diviseurs communs de a et b :

pgcd :: Int -> Int -> Int
pgcd a b = maximum $ diviseursCommuns a b
    where
        diviseursCommuns x y
            | x == 0 || y == 0 = [ ]
            | x == y = [x]
            | x > y = diviseursCommuns (x - y) y
            | otherwise = diviseursCommuns x (y - x)

Explications :

La fonction pgcd prend en entrée deux entiers positifs (a et b) et retourne leur PGCD.

Dans cette implémentation, on utilise une fonction récursive diviseursCommuns qui calcule tous les diviseurs communs de a et b.

La fonction récursive utilise une série de tests pour traiter les différents cas :

Si x ou y est nul, il n'y a pas de diviseurs communs et la fonction retourne une liste vide.

Si x et y sont égaux, ils sont eux-mêmes des diviseurs communs et la fonction retourne une liste contenant uniquement x.

Si x est supérieur à y, on soustrait y de x et on répète l'appel récursif avec les nouveaux arguments x - y et y.

Si x est inférieur à y, on soustrait x de y et on répète l'appel récursif avec les nouveaux arguments x et y - x.

La valeur renvoyée par la fonction diviseursCommuns est une liste contenant tous les diviseurs communs de a et b. Le PGCD est le plus grand diviseur commun de cette liste, obtenu en appliquant la fonction maximum.

Cette implémentation est également efficace et gère les mêmes cas que les précédentes implémentations. Elle peut sembler plus facile à comprendre pour certains débutants car elle utilise une fonction récursive explicite pour calculer tous les diviseurs communs.

Si vous avez trouvé les exercices corrigés en Haskell de JoëlYk intéressants et utiles, pourquoi ne pas les partager avec d'autres personnes qui pourraient également en bénéficier ? Partagez ce lien sur les réseaux sociaux ou envoyez-le à vos amis et collègues. Vous pourriez aider quelqu'un à améliorer ses compétences en programmation ou à trouver des solutions à des problèmes complexes. N'oubliez pas que la connaissance doit être partagée pour grandir. Merci pour votre soutien et votre partage !

Contact WhatsApp : +237 658395978 | Réaliser Par Joël_Yk