Université de la Réunion Faculté des Sciences et Technologies ...

De
Publié par

  • cours - matière potentielle : des instructions
  • mémoire
Université de la Réunion Faculté des Sciences et Technologies Département de Biochimie et Biologie Moléculaire Histoire des Sciences et Bioinformatique (S33BC23) Algorithmique TD2 Le jeu du pendu Un(e) étudiant(e) décide d'écrire l'algorithme permettant de programmer le jeu du pendu. L'algorithme écrit par cet(te) étudiant(e) est présenté sur la dernière page. - Corrigez les erreurs commises par cet(te) étudiant(e).
  • jeu du pendu
  • comparaisons ⇒
  • nbalea ←
  • bloc d'instruction de la boucle
  • string variable
  • nbtrouve old
  • instruction
  • instructions
  • saisie
  • mot
  • mots
  • lettre
Publié le : mercredi 28 mars 2012
Lecture(s) : 57
Source : dbbm.univ-reunion.fr
Nombre de pages : 12
Voir plus Voir moins

Université de la Réunion
Faculté des Sciences et Technologies
Département de Biochimie et Biologie
Moléculaire

Histoire des Sciences et Bioinformatique
(S33BC23)
Algorithmique

TD2


Le jeu du pendu

Un(e) étudiant(e) décide d’écrire l’algorithme permettant de programmer le
jeu du pendu. L’algorithme écrit par cet(te) étudiant(e) est présenté sur la
dernière page.

- Corrigez les erreurs commises par cet(te) étudiant(e).

- Quel sera le résultat de l’algorithme sachant que la fonction Alea() a
-19renvoyé la valeur 1,6.10 et que l’utilisateur a saisi successivement les
lettres « a », « e », « r », « s », « n », « o », « c », « j », « l », « p », « i », « d »,
« g », « v », « m », « u », « b », « i » ?
Écrivez toutes les lignes affichées à l’écran en précisant à quel moment
l’utilisateur rentre les lettres
Précisez les valeurs des variables stockant le nombre de lettres trouvées et le
nombre d’essais restants.

- Quelle instruction utiliser afin de ne pas entrer dans la boucle POUR si le
mot ne contient pas la lettre entrée par l’utilisateur ? Pourquoi l’étudiant(e) a
eu raison de ne pas rajouter cette instruction ?

- Transformez l’algorithme afin qu’il prenne son dictionnaire de mot (tableau
dico) à partir d’un fichier.
- Transformez l’algorithme afin qu’il permette de respecter les conditions de
victoire du jeu et de faire l’affichage attendu lors du jeu du pendu.

Exemple d’affichage :

Le mot à deviner est « cacahuètes ».
L’utilisateur rentre la lettre « a » :
$ _ a _ a _ _ _ _ _ _
L’utilisateur rentre la lettre « e » :
$ _ a _ a _ _ _ _ e _
L’utilisateur rentre la lettre « i » :
$ _ a _ a _ _ _ _ e _

|
|
|
|
|

L’utilisateur rentre la lettre « z » :
$ _ a _ a _ _ _ _ e _
_ _ _ _ _
|
|
|
|
|


L’affichage final si l’utilisateur ne trouve pas le mot sera :
$ _ a _ a _ _ _ _ e _
_ _ _ _ _
|/ |
| O
| -|-
| / \
|

Le mot mystère était : cacahuètes

L’affichage final si l’utilisateur ne trouve pas le mot sera :
$ c a c a h u è t e s
$ Vous avez trouvé le mot mystère. Félicitations !!! Les erreurs sont indiquées en vert et les corrections en rouge.
Le caractère # permet d’insérer des commentaires dans le code.

