Introduction à la programmation : Plus d’applications en Racket

Ce chapitre est entièrement consacré à la pratique. Nous coderons plusieurs problèmes en Racket. Ces problèmes sont de diverses natures : problèmes en Arithmétique, des jeux, des cas concrets de la vie active… Les deux premiers problèmes sont ceux que je vous ai laissés en exercice aux chapitres précédents : l’algorithme complet de l’élévation à la puissance et l’algorithme d’Euclide pour la détermination du pgcd de deux nombres. J’espère que vous avez pris le temps de coder ces algorithmes par vous-mêmes. Si vous ne l’avez pas encore fait, je vous invite à le faire avant de regarder les solutions que je propose. C’est seulement comme ça que vous deviendrez de bons codeurs. 😉

J’en ai dit assez, alors commençons !

L’élévation à la puissance revisitée

Voici le code minimal que nous avions obtenu au chapitre précédent :

> (define (puissance base exposant) 
    (let rec-puiss ([b base] [e exposant] [acc 1]) 
      (if (zero? e) 
          acc
          (rec-puiss b (- e 1) (* acc base)))))

Ce qui manque dans cet algorithme, c’est la prise en compte du cas où l’exposant est pair à chaque appel de la fonction rec-puiss. En effet, cette prise en compte n’est pas fondamentale à l’élévation à la puissance, c’est juste une technique pour accélérer le processus, puisque nous savons que :

$$2^{18} = 2^{2 \times 9} = (2^2)^9 = 4^9$$

Je vous invite à revoir le cours sur l’élévation à la puissance si l’exemple précédent vous semble obscur.

En effet, nous avons dit qu’à chaque fois que l’exposant se trouve pair, il faut le diviser par 2 et élever la base au carré, ce qui revient à la multiplier par elle-même. Voici une version prenant en compte ce cas :

> (define (puissance base exposant) 
    (let rec-puiss ([b base] [e exposant] [acc 1]) 
      (cond [(zero? e) acc] 
            [(even? e) (rec-puiss (* b b) (/ e 2) acc)]
            [else (rec-puiss b (- e 1) (* acc b))])))

La nouvelle clause est indiquée en gras. Notez que dans ce code, nous avons deux clauses récursives, les deux dernières. Je vous laisse vérifier que ce code donne des résultats corrects avec les mêmes arguments que ceux du chapitre précédent et avec de nouveaux arguments.

La principale différence entre les deux algorithmes se situent au niveau de la rapidité : le second est plus rapide que le premier. Pour s’en apercevoir, il faut exécuter chacun d’eux avec des arguments très grands et mesurer le temps de calcul. On y arrive en utilisant l’opérateur time de Racket. Dans les exemples qui suivent, pour faire la différence entre les deux algorithmes, appelons le premier puissance-1 et le second puissance-2.

> (time (puissance-1 2 100))
\(=>\) cpu time: 0 real time: 0 gc time: 0

> (time (puissance-2 2 100))
\(=>\) cpu time: 0 real time: 0 gc time: 0

> (time (puissance-1 2 1000))
\(=>\) cpu time: 7 real time: 6 gc time: 5

> (time (puissance-2 2 1000))
\(=>\) cpu time: 0 real time: 1 gc time: 0

J’ai volontairement remplacé la valeur de la puissance par trois points de suspension car c’est très long pour les grands exposants et ça ne nous intéresse pas. Ce sont les informations retournées par time qui nous importe. Le premier indicateur, cpu time, est le temps de calcul du processeur, le second, real time, est le temps réel, et le dernier, gc time, est le temps nécessaire pour nettoyer les variables inutiles. Ce dernier indicateur ne nous intéresse pas, ce sont les deux premiers qui ont du sens pour nous.

Comme vous pouvez le voir, dans le premier exemple, il n’y a pas de différence entre les temps de calcul des deux codes : tout est apparemment nul. Mais, après avoir augmenter l’exposant d’une octave de 10, les indicateurs ont dramatiquement changé. On voit maintenant que le premier code prend plus de temps cpu (7) et de temps réel (6) que le second code (0 et 1, respectivement). Cela prouve bien que le second algorithme est bien plus efficient que le premier.

Détermination du pgcd de deux entiers : Algorithme d’Euclide

