lesson des boucle et exersise

Les Boucles
« Les premiers 90% du code prennent les premiers 90% du temps de développement. Les 10% restants prennent les autres 90% du temps de développement » - Tom Cargill


Et ça y est, on y est, on est arrivés, la voilà, c’est Broadway, la quatrième et dernière structure : ça est les boucles. Si vous voulez épater vos amis, vous pouvez également parler de structures répétitives, voire carrément de structures itératives. Ca calme, hein ? Bon, vous faites ce que vous voulez, ici on est entre nous, on parlera de boucles.
Les boucles, c'est généralement le point douloureux de l'apprenti programmeur. C'est là que ça coince, car autant il est assez facile de comprendre comment fonctionnent les boucles, autant il est souvent long d'acquérir les réflexes qui permettent de les élaborer judicieusement pour traiter un problème donné.
On peut dire en fait que les boucles constituent la seule vraie structure logique caractéristique de la programmation. Si vous avez utilisé un tableur comme Excel, par exemple, vous avez sans doute pu manier des choses équivalentes aux variables (les cellules, les formules) et aux tests (la fonction SI…). Mais les boucles, ça, ça n'a aucun équivalent. Cela n'existe que dans les langages de programmation proprement dits.
Le maniement des boucles, s'il ne différencie certes pas l'homme de la bête (il ne faut tout de même pas exagérer), est tout de même ce qui sépare en informatique le programmeur de l'utilisateur, même averti.
Alors, à vos futures – et inévitables - difficultés sur le sujet, il y a trois remèdes : de la rigueur, de la patience, et encore de la rigueur !
1. A quoi cela sert-il donc ?
Prenons le cas d’une saisie au clavier (une lecture), où par exemple, le programme pose une question à laquelle l’utilisateur doit répondre par O (Oui) ou N (Non). Mais tôt ou tard, l’utilisateur, facétieux ou maladroit, risque de taper autre chose que la réponse attendue. Dès lors, le programme peut planter soit par une erreur d’exécution (parce que le type de réponse ne correspond pas au type de la variable attendu) soit par une erreur fonctionnelle (il se déroule normalement jusqu’au bout, mais en produisant des résultats fantaisistes).
Alors, dans tout programme un tant soit peu sérieux, on met en place ce qu’on appelle un contrôle de saisie, afin de vérifier que les données entrées au clavier correspondent bien à celles attendues par l’algorithme.
A vue de nez, on pourrait essayer avec un SI. Voyons voir ce que ça donne :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
Si Rep <> "O" et Rep <> "N" Alors
Ecrire "Saisie erronnée. Recommencez"
Lire Rep
FinSi
Fin
C’est impeccable. Du moins tant que l’utilisateur a le bon goût de ne se tromper qu’une seule fois, et d’entrer une valeur correcte à la deuxième demande. Si l’on veut également bétonner en cas de deuxième erreur, il faudrait rajouter un SI. Et ainsi de suite, on peut rajouter des centaines de SI, et écrire un algorithme aussi lourd qu’une blague des Grosses Têtes, on n’en sortira pas, il y aura toujours moyen qu’un acharné flanque le programme par terre.
La solution consistant à aligner des SI… en pagaille est donc une impasse. La seule issue est donc de flanquer une structure de boucle, qui se présente ainsi :
TantQue booléen
…
Instructions
…
FinTantQue
Le principe est simple : le programme arrive sur la ligne du TantQue. Il examine alors la valeur du booléen (qui, je le rappelle, peut être une variable booléenne ou, plus fréquemment, une condition). Si cette valeur est VRAI, le programme exécute les instructions qui suivent, jusqu’à ce qu’il rencontre la ligne FinTantQue. Il retourne ensuite sur la ligne du TantQue, procède au même examen, et ainsi de suite. Le manège enchanté ne s’arrête que lorsque le booléen prend la valeur FAUX.
Illustration avec notre problème de contrôle de saisie. Une première approximation de la solution consiste à écrire :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Là, on a le squelette de l’algorithme correct. Mais de même qu’un squelette ne suffit pas pour avoir un être vivant viable, il va nous falloir ajouter quelques muscles et organes sur cet algorithme pour qu’il fonctionne correctement.
Son principal défaut est de provoquer une erreur à chaque exécution. En effet, l’expression booléenne qui figure après le TantQue interroge la valeur de la variable Rep. Malheureusement, cette variable, si elle a été déclarée, n’a pas été affectée avant l’entrée dans la boucle. On teste donc une variable qui n’a pas de valeur, ce qui provoque une erreur et l’arrêt immédiat de l’exécution. Pour éviter ceci, on n’a pas le choix : il faut que la variable Rep ait déjà été affectée avant qu’on en arrive au premier tour de boucle. Pour cela, on peut faire une première lecture de Rep avant la boucle. Dans ce cas, celle-ci ne servira qu’en cas de mauvaise saisie lors de cette première lecture. L’algorithme devient alors :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Une autre possibilité, fréquemment employée, consiste à ne pas lire, mais à affecter arbitrairement la variable avant la boucle. Arbitrairement ? Pas tout à fait, puisque cette affectation doit avoir pour résultat de provoquer l’entrée obligatoire dans la boucle. L’affectation doit donc faire en sorte que le booléen soit mis à VRAI pour déclencher le premier tour de la boucle. Dans notre exemple, on peut donc affecter Rep avec n’importe quelle valeur, hormis « O » et « N » : car dans ce cas, l’exécution sauterait la boucle, et Rep ne serait pas du tout lue au clavier. Cela donnera par exemple :
Variable Rep en Caractère
Début
Rep ← "X"
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Cette manière de procéder est à connaître, car elle est employée très fréquemment.
Il faut remarquer que les deux solutions (lecture initiale de Rep en dehors de la boucle ou affectation de Rep) rendent toutes deux l’algorithme satisfaisant, mais présentent une différence assez importante dans leur structure logique.
En effet, si l’on choisit d’effectuer une lecture préalable de Rep, la boucle ultérieure sera exécutée uniquement dans l’hypothèse d’une mauvaise saisie initiale. Si l’utilisateur saisit une valeur correcte à la première demande de Rep, l’algorithme passera sur la boucle sans entrer dedans.
En revanche, avec la deuxième solution (celle d’une affectation préalable de Rep), l’entrée de la boucle est forcée, et l’exécution de celle-ci, au moins une fois, est rendue obligatoire à chaque exécution du programme. Du point de vue de l’utilisateur, cette différence est tout à fait mineure ; et à la limite, il ne la remarquera même pas. Mais du point de vue du programmeur, il importe de bien comprendre que les cheminements des instructions ne seront pas les mêmes dans un cas et dans l’autre.
Pour terminer, remarquons que nous pourrions peaufiner nos solutions en ajoutant des affichages de libellés qui font encore un peu défaut. Ainsi, si l’on est un programmeur zélé, la première solution (celle qui inclut deux lectures de Rep, une en dehors de la boucle, l’autre à l’intérieur) pourrait devenir :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
TantQue Rep <> "O" et Rep <> "N"
Ecrire "Vous devez répondre par O ou N. Recommencez"
Lire Rep
FinTantQue
Ecrire "Saisie acceptée"
Fin
Quant à la deuxième solution, elle pourra devenir :
Variable Rep en Caractère
Début
Rep ← "X"
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
Si Rep <> "O" et Rep <> "N" Alors
Ecrire "Saisie Erronée, Recommencez"
FinSi
FinTantQue
Fin
Le Gag De La Journée
C’est d’écrire une structure TantQue dans laquelle le booléen n’est jamais VRAI. Le programme ne rentre alors jamais dans la superbe boucle sur laquelle vous avez tant sué !
Mais la faute symétrique est au moins aussi désopilante.
Elle consiste à écrire une boucle dans laquelle le booléen ne devient jamais FAUX. L’ordinateur tourne alors dans la boucle comme un dératé et n’en sort plus. Seule solution, quitter le programme avec un démonte-pneu ou un bâton de dynamite. La « boucle infinie » est une des hantises les plus redoutées des programmeurs. C’est un peu comme le verre baveur, le poil à gratter ou le bleu de méthylène : c’est éculé, mais ça fait toujours rire.
Cette faute de programmation grossière – mais fréquente - ne manquera pas d’égayer l’ambiance collective de cette formation… et accessoirement d’étancher la soif proverbiale de vos enseignants.
Bon, eh bien vous allez pouvoir faire de chouettes algorithmes, déjà rien qu’avec ça
2. Boucler en comptant, ou compter en bouclant
Dans le dernier exercice, vous avez remarqué qu’une boucle pouvait être utilisée pour augmenter la valeur d’une variable. Cette utilisation des boucles est très fréquente, et dans ce cas, il arrive très souvent qu’on ait besoin d’effectuer un nombre déterminé de passages. Or, a priori, notre structure TantQue ne sait pas à l’avance combien de tours de boucle elle va effectuer (puisque le nombre de tours dépend de la valeur d’un booléen).
C’est pourquoi une autre structure de boucle est à notre disposition :
Variable Truc en Entier
Début
Truc ← 0
TantQue Truc < 15
Truc ← Truc + 1
Ecrire "Passage numéro : ", Truc
FinTantQue
Fin
Equivaut à :
Variable Truc en Entier
Début
Pour Truc ← 1 à 15
Ecrire "Passage numéro : ", Truc
Truc Suivant
Fin
Insistons : la structure « Pour … Suivant » n’est pas du tout indispensable ; on pourrait fort bien programmer toutes les situations de boucle uniquement avec un « Tant Que ». Le seul intérêt du « Pour » est d’épargner un peu de fatigue au programmeur, en lui évitant de gérer lui-même la progression de la variable qui lui sert de compteur (on parle d’incrémentation, encore un mot qui fera forte impression sur votre entourage).
Dit d’une autre manière, la structure « Pour … Suivant » est un cas particulier de TantQue : celui où le programmeur peut dénombrer à l’avance le nombre de tours de boucles nécessaires.
Il faut noter que dans une structure « Pour … Suivant », la progression du compteur est laissée à votre libre disposition. Dans la plupart des cas, on a besoin d’une variable qui augmente de 1 à chaque tour de boucle. On ne précise alors rien à l’instruction « Pour » ; celle-ci, par défaut, comprend qu’il va falloir procéder à cette incrémentation de 1 à chaque passage, en commençant par la première valeur et en terminant par la deuxième.
Mais si vous souhaitez une progression plus spéciale, de 2 en 2, ou de 3 en 3, ou en arrière, de –1 en –1, ou de –10 en –10, ce n’est pas un problème : il suffira de le préciser à votre instruction « Pour » en lui rajoutant le mot « Pas » et la valeur de ce pas (Le « pas » dont nous parlons, c’est le « pas » du marcheur, « step » en anglais).
Naturellement, quand on stipule un pas négatif dans une boucle, la valeur initiale du compteur doit être supérieure à sa valeur finale si l’on veut que la boucle tourne ! Dans le cas contraire, on aura simplement écrit une boucle dans laquelle le programme ne rentrera jamais.
Nous pouvons donc maintenant donner la formulation générale d’une structure « Pour ». Sa syntaxe générale est :
Pour Compteur ← Initial à Final Pas ValeurDuPas
…
Instructions
…
Compteur suivant
Les structures TantQue sont employées dans les situations où l’on doit procéder à un traitement systématique sur les éléments d’un ensemble dont on ne connaît pas d’avance la quantité, comme par exemple :
• le contrôle d’une saisie
• la gestion des tours d’un jeu (tant que la partie n’est pas finie, on recommence)
• la lecture des enregistrements d’un fichier de taille inconnue(cf. Partie 9)
Les structures Pour sont employées dans les situations où l’on doit procéder à un traitement systématique sur les éléments d’un ensemble dont le programmeur connaît d’avance la quantité.
Nous verrons dans les chapitres suivants des séries d’éléments appelés tableaux (parties 7 et et chaînes de caractères (partie 9). Selon les cas, le balayage systématique des éléments de ces séries pourra être effectué par un Pour ou par un TantQue : tout dépend si la quantité d’éléments à balayer (donc le nombre de tours de boucles nécessaires) peut être dénombrée à l’avance par le programmeur ou non.

4. Et encore une bêtise à ne pas faire !
Examinons l’algorithme suivant :
Variable Truc en Entier
Début
Pour Truc ← 1 à 15
Truc ← Truc * 2
Ecrire "Passage numéro : ", Truc
Truc Suivant
Fin
Vous remarquerez que nous faisons ici gérer « en double » la variable Truc, ces deux gestions étant contradictoires. D’une part, la ligne
Pour…
augmente la valeur de Truc de 1 à chaque passage. D’autre part la ligne
Truc ← Truc * 2
double la valeur de Truc à chaque passage. Il va sans dire que de telles manipulations perturbent complètement le déroulement normal de la boucle, et sont causes, sinon de plantages, tout au moins d’exécutions erratiques.
Le Gag De La Journée
Il consiste donc à manipuler, au sein d’une boucle Pour, la variable qui sert de compteur à cette boucle. Cette technique est à proscrire absolument… sauf bien sûr, si vous cherchez un prétexte pour régaler tout le monde au bistrot.
Mais dans ce cas, n’ayez aucune inhibition, proposez-le directement, pas besoin de prétexte.




index.htm&é&&&http://www.xiti.com/xiti.asp?s=98415
PARTIE 5
Enonce des Exercices
Exercice 5.1
Ecrire un algorithme qui demande à l’utilisateur un nombre compris entre 1 et 3 jusqu’à ce que la réponse convienne.
corrigé - retour au cours

Exercice 5.2
Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu’à ce que la réponse convienne. En cas de réponse supérieure à 20, on fera apparaître un message : « Plus petit ! », et inversement, « Plus grand ! » si le nombre est inférieur à 10.
corrigé - retour au cours

Exercice 5.3
Ecrire un algorithme qui demande un nombre de départ, et qui ensuite affiche les dix nombres suivants. Par exemple, si l'utilisateur entre le nombre 17, le programme affichera les nombres de 18 à 27.
corrigé - retour au cours

Exercice 5.4
Ecrire un algorithme qui demande un nombre de départ, et qui ensuite écrit la table de multiplication de ce nombre, présentée comme suit (cas où l'utilisateur entre le nombre 7) :
Table de 7 :
7 x 1 = 7
7 x 2 = 14
7 x 3 = 21
…
7 x 10 = 70
corrigé - retour au cours

Exercice 5.5
Ecrire un algorithme qui demande un nombre de départ, et qui calcule la somme des entiers jusqu’à ce nombre. Par exemple, si l’on entre 5, le programme doit calculer :
1 + 2 + 3 + 4 + 5 = 15
NB : on souhaite afficher uniquement le résultat, pas la décomposition du calcul.
corrigé - retour au cours

Exercice 5.6
Ecrire un algorithme qui demande un nombre de départ, et qui calcule sa factorielle.
NB : la factorielle de 8, notée 8 !, vaut
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
corrigé - retour au cours

Exercice 5.7
Ecrire un algorithme qui demande successivement 20 nombres à l’utilisateur, et qui lui dise ensuite quel était le plus grand parmi ces 20 nombres :
Entrez le nombre numéro 1 : 12
Entrez le nombre numéro 2 : 14
etc.
Entrez le nombre numéro 20 : 6
Le plus grand de ces nombres est : 14
Modifiez ensuite l’algorithme pour que le programme affiche de surcroît en quelle position avait été saisie ce nombre :
C’était le nombre numéro 2
corrigé - retour au cours

Exercice 5.8
Réécrire l’algorithme précédent, mais cette fois-ci on ne connaît pas d’avance combien l’utilisateur souhaite saisir de nombres. La saisie des nombres s’arrête lorsque l’utilisateur entre un zéro.
corrigé - retour au cours

Exercice 5.9
Lire la suite des prix (en euros entiers et terminée par zéro) des achats d’un client. Calculer la somme qu’il doit, lire la somme qu’il paye, et simuler la remise de la monnaie en affichant les textes "10 Euros", "5 Euros" et "1 Euro" autant de fois qu’il y a de coupures de chaque sorte à rendre.
corrigé - retour au cours

Exercice 5.10
Écrire un algorithme qui permette de connaître ses chances de gagner au tiercé, quarté, quinté et autres impôts volontaires.
On demande à l’utilisateur le nombre de chevaux partants, et le nombre de chevaux joués. Les deux messages affichés devront être :
Dans l’ordre : une chance sur X de gagner
Dans le désordre : une chance sur Y de gagner
X et Y nous sont donnés par la formule suivante, si n est le nombre de chevaux partants et p le nombre de chevaux joués (on rappelle que le signe ! signifie "factorielle", comme dans l'exercice 5.6 ci-dessus) :
X = n ! / (n - p) !
Y = n ! / (p ! * (n – p) !)
NB : cet algorithme peut être écrit d’une manière simple, mais relativement peu performante. Ses performances peuvent être singulièrement augmentées par une petite astuce. Vous commencerez par écrire la manière la plus simple, puis vous identifierez le problème, et écrirez une deuxième version permettant de le résoudre.
corrigé - retour au cours



http://www.xiti.com/xiti.asp?s=98415&é&&&http://www.xiti.com/xiti.asp?s=98415
PARTIE 5
Corrigés des Exercices
Exercice 5.1
Variable N en Entier
Debut
N ← 0
Ecrire "Entrez un nombre entre 1 et 3"
TantQue N < 1 ou N > 3
Lire N
Si N < 1 ou N > 3 Alors
Ecrire "Saisie erronée. Recommencez”
FinSi
FinTantQue
Fin
énoncé - retour au cours

Exercice 5.2
Variable N en Entier
Debut
N ← 0
Ecrire "Entrez un nombre entre 10 et 20"
TantQue N < 10 ou N > 20
Lire N
Si N < 10 Alors
Ecrire "Plus grand !"
SinonSi N > 20 Alors
Ecrire "Plus petit !"
FinSi
FinTantQue
Fin
énoncé - retour au cours

Exercice 5.3
Variables N, i en Entier
Debut
Ecrire "Entrez un nombre : "
Lire N
Ecrire "Les 10 nombres suivants sont : "
Pour i ← N + 1 à N + 10
Ecrire i
i Suivant
Fin
énoncé - retour au cours

Exercice 5.4
Variables N, i en Entier
Debut
Ecrire "Entrez un nombre : "
Lire N
Ecrire "La table de multiplication de ce nombre est : "
Pour i ← 1 à 10
Ecrire N, " x ", i, " = ", n*i
i Suivant
Fin
énoncé - retour au cours

Exercice 5.5
Variables N, i, Som en Entier
Debut
Ecrire "Entrez un nombre : "
Lire N
Som ← 0
Pour i ← 1 à N
Som ← Som + i
i Suivant
Ecrire "La somme est : ", Som
Fin
énoncé - retour au cours

Exercice 5.6
Variables N, i, F en Entier
Debut
Ecrire "Entrez un nombre : "
Lire N
F ← 1
Pour i ← 2 à N
F ← F * i
i Suivant
Ecrire "La factorielle est : ", F
Fin
énoncé - retour au cours

Exercice 5.7
Variables N, i, PG en Entier
Debut
PG ← 0
Pour i ← 1 à 20
Ecrire "Entrez un nombre : "
Lire N
Si i = 1 ou N > PG Alors
PG ← N
FinSi
i Suivant
Ecrire "Le nombre le plus grand était : ", PG
Fin
En ligne 3, on peut mettre n’importe quoi dans PG, il suffit que cette variable soit affectée pour que le premier passage en ligne 7 ne provoque pas d'erreur.

Pour la version améliorée, cela donne :
Variables N, i, PG, IPG en Entier
Debut
PG ← 0
Pour i ← 1 à 20
Ecrire "Entrez un nombre : "
Lire N
Si i = 1 ou N > PG Alors
PG ← N
IPG ← i
FinSi
i Suivant
Ecrire "Le nombre le plus grand était : ", PG
Ecrire "Il a été saisi en position numéro ", IPG
Fin
énoncé - retour au cours

Exercice 5.8
Variables N, i, PG, IPG en Entier
Debut
N ← 1
i ← 0
PG ← 0
TantQue N <> 0
Ecrire "Entrez un nombre : "
Lire N
i ← i + 1
Si i = 1 ou N > PG Alors
PG ← N
IPG ← i
FinSi
FinTantQue
Ecrire "Le nombre le plus grand était : ", PG
Ecrire "Il a été saisi en position numéro ", IPG
Fin
énoncé - retour au cours

Exercice 5.9
Variables E, somdue, M, Reste, Nb10E, Nb5E En Entier
Debut
E ← 1
somdue ← 0
TantQue E <> 0
Ecrire "Entrez le montant : "
Lire E
somdue ← somdue + E
FinTantQue
Ecrire "Vous devez :", somdue, " euros"
Ecrire "Montant versé :"
Lire M
Reste ← M - somdue
Nb10E ← 0
TantQue Reste >= 10
Nb10E ← Nb10E + 1
Reste ← Reste – 10
FinTantQue
Nb5E ← 0
Si Reste >= 5
Nb5E ← 1
Reste ← Reste – 5
FinSi
Ecrire "Rendu de la monnaie :"
Ecrire "Billets de 10 E : ", Nb10E
Ecrire "Billets de 5 E : ", Nb5E
Ecrire "Pièces de 1 E : ", reste
Fin
énoncé - retour au cours

Exercice 5.10
Spontanément, on est tenté d'écrire l'algorithme suivant :
Variables N, P, i, Numé, Déno1, Déno2 en Entier
Debut Ecrire "Entrez le nombre de chevaux partants : "
Lire N
Ecrire "Entrez le nombre de chevaux joués : "
Lire P
Numé ← 1
Pour i ← 2 à N
Numé ← Numé * i
i Suivant
Déno1 ← 1
Pour i ← 2 à N-P
Déno1 ← Déno1 * i
i Suivant
Déno2 ← 1
Pour i ← 2 à P
Déno2 ← Déno2 * i
i Suivant
Ecrire "Dans l’ordre, une chance sur ", Numé / Déno1
Ecrire "Dans le désordre, une sur ", Numé / (Déno1 * Déno2)
Fin
Cette version, formellement juste, comporte tout de même deux faiblesses.

La première, et la plus grave, concerne la manière dont elle calcule le résultat final. Celui-ci est le quotient d'un nombre par un autre ; or, ces nombres auront rapidement tendance à être très grands. En calculant, comme on le fait ici, d'abord le numérateur, puis ensuite le dénominateur, on prend le risque de demander à la machine de stocker des nombres trop grands pour qu'elle soit capable de les coder (cf. le préambule). C'est d'autant plus bête que rien ne nous oblige à procéder ainsi : on n'est pas obligé de passer par la division de deux très grands nombres pour obtenir le résultat voulu.

La deuxième remarque est qu'on a programmé ici trois boucles successives. Or, en y regardant bien, on peut voir qu'après simplification de la formule, ces trois boucles comportent le même nombre de tours ! (si vous ne me croyez pas, écrivez un exemple de calcul et biffez les nombres identiques au numérateur et au dénominateur). Ce triple calcul (ces trois boucles) peut donc être ramené(es) à un(e) seul(e). Et voilà le travail, qui est non seulement bien plus court, mais aussi plus performant :
Variables N, P, i, O, F en Entier
Debut
Ecrire "Entrez le nombre de chevaux partants : "
Lire N
Ecrire "Entrez le nombre de chevaux joués : "
Lire P
A ← 1
B ← 1
Pour i ← 1 à P
A ← A * (i + N - P)
B ← B * i
i Suivant
Ecrire "Dans l’ordre, une chance sur ", A
Ecrire "Dans le désordre, une chance sur ", A / B
Fin
énoncé - retour au cours