Cours d’algorithmique by Ph. RIS est mis à disposition selon les termes de la licence Creative Commons Paternité – Pas d’Utilisation Commerciale – Pas de Modification 3.0 Unported. IV. Les itérations
Une itération est une boucle qui permet de répéter une ou plusieurs actions tant qu’une condition n’est pas réalisée (i.e. tant que l’on a pas assez d’eau dans la cafetière, remettre une dose d’eau). Il existe trois façons d’écrire une telle répétition :
FOR valeur_de_départ TO valeur_finale DO action
WHILE condition DO BEGIN action END
REPEAT action UNTIL condition
La boucle FOR est utilisée dans le cas où l’on connaît parfaitement la valeur d’arrivée et de départ de l’indice de boucle et lorsque cet indice est incrémenté de la même valeur à chaque étape (+1).
La boucle WHILE sert dans les cas où l’on ne sait pas exactement le nombre d’itération de la boucle ou encore le pas est variable.
La boucle REPEAT UNTIL est semblable à la boucle WHILE à la différence près que le REPEAT est effectué au moins une fois car le test est fait en fin de boucle.
IV.1. Exemples
* Saisir une lettre tant que ce n’est pas une majuscule.
Program exemple1 ;
Uses crt ;
var c : char ;
begin
write (‘Frapper une majuscule : ‘) Readln(c) ;
while (cwrite (‘Frapper une majuscule : ‘) ; Readln(c) ;
end ;
end.
* Saisir une lettre tant que ce n’est pas une majuscule.
Program exemple2 ;
Uses crt ;
var c : char ;
begin
c := ‘a’ ;
repeat
write (‘Frapper une majuscule : ‘) Readln(c) ;
until (c
end.
* Afficher les 10 premiers chiffres positifs.
Program exemple3 ;
Uses crt ;
var c, i : integer ;
begin
c := 1 ;
For i:=0 to 10 do
begin
write (c,’ ‘) ; c := c+1 :
end ;
end.
IV.2. Exercices
IV.2.b. Exercice 1
On rappelle que factorielle n=1*2*3…*n.
Écrire un programme qui demande un entier entre 0 et 10 et qui calcule la factorielle de ce nombre. Écrire ce programme avec un for, un while et un repeat.
IV.2.b. Exercice 2 : l’escargot et la laitue
Un escargot grimpe sur un mur le jour pour atteindre une laitue que se trouve en haut et dort la nuit. Ce mur fait 2 m de haut et il part du bas. Lorsqu’il grimpe, l’escargot le fait de 25 cm par jour. Lorsqu’il dort, il redescend de 5 cm. Écrire un programme qui donne le nombre de jours qu’il faut à l’escargot pour arriver en haut du mur.
IV.2.c. Exercice 3
Récrire le programme ci-dessus en demandant les différents paramètres à l’utilisateur. Au bout de 50 jours, l’escargot est mort s’il n’est pas arrivé en haut du mur. inclure un test qui arrête le programme dans ce cas.
IV.2.d. Exercice 4
On considère l’équation logistique définie par yn+1 = r*yn (1 – yn). Écrire un programme qui demande à l’utilisateur de donner une valeur de r quelconque et une valeur y0 comprise entre 0,0 et 0,1 ainsi qu’un nombre nb d’itérations.
Afficher la valeur des nb premières valeurs de cette équation.
Après avoir affiché ces valeurs, donner la plus grande et la plus petite valeur des nombres que l’on vient de calculer.
Afficher également la moyenne de tous ceux-ci.
IV.2.e. Exercice 5 (nombre premier)
Un entier est premier s’il n’est divisible par aucun entier plus grand que 1 (ou encore si Premier / Entier = n alors n*Entier Premier pour tout Entier1).
Demander à l’utilisateur d’indiquer combien il veut tester de nombres entiers.
Dans une boucle qui génère les n premiers entiers, écrire une autre boucle qui teste si l’entier courant est divisible par un entier plus petit. Si ce n’est pas le cas, alors afficher cet entier car il est premier.
IV.2.f. Exercice 6 (nombre magique)
La fonction randomize initialise le générateur interne de nombres aléatoires avec une valeur aléatoire. La fonction random(limite) renvoie un nombre aléatoire entre 0 et limite.
Écrire un programme qui demande la limite à l’utilisateur, qui génère aléatoirement un nombre dans cette limite et qui demande à l’utilisateur de découvrir ce nombre en lui indiquant « plus grand » ou « plus petit » lorsqu’il se trompe.
Écrire le programme inverse qui demande à l’utilisateur d’entrer un nombre dans une limite fixée et qui cherche à découvrir ce nombre par la même méthode et affiche le nombre de coups joués.
IV.2.g. Exercice 7
Écrire un programme qui affiche :
1 -> 1
2 -> 2 1
3 -> 3 2 1
…
n -> n (n-1) … 2 1
Où n est donné par l’utilisateur.
IV.2.h. Exercice 8
Ecrire un programme qui affiche :
1 -> 0
2 -> 2 0
3 -> 2 0
4 -> 4 0 2
…
2*n -> (2*n) (2*n-2) … 2 0
où n est donné par l’utilisateur.
IV.2.i. Exercice 9
On veut concevoir un jeu basé sur le principe du « pile ou face ». Il se joue à deux : un humain et un ordinateur. Au début de la partie, chaque joueur possède 10 points de capital. La somme des capitaux reste toujours égale à 20 points. La partie se termine lorsque l’un des deux capitaux devient négatif.
Chaque étape du jeu se déroule de la manière suivante :
- L’ordinateur « jette une pièce de monnaie », c’est-à-dire qu’il tire au hasard l’un des deux caractères ‘p’ et ‘f’ avec une probabilité de 1/2 pour chacun.
- Il demande à l’humain de deviner son choix.
- L’ordinateur adopte alors l’une des deux attitudes suivantes :
Il avoue à l’humain que sa réponse est exacte et lui donne un point.
Il annonce à l’humain que sa réponse est fausse, – mais il peut bluffer (avec une probabilité de 1/3). L’humain a donc la possibilité de contrôler l’affirmation de l’ordinateur. S’il ne contrôle pas, l’ordinateur lui prend un point. S’il contrôle, deux nouveaux cas sont à envisager : soit l’ordinateur avait bluffé et, démasqué, doit donner deux points à l’humain ; soit l’ordinateur était sincère et l’humain doit lui donner deux points à titre de réparation du préjudice moral.
- Les capitaux sont affichés.
- Et ainsi de suite jusqu’à la fin…
On demande d’écrire un programme commenté. Il est recommandé de distinguer les variables par leur première lettre selon qu’elles concernent le joueur Humain ou le joueur Ordinateur (ex : OCapital).
Exemple d’exécution :
Ai-je choisi pile, ou face (p/f) ? p
… C’est faux! … Contrôlez-vous (o/n) ? o
… J’avais bluffé! … Je vous donne deux points.
… Il vous en reste 12… J’en ai 8.
Ai-je chosi pile, ou face (p/f) ? f
… C’est faux ! … Contrôlez-vous (o/n) ? n
… C’est plus prudent… Je vous prends donc un point…
… Il vous en reste 11… J’en ai 9.
Ai-je choisi pile, ou face (p/f) ? f
… C’est faux ! … Contrôlez-vous (o/n) ? o
… J’étais sincère… Je vous prends deux points.
… Il vous en reste 9… J’en ai 11.
Ai-je choisi pile, ou face (p/f) ? f
… Vous avez raison… Je vous donne un point.
… Il vous en reste 10… J’en ai 10.
… J’étais sincère… Je vous prends deux points.
… Il vous en reste -2… J’en ai 22.
J’ai gagné !