Tableau dico(9) en stringue # le type stringue n’existe pas ⇒ string ou
caractère ; le tableau dico va contenir 11 cases par la suite donc il faut qu’on
déclare un tableau à 11 cases ⇒ dico(10)
Variables nb-alea, nbess@i, nbtrouve, nbtrouve old en numérique # /!\ pas
de – ni de @ et encore moins d’espaces dans les noms des variables ⇒
remplacez partout par nbalea, nbessai et nbtrouveold
De plus, on utilise la variable i par la suite mais elle n’est pas définie ⇒
Variable i en numérique
Variables mot et lettre en thong # pas de et pour séparer les noms des
variables ⇒ mot, lettre ; le type thong n’existe pas non plus ⇒ string

DEBUT
dico(0) = bioinformatique ; dico(1) = biochimie ; dico(2) = bioénergétique ;
dico(3) = physique ; dico(4) = physiologie ; dico(5) = botanique ;
dico(6) = zoologie ; dico(7) = enzymologie ; dico(8) = probabilités ;
dico(9) = gène ; dico(10) = anglais # pas de signe = pour l’affectation
seulement pour les comparaisons ⇒ remplacez tous les = par des ← pour les
instructions d’affectation.
nb-alea = Entier(Alea()+9) # la fonction Alea() renvoie un nombre réel
compris entre 0 et 1. Si on souhaite pouvoir sélectionner un mot parmi
l’ensemble des mots du dictionnaire, il faut que le nombre soit compris entre
0 et 10. Pour cela, il faut multiplier la valeur retournée par Alea() par 10. Mais
attention puisque les indices du tableau doivent être des nombres entiers.
Donc on utilise la fonction Ent() – pas Entier() qui n’existe pas – afin de ne
prendre que la partie entière du nombre aléatoire généré ⇒ Ent(Alea()*10)
mot = dico[nb-alea] #En algorithmique on utilise les () pour les tableaux ⇒
dico(nbalea)

ECRIRE « Vous avez 10 essais pour deviner toutes les lettres du mot
mystère. En cas d’échec, vous perdez 1 essai jusqu’à ce qu’il ne vous en reste
plus. Si vous trouvez le mot mystère avant qu’il ne vous reste plus d’essais,
vous gagnez. Sinon vous serez pendu sur la place publique (mwouahahah).
»
nbess@i = 10
nbtrouve = 0

TANTQUE nbess@i > 0
ECRIRE « Entrez une lettre minuscule »
LIRE lettre
nbtrouve old = nbtrouve POUR i = 0 A Len(« mot ») #on souhaite parcourir l’ensemble de la chaîne
de caractère contenue dans la variable mot et pas la chaîne de caractère
« mot » ⇒ mot
SI L == Mid(mot, i, 1) #la variable L n’a pas été déclarée à l’inverse de la
variable lettre permettant de stocker la lettre saisie par l’utilisateur. De plus,
la variable i commence à 0 or la position 0 n’existe pas pour la chaîne de
caractère mot. En outre, une instruction SI doi contenir un ALORS après la
condition pour savoir quand la condition est terminée ⇒ SI lettre ==
Mid(mot, i+1, 1) ALORS
nbtrouve = nbtrouve + 1
FINSI
i = i + 1 #voir ligne suivante
FINPOUR #l’instruction FINPOUR n’existe pas !!! ⇒ remplacez par i
SUIVANT

SI nbtrouve == nbtrouve old
nbess@i = nbess@i – 1
ECRIRE « La lettre », lettre, « n’est pas dans le mot mystère. »
ECRIRE « Il vous reste », nbess@i, « essai(s). »
SINON nbtrouve == Len(« mot ») #l’instruction SINON ne doit pas contenir
de condition puisqu’elle définit tous les autres cas. Si une condition est
nécessaire il faut utiliser l’instruction SINONSI et terminer la condition par
un ALORS ; même correction que précédemment pour mot ⇒ SINONSI
nbtrouve == Len(mot) ALORS
ECRIRE « Vous avez trouvé le mot mystère. Félicitations !!! »
FINSI

SI nbess@i == 0
ECRIRE « Vous n’avez pas trouvé le mot mystère dans la limite de 10
essais. Qu’on apporte la corde !!! »
FINSI
#la boucle TANTQUE n’a pas été fermée. L’ensemble des instructions
précédentes devant se trouver dans la boucle TANTQUE, il faut fermer cette
boucle à ce niveau ⇒ FINTANTQUE
FIN