Voici une définition récursive de la détermination du pgcd de deux nombres entiers dont le premier est le dividende et le second le diviseur : si le diviseur divise entièrement le dividende alors il est le pgcd recherché sinon le pgcd recherché est le pgcd de deux nombres dont le dividende est le précédent diviseur et le diviseur est le reste de la précédente division.

Racket nous offre déjà un opérateur pour déterminer le reste de la division de deux nombres, c’est l’opérateur remainder. Mais, c’est un bon exercice d’écrire le nôtre, nous l’appellerons rem. Voici donc une définition récursive de cette opération : Le reste de la division de deux nombres entiers est le dividende si celui-ci est inférieur au diviseur, ou le reste de la division de deux nombres dont le dividende est la différence du dividende précédent et du diviseur, et dont le diviseur est le diviseur précédent. Il est évident que si les deux nombres sont égaux, alors le reste est nul ; on ajoutera donc cette condition comme cas particulier. Nous avons donc le code suivant :

> (define (rem n p)
    (cond [(= n p) 0]
          [(< n p) n]
          [else (rem (- n p) p)]))

Et voici quelques applications de ce code :

> (rem 3 2)
\(=>\) 1
> (rem 3 3)
\(=>\) 0
> (rem 4 2)
\(=>\) 0
> (rem 15 4)
\(=>\) 3

Voici maintenant le code du pgcd :

> (define (pgcd n p)
    (cond [(< n p) (pgcd p n)]
          [(zero? (rem n p)) p]
          [else (pgcd p (rem n p))]))

La première clause sert juste à garantir que le premier argument est plus grand que le second. Alors, voici des exemples d’utilisation :

> (pgcd 26 15)
\(=>\) 1
> (pgcd 96 36)
\(=>\) 12
> (pgcd 306 758)
\(=>\) 2
> (pgcd 12 1236)
\(=>\) 12
> (pgcd 546 23)
\(=>\) 1
> (pgcd 15489 156)
\(=>\) 3

La suite de Fibonacci

Wikipédia définit la suite de Fibonacci comme étant une suite d’entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Nous n’entrerons dans les détails sur l’origine et les applications de cette suite en Arithmétique. Ce qui nous importe ici c’est que la suite est définie récursivement et donc nous pouvons écrire son code assez aisément.

Voici les quelques nombres de la suite de Fibonacci :

0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

Remarquez bien que cette suite est conforme à la définition. Au départ, les deux premiers nombres, 0 et 1, nous sont donnés. Si on considère que les positions sont numérotées en commençant par 0, notons par F(0) et F(1) ces deux nombres. Il s’en suit que nous pouvons noter F(n) le nombre qui se trouve à la position n. On détermine tous les autres comme suit :

\begin{split}
F(2) &= F(0) + F(1) = 0 + 1 = 1\\
F(3) &= F(1) + F(2) = 1 + 1 = 2\\
F(4) &= F(2) + F(3) = 1 + 2 = 3\\
F(5) &= F(3) + F(4) = 2 + 3 = 5\\
F(6) &= F(4) + F(5) = 3 + 5 = 8\\
F(7) &= F(5) + F(6) = 5 + 8 = 13\\
F(8) &= F(6) + F(7) = 8 + 13 = 21

\end{split}

Voici donc une version de la détermination de la suite de Fibonacci en Racket :

> (define (fibonacci n)
    (cond [(= n 0) 0]
          [(= n 1) 1]
          [else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))]))

Remarquez que dans ce code, nous avons deux clauses d’arrêt et la clause récursive contient deux appels à la fonction fibonacci : on dit qu’elle a deux branches récursives. La forme (- n 1) représente le nombre plus petit que le nombre n d’une unité et la forme (- n 2) représente le nombre plus petit que le nombre n de deux unités. Du reste, ce code est relativement simple.

Voici des exemples d’utilisation :

> (fibonacci 1)
\(=>\) 1
> (fibonacci 8)
\(=>\) 21
> (fibonacci 15)
\(=>\) 610
> (fibonacci 23)
\(=>\) 28657

Implémentation du type rationnel