- Résultat de l’algorithme

-19Si la fonction Alea() renvoie 1,6.10 nbalea sera égal à 0 car la partie entrière
-19 -18de 1,6.10 * 9 = 1,44.10 sera 0.
La variable mot contiendra la chaîne de caractère « bioinformatique ». La taille de la variable mot sera donc 15. Donc lorsque la variable nbtrouve
sera égale à 15 l’algorithme considérera que l’utilisateur aura trouvé le mot
mystère.

$ Vous avez 10 essais pour deviner toutes les lettres du mot mystère. En cas
d’échec, vous perdez 1 essai jusqu’à ce qu’il ne vous en reste plus. Si vous
trouvez le mot mystère avant qu’il ne vous reste plus d’essais, vous gagnez.
Sinon vous serez pendu sur la place publique (mwouahahah)

$ Entrez une lettre minuscule
$ a # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 1 ; pas d’erreur donc
nbessai = 10

$ Entrez une lettre minuscule
$ e # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 2 ; pas d’erreur donc
nbessai = 10

$ Entrez une lettre minuscule
$ r # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 3 ; pas d’erreur donc
nbessai = 10

$ Entrez une lettre minuscule
$ s # lettre saisie par l’utilisateur
$ La lettre s n’est pas dans le mot mystère.
$ Il vous reste 9 essai(s)
èrenbtrouve = 3 ; 1 erreur donc nbessai = 9

$ Entrez une lettre minuscule
$ n # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 4 ; pas d’erreur donc
nbessai = 9

$ Entrez une lettre minuscule
$ o # lettre saisie par l’utilisateur
La lettre est trouvée 2 fois dans le mot donc nbtrouve = 6 ; pas d’erreur donc
nbessai = 9

$ Entrez une lettre minuscule
$ c # lettre saisie par l’utilisateur
$ La lettre c n’est pas dans le mot mystère. $ Il vous reste 8 essai(s)
èmenbtrouve = 6 ; 2 erreur donc nbessai = 8

$ Entrez une lettre minuscule
$ j # lettre saisie par l’utilisateur
$ La lettre j n’est pas dans le mot mystère.
$ Il vous reste 7 essai(s)
èmenbtrouve = 6 ; 3 erreur donc nbessai = 7

$ Entrez une lettre minuscule
$ l # lettre saisie par l’utilisateur
$ La lettre l n’est pas dans le mot mystère.
$ Il vous reste 6 essai(s)
èmenbtrouve = 6 ; 4 erreur donc nbessai = 6

$ Entrez une lettre minuscule
$ p # lettre saisie par l’utilisateur
$ La lettre p n’est pas dans le mot mystère.
$ Il vous reste 5 essai(s)
èmenbtrouve = 6 ; 5 erreur donc nbessai = 5

$ Entrez une lettre minuscule
$ i # lettre saisie par l’utilisateur
La lettre est trouvée 3 fois dans le mot donc nbtrouve = 9 ; pas d’erreur donc
nbessai = 5

$ Entrez une lettre minuscule
$ d # lettre saisie par l’utilisateur
$ La lettre d n’est pas dans le mot mystère.
$ Il vous reste 4 essai(s)
èmenbtrouve = 9 ; 6 erreur donc nbessai = 4

$ Entrez une lettre minuscule
$ g # lettre saisie par l’utilisateur
$ La lettre g n’est pas dans le mot mystère.
$ Il vous reste 3 essai(s)
èmenbtrouve = 9 ; 7 erreur donc nbessai = 3

$ Entrez une lettre minuscule
$ v # lettre saisie par l’utilisateur
$ La lettre v n’est pas dans le mot mystère.
$ Il vous reste 2 essai(s)
èmenbtrouve = 9 ; 8 erreur donc nbessai = 2
$ Entrez une lettre minuscule
$ m # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 10 ; pas d’erreur donc
nbessai = 2

$ Entrez une lettre minuscule
$ u # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 11 ; pas d’erreur donc
nbessai = 2

$ Entrez une lettre minuscule
$ b # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 12 ; pas d’erreur donc
nbessai = 2

$ Entrez une lettre minuscule
$ i # lettre saisie par l’utilisateur
La lettre est trouvée 1 fois dans le mot donc nbtrouve = 15 ; pas d’erreur donc
nbessai = 2
Or nbtrouve == Len(mot) puisque 15 == 15.

$ Vous avez trouvé le mot mystère. Félicitations !!!
Cependant l’algorithme ne s’arrête pas là puisque la valeur de la variable
nbessai n’est pas inférieure ou égale à 0. Donc, on retourne au début de la
boucle TANTQUE est l’algorithme affiche :
$ Entrez une lettre
$ # le curseur clignote pour indiquer qu’une saisie est attendue
L’utilisateur pensant avoir gagné il ne saisit plus aucune lettre.
On peut remarquer que l’algorithme n’effectue pas la tâche que l’étudiant(e)
souhaitait puisqu’il affiche « Vous avez trouvé le mot mystère.
Félicitations !!! » alors que l’utilisateur n’a pas trouvé les lettres « q » et « f »
du mot « bioinformatique ».
L’erreur de l’étudiant(e) a été de considérer que l’utilisateur se souviendrait
de toutes les lettres qu’il a saisies et qu’il ne les saisirait plus par la suite. Or,
cette erreur est préjudiciable car dans cet algorithme aucun affichage est fait
pour tenir informé l’utilisateur sur les lettres déjà trouvées, leurs positions
dans le mot entier et le nombre de lettre qu’il reste à trouver. Donc, il est
nécessaire, comme il sera fait par la suite, de modifier l’algorithme afin de
donner l’ensemble des informations nécessaires à la réalisation du jeu du
pendu.

- Condition pour entrer dans la boucle POUR

SI Trouve(mot, lettre) != 0 ALORS
POUR i ← 0 A Len(mot)
SI lettre == Mid(mot, i, 1) ALORS
nbtrouve ← nbtrouve + 1
FINSI
i SUIVANT
FINSI

La fonction Trouve(mot, lettre) renvoie la position de la lettre dans le mot ou
0 dans le cas où la lettre n’est pas dans le mot.
Donc, en mettant le bloc d’instruction de la boucle POUR au sein de cette
condition, on évite d’effectuer la boucle lorsque la lettre n’est pas dans le mot.
Cependant, la fonction Trouve(mot, lettre) est basée sur une boucle qui
parcourt l’ensemble du mot lorsque la lettre n’est pas trouvée. Donc, au final
il n’y a pas de réelle optimisation possible à ce niveau. Au contraire, on
risque de doubler le temps, lorsque la lettre saisie par l’utilisateur est dans le
mot puisqu’on va effectuer la boucle une fois avec la fonction Trouve puis
une deuxième fois avec la boucle POUR.

- Transformation pour prendre le dictionnaire à partir d’un fichier

Afin de pouvoir jouer avec plus de mots, il est plus intéressant de prendre les
mots du dictionnaire dans un fichier séparé de l’algorithme plutôt que de les
écrire directement dans l’algorithme.

Donc au lieu d’avoir les instructions :
dico(0) = bioinformatique ; dico(1) = biochimie ; dico(2) = bioénergétique ;
dico(3) = physique ; dico(4) = physiologie ; dico(5) = botanique ;
dico(6) = zoologie ; dico(7) = enzymologie ; dico(8) = probabilités ;
dico(9) = gène ; dico(10) = anglais
on va utiliser une boucle permettant de lire les lignes d’un fichier et de
stocker chaque mot dans une case d’un tableau.
À priori le nombre de lignes du fichier n’est pas connu, donc il faut utiliser
un tableau dynamique, i.e. dont la taille va varier au cours des instructions.

Admettons que le fichier contenant les mots se nomme « Dico.txt ».