Nous avons dit dans le premier cours d’introduction à Racket que le type rationnel (rational en Racket) n’était pas un type primitif. C’est une structure de donnée, mais elle vient quand même avec Racket donc on peut l’utiliser comme type primitif. Nous ferons ici comme les concepteurs de Racket, nous implémenterons une version simplifiée mais fonctionnelle du type rational. Cet exemple est tiré du livre classique d’Harold Abelson, Gerald Jay Sussman et Julie Sussman, intitulé Structure and Interpretation of Computer Programs (2nde édition).

En général, une structure de donnée opère sur un ensemble de données, qu’on appelle son domaine de définition, en utilisant des opérateurs. Ces opérateurs sont de trois principaux genres :

  • Les constructeurs : permettent de construire une donnée conforme à la représentation d’une donnée du type de la structure de donnée.
  • Les sélecteurs : permettent de sélectionner diverses parties d’une donnée.
  • Les opérations : permettent d’effectuer des opérations élémentaires sur les données.

Rappelons qu’un rationnel est un nombre fractionnaire (ou une fraction). Un nombre fractionnaire n’est rien d’autre qu’un nombre composé de deux nombres (entiers ou rationnels) : un numérateur et un dénominateur (Voir cours sur les fractions). Les nombres \(\frac{1}{2}, \frac{15}{7}, \frac{111}{22212} sont des rationnels. Notez que c’est juste une manière de représenter — le numérateur au dessus du dénominateur séparés par une barre — les rationnels et qu’on aurait pu employer d’autres représentations. Le plus important, c’est qu’un rationnel est composé de deux éléments.

Le constructeur

Appelons par make-rational (make est un mot anglais qui signifie faire dans le sens de construire ou fabriquer), le constructeur des nombres rationnels. Nous coderons ce constructeur comme une fonction qui prend deux paramètres — un numérateur et un dénominateur — et retourne un nombre de type rational. Mais comment représenterons-nous les rationnels ? Le plus simple, c’est sous forme d’une paire d’éléments : une liste à deux éléments séparés par un point. En Racket, on construit une paire en faisant un cons de deux atomes.

> (define (make-rational n d)
    (cons n d))

Voici quelques exemples d’utilisation :

> (make-rational 1 3)
\(=>\) ‘(1 . 3)
> (make-rational 25 5)
\(=>\) ‘(25 . 5)

Remarquez le point entre les deux éléments de la liste. En effet, lorsque le second argument de cons n’est pas une liste (liste vide incluse), la liste est affichée en séparant les deux éléments par un point. Encore une fois, c’est juste une représentation. Le plus important, c’est que nous avons bien les deux éléments qui composent un rationnel. Notez aussi qu’en Racket, aussi étrange que ça puisse paraître, une paire n’est pas une liste. En voici la preuve :

> (list? ‘(1 . 3))
\(=>\) #f
> (list? ‘(1 3))
\(=>\) #t

Le code de make-rational fonctionne correctement mais ne nous permet pas de représenter la fraction sous sa forme irréductible (second exemple). Vous rappelez-vous ce que ça signifie ? Une fraction est irréductible lorsque le numérateur et le dénominateur n’ont aucun facteur en commun.
Considérons que le numérateur et le dénominateur passés en argument de make-rational ont un ou plusieurs facteurs en commun. Comment donc trouver ce facteur (ou ces facteurs) et le(s) supprimer ? Remarquez que si deux nombres ont des facteurs en commun, le produit de ces facteurs est est commun à ces deux nombres. Et vous savez quoi ? Ce produit est le plus grand des facteurs de chacun de ces nombres : c’est donc leur pgcd. Du coup, il nous suffit de trouver le pgcd du numérateur et du dénominateur et de diviser chacun d’eux par celui-ci et bingo !

Voici donc la nouvelle version de make-rational :

> (define (make-rational n d)
    (let ((g (pgcd n d)))
    (cons (/ n g) (/ d g))))

Nous avons maintenant :

> (make-rational 60 21)
\(=>\) ‘(20 . 7)
> (make-rational 25 5)
\(=>\) ‘(5 . 1)

Les sélecteurs

Nous avons besoin d’opérateurs qui, pour un rationnel donné, nous permettent de sélectionner son numérateur et son dénominateur. Appelons ces opérateurs numer et denom, respectivement.

Puisque nous avons représenté les rationnels sous forme de liste à deux éléments, pour récupérer le numérateur, il suffit de faire un CAR et pour récupérer le dénominateur, de faire un CDR.

> (define (numer x)
    (car x))
> (define (denom x)
    (cdr x))

Et voilà ! simple comme bonjour ! 😆

Voici quelques exemples :

> (numer ‘(20 . 7))
\(=>\) 20
> (denom (cons 12 33))
\(=>\) 33

Les opérations élémentaires de l’arithmétique

Je rappelle ci-dessous les opérations élémentaires sur les rationnels :

\begin{split}
\frac{n_1}{d_1} + \frac{n_2}{d_2} &= \frac{n_1 \times d_2 + n_2 \times d_1}{d_1 \times d_2} \\
\frac{n_1}{d_1} – \frac{n_2}{d_2} &= \frac{n_1 \times d_2 – n_2 \times d_1}{d_1 \times d_2} \\
\frac{n_1}{d_1} \times \frac{n_2}{d_2} &= \frac{n_1 \times n_2}{d_1 \times d_2} \\
\frac{n_1/d_1}{n_2/d_2} &= \frac{n_1}{d_1} \times \frac{d_2}{n_2} = \frac{n_1 \times d_2}{d_1 \times n_2} \\
\end{split}

On peut coder ces opérations comme suit :

> (define (add-rat x y)   ; L'addition
    (make-rational (+ (* (numer x) (denom y)) (* (numer y) (denom x)))
                   (* (denom x) (denom y))))
> (define (sub-rat x y)   ; La soustraction
    (make-rational (- (* (numer x) (denom y)) (* (numer y) (denom x)))
                   (* (denom x) (denom y))))
> (define (mult-rat x y)   ; La multiplication
    (make-rational (* (numer x) (numer y))
                   (* (denom x) (denom y))))
> (define (div-rat x y)   ; La division
    (make-rational (* (numer x) (denom y))
                   (* (denom x) (numer y))))

Dans ces implémentations, j’utilise make-rational pour m’assurer que le résultat est également un nombre rationnel, et que ce rationnel est sous sa forme irréductible. Voici donc des exemples d’utilisations de ces opérateurs :

> (add-rat (cons 1 2) (cons 3 4))       ; \(1/2 + 3/4\)
\(=>\) ‘(5 . 4)
> (sub-rat ‘(7 . 4) (cons 3 4))             ; \(7/4 – 3/4\)
\(=>\) ‘(1 . 1)
> (mult-rat ‘(10 . 3) ‘(6 . 28))             ; \(10/3 \times 6/28\)
\(=>\) ‘(5 . 7)
> (div-rat ‘(2 . 5) ‘(2 . 3))                   ; \(2/5 \div 2/3\)
\(=>\) ‘(3 . 5)
> (add-rat ‘(1 . 2) (div-rat ‘(2 . 5) ‘(2 . 3)))       ; \(1/2 + 2/5 \div 2/3\)
\(=>\) ‘(11 . 10)

Le dernier exemple montre que nous pouvons aisément combiner les opérations.

Affichage des rationnels

La représentation interne des rationnels sous forme de pairs est excellente car elle nous permet de manipuler ces nombres de manière abstraite. Mais convenez avec moi qu’il serait préférable d’afficher les résultats sous une forme qui approche la représentation mathématique. Ainsi, la fraction ‘(n . d) serait affichée comme \(n/d\). On doit donc coder notre propre fonction printf qui ferait ce travail. Voici comment on pourrait coder cette fonction qu’on appelle print-rat :

> (define (print-rat x)
    (printf "~%~a/~a" (numer x) (denom x)))

Ce code devrait vous être familier mais il convient que j’explique la chaîne de formatage “~%~a/~a”. En effet, la séquence ~% exprime l’intention d’ajouter une ligne vide, la séquence ~a est connue de vous, elle exprime que la première variable — (numer x) — après la chaîne de formatage doit être affichée telle quelle. Le symbole / est le symbole de la division et la dernière séquence ~a exprime que la seconde variable — (denom x) — après la chaîne de formatage doit être affichée telle quelle. Ainsi, si nous entrons (print-rat ‘(1 . 2)) dans le REPL, il affichera d’abord une ligne vierge, ensuite sur la même ligne (numer ‘(1 . 2)) qui est 1, suivi du symbole / suivi de (denom ‘(1 . 2)) qui est 2. Il affichera donc sur cette dernière ligne : 1/2. Ce qui est le résultat que nous espérions.

> (print-rat (cons 1 2)
\(=>\)
1/2
> (print-rat (add ‘(7 . 4) (cons 3 4)))
\(=>\)
5/2

Dans le second exemple, le REPL fait d’abord l’addition des deux fractions et il affiche le résultat. Rien de sorcier !

Le jeu “Devine mon nombre”

Ce jeu est un classique des livres de programmation. Le cas présent est tiré du livre de Matthias Felleisen et al., intitulé Realm of Racket. Le principe du jeu est le suivant : deux joueurs s’affrontent dont le premier choisit un nombre entier quelconque compris entre deux nombres, sans le dévoiler, et le second doit deviner ce nombre. Si le second joueur choisit un nombre plus petit que celui qu’il doit deviner, le premier joueur lui dit “Plus grand”. Sinon si le second joueur choisit un nombre plus grand que celui qu’il doit deviner, le premier joueur lui dit “Plus petit”. Le jeu continue ainsi jusqu’à ce que le second joueur trouve le bon résultat, et le jeu prend fin.

Par exemple, disons que le premier joueur doit choisir un nombre entre 1 et 100 et qu’il choisit 23. Appelons plage l’ensemble de nombre compris entre 1 et 100, appelons minimum le nombre le plus petit de cette plage, donc 1, maximum le plus grand, donc 100, objectif le nombre qu’il doit deviner et choix le nombre qu’il vient de choisir. Le second joueur doit donc deviner ce nombre par plusieurs tentatives. En combien de coups arriverait-il à la bonne réponse ? À première vue, puisqu’il y a exactement cent nombres entiers entre 1 et 100 et que chaque nombre a la même chance d’être choisi par le premier joueur, au pire des cas, il faudrait 100 coups pour arriver à la bonne réponse. Mais c’est vraiment le pire des cas car si vous êtes très chanceux, vous pouvez trouver le résultat au premier coup ou au second coup, etc.

Cependant, il existe une technique pour aller très vite et cette technique est basée sur la technique diviser pour mieux régner. Cette technique s’appelle la recherche binaire. Voici en quoi elle consiste : on choisit le nombre qui est juste au milieu de la plage — qui s’obtient en additionnant le minimum et le maximum et en divisant la somme par 2. Si le premier joueur crie “Plus grand”, on sait immédiatement que l’objectif ne se trouve pas entre le minimum et le choix, il se trouve entre le choix et le maximum. Donc convenez avec moi que la nouvelle plage est constituée des nombres entiers compris entre le choix précédent et le maximum. Mais, le choix n’est pas compris dans la plage puisque nous savons qu’il n’est pas l’objectif. Dans ce cas, le minimum est maintenant le choix précédent plus une unité. Si en revanche, le premier joueur crie “Plus petit”, on sait immédiatement que l’objectif ne se trouve pas entre le choix et le maximum mais qu’il se trouve entre le minimum et le choix (le choix n’étant pas inclus). La nouvelle plage est alors constituée des nombres entiers compris entre le minimum et le choix précédent. Et donc, le nouveau maximum est le choix précédent moins une unité. Remarquez-vous que nous venons de réduire drastiquement le problème ? Bien. On continue de cette manière jusqu’à atteindre l’objectif et on l’atteint très rapidement. Voyons pourquoi.

Revenons à l’exemple précédent : le minimum initial est 1, le maximum initial est 100 et le premier joueur a choisi 23 qui est l’objectif.

  • Premier choix = \((1 + 100) \div 2 = 50\). Le premier joueur crie donc “Plus petit”. On a donc maintenant minimum = 1, maximum = \(50 – 1 = 49\).
  • Deuxième choix = \((1 + 49) \div 2 = 25\). Le premier joueur crie encore “Plus petit”. On a donc maintenant minimum = 1, maximum = \(24 – 1 = 23\).
  • Troisième choix = \((1 + 23) \div 2 = 12\). Le premier joueur crie “Plus grand”. On a donc maintenant minimum = \(12 + 1 = 13\), maximum = 23.
  • Quatrième choix = \((13 + 23) \div 2 = 18\). Le premier joueur crie “Plus grand”. On a donc maintenant minimum = \(18 + 1 = 19\), maximum = 23.
  • Cinquième choix = \((19 + 23) \div 2 = 21\). Le premier joueur crie “Plus grand”. On a donc maintenant minimum = \(21 + 1 = 22\), maximum = 23.
  • Sixième choix = \((22 + 23) \div 2 = 22\). Le premier joueur crie “Plus grand”. On a donc maintenant minimum = \(22 + 1 = 23\), maximum = 23.
  • À ce stade, nous sommes assurés que le nombre recherché est 23.

Remarquez qu’il a fallu juste 7 choix plutôt que 100 choix. N’est-ce pas incroyable ! 😆

Voici maintenant comment coder ce jeu :

> (define (guess-my-number n m)
    (cond [(> n m) (guess-my-number m n)]
          [else
            (define choix (quotient (+ n m) 2))
            (printf "~%Mon choix: ~a" choix)
            (printf "~%1: egal\n2: plus petit\n3: plus grand ?\n")
            (define rep (read))
            (cond [(= rep 1) (printf "Bravo !")]
                  [(= rep 2) (guess-my-number n (- choix 1))]
                  [(= rep 3) (guess-my-number (+ choix 1) m)]
                  [else (error "Reponse inconnue")])]))

Ce code est un peu long parce que j’ai ajouté des formes pour le rendre plus interactif. Sinon il n’a rien de surprenant pour le niveau que nous avons actuellement. En effet, la première expression conditionnelle cond a pour but de faire en sorte que le premier argument (le minimum) de guess-my-number soit plus petit que le second argument (le maximum). Dès que nous nous avons réglé ce point, on passe dans la partie importante. D’abord on définit la variable choix qui constitue le choix que nous faisons à chaque itération. Ensuite, on affiche la valeur de ce choix afin que l’adversaire décide si nous avons atteint l’objectif ou pas. On lui affiche pour cela trois réponses possibles numérotées de 1 à 3. Il n’a qu’à entrer le chiffre correspondant à la réponse, qui est lu par l’opération (read) et stocké dans la variable rep. Enfin, avec la valeur de la réponse, l’expression conditionnelle évalue la clause vraie. Le reste n’est que routine. Notez juste qu’on appelle de nouveau guess-my-number dans deux clauses alors le programme est récursif.

Il convient que j’explique comment l’opérateur read se comporte dans DrRacket. Lorsqu’on fait (read) dans le REPL, une zone d’édition nous est retournée attendant qu’on y entre quelque chose et qu’on appuie Entrée à la fin. Notre saisie est alors lue et traitée par le REPL. Voici une image de ce à quoi ressemble cette zone de saisie :

Zone d'édition retournée par le REPL lors de l'évaluation de (read)

Appliquons ce code à notre exemple précédent :

> (guess-my-number 100 1)\(=>\) Mon choix: 50
1: egal
2: plus petit
3: plus grand ?
2Mon choix: 25
1: egal
2: plus petit
3: plus grand ?
2Mon choix: 12
1: egal
2: plus petit
3: plus grand ?
3Mon choix: 18
1: egal
2: plus petit
3: plus grand ?
3

Mon choix: 21
1: egal
2: plus petit
3: plus grand ?
3

Mon choix: 23
1: egal
2: plus petit
3: plus grand ?
1
Bravo !

On voit bien les différentes étapes du jeu et les différentes valeurs du choix jusqu’à l’objectif. En effet, lorsque vous jouez, vous êtes qui choisit le nombre à deviner et l’ordinateur est celui qui doit deviner ce nombre. C’est donc qui répondez si le choix de l’ordinateur est plus petit, plus grand, ou égal à l’objectif.

Nous sommes au terme de ce chapitre passionnant et plein de pratique. Prenez le temps de reprendre les applications, de vous l’expliquer ligne par ligne et d’être certain que vous avez compris chaque ligne. À ce stade, vous connaissez les bases du langage Racket. Alors soyez fier de votre évolution.

Bon Lisping ! 😉

  •  
    14
    Shares
  • 14
  •  
  •  
  •  
  •  

Poster un Commentaire

avatar
  S’abonner  
Notifier de