Tableau dico() en string
Variable nbmot en numérique

DEBUT OUVRIR « Dico.txt » SUR 1 EN LECTURE
nbmot ← 0
TANTQUE NON EOF(1)
Redim dico(nbmot)
LIREFICHIER 1, dico(nbmot)
nbmot ← nbmot + 1
FINTANTQUE
FERMER 1

nbalea ← Ent(Alea()*(nbmot-1))

FIN

- Transformation pour obtenir l’affichage classique du jeu du pendu

Tout d’abord, il faut éviter que l’utilisateur rentre deux fois la même lettre.
Donc, il faudra penser à stocker les lettres que l’utilisateur a saisies. Puis,
comparer chaque nouvelle saisie avec les saisies précédentes. Une façon qui
permettrait de limiter le nombre de ligne de pseudo code serait d’utiliser la
fonction Trouve.

Ensuite, il faut trouver le moyen d’afficher seulement les lettres qui ont été
trouvées et mettre des _ à la place des autres lettres. Pour cela, il est
préférable de garder en mémoire soit les positions soit les lettres que
l’utilisateur a déjà trouvées.

Enfin, pour l’affichage, il serait utile de stocker chaque figure représentant un
échec supplémentaire dans un tableau de 10 cases (/!\ les indices
commencent à 0).

Voici l’algorithme final :

Tableau dico(), motrouve(), pendu(9) en string
Variables nbmot, nbalea, nbessai, nbtrouve, nbtrouveold, i en numérique
Variables mot, lettre, lettresold, affiche en string

DEBUT
OUVRIR « Dico.txt » SUR 1 EN LECTURE
nbmot ← 0
TANTQUE NON EOF(1)
Redim dico(nbmot)
LIREFICHIER 1, dico(nbmot)
nbmot ← nbmot + 1 FINTANTQUE
FERMER 1

nbalea ← Ent(Alea()*(nbmot-1))
mot ← dico(nbalea)
affiche ← «»

ECRIRE « Vous avez 10 essais pour deviner toutes les lettres du mot
mystère. En cas d’échec, vous perdez 1 essai jusqu’à ce qu’il ne vous en reste
plus. Si vous trouvez le mot mystère avant qu’il ne vous reste plus d’essais,
vous gagnez. Sinon vous serez pendu sur la place publique (mwouahahah).
»
POUR i ← 0 A Len(mot)
Redim motrouve(i)
motrouve(i) ← « _ »
affiche ← affiche & « _ » & « »
i SUIVANT
ECRIRE affiche

nbessai ← 10
nbtrouve ← 0

# le tableau pendu contient à chaque case l’affichage correspondant au
nombre d’erreurs commises par l’utilisateur
pendu(9) ← «|\n|\n|\n|\n|\n »
pendu(8) ← « _ _ _ _ _\n » & pendu(9)
pendu(7) ← « _ _ _ _ _\n » & «|/\n|\n|\n|\n|\n »
pendu(6) ← « _ _ _ _ _\n|/ |\n|\n|\n|\n|\n »
pendu(5) ← « _ _ _ _ _\n|/ |\n| O\n|\n|\n|\n »
pendu(4) ← « _ _ _ _ _\n|/ |\n| O\n| |\n|\n|\n »
pendu(3) ← « _ _ _ _ _\n|/ |\n| O\n| -|\n|\n|\n »
pendu(2) ← « _ _ _ _ _\n|/ |\n| O\n| -|-\n|\n|\n »
pendu(1) ← « _ _ _ _ _\n|/ |\n| O\n| -|-\n
/\n|\n|\n »
pendu(0) ← « _ _ _ _ _\n|/ |\n| O\n| -|-\n /\\
\n|\n|\n »

lettresold ← «»
TANTQUE nbessai > 0
ECRIRE « Entrez une lettre minuscule »
LIRE lettre
TANTQUE Trouve(lettresold, lettre) != 0
ECRIRE « Vous avez déjà saisi la lettre », lettre

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi