Le Monde Merveilleux de l'AlgorithmiqueMD
Bienvenue dans le Monde Merveilleux de l'AlgorithmiqueMD.
Ce cours se veut une introduction � l'algorithmique et � la
programmatique, deux termes que nous d�finirons plus loin.
Vous �tes au bon endroit si vous n'avez pas, ou �
peu pr�s pas, programm�, mais avez envie d'apprendre cette science
(ou cet art, tout d�pendant du point de vue).
Vous �tes au mauvais endroit si vous avez d�j�
un bagage en programmation ou en langage C++, ou encore si votre objectif
est d'approfondir votre savoir en la mati�re plut�t que d'y �tre
introduit.
Note: |
une partie de ce document provient des efforts de Vincent Echelard,
professeur lui aussi au d�partement d'informatique du Coll�ge
Lionel-Groulx. Si vous le voyez, remerciez-le et offrez-lui un caf� |
La programmatique et la r�solution de probl�mes
- On dit de la programmatique qu'elle
repr�sente l'art de la bonne
programmation.
En effet, si l'algorithmique est une science exacte, au m�me
titre que les math�matiques ou la physique, la programmatique comporte
de son c�t� une part d'investissement humain et d'esth�tique,
tout en �tant une composante � part enti�re (et essentielle)
de la programmation.
Les principaux �l�ments de la programmatique, et donc les �tapes
fondamentales requises pour la r�daction d'un programme, sont:
- Une analyse structur�e du
probl�me;
- Un mode
d'expression permettant d'exprimer les r�sultats de cette
analyse qui soit ind�pendant du langage de programmation utilis�
par la suite;
- Une traduction du
r�sultat exprim� dans un langage compr�hensible par la
machine.
Prenons, dans ce qui suit, les
�l�ments dans l'ordre.
La raison d'�tre d'un algorithme
� la base de toute la programmatique se trouve
l'algorithmique, la science propre � la conception et �
l'analyses des algorithmes.
- un algorithme se voudra, dans sa forme la
plus g�n�rale, une m�thode formelle pour r�soudre
un probl�me. Une d�finition plus pr�cise suivra, mais
gardez celle-ci en t�te; elle sera souvent suffisante pour combler nos
besoins.
C'est pourquoi le probl�me lui-m�me fait partie int�grante
de notre d�finition. Pas de probl�me, pas de plaisir pour nous.
Pour parvenir � produire un v�ritable algorithme, il faut d'abord
proc�der � une analyse du probl�me, mais pas n'importe
quelle analyse: une analyse structur�e.
Exemple: supposons que nous recherchons un algorithme qui nous
permettra de nous faire cuire un oeuf.
Si notre analyse ressemble par exemple � ce qui suit:
Probl�me:
se faire cuire un oeuf
Algorithme: «euh...
bien, on fait cuire l'oeuf!»
|
nous ne serons pas vraiment plus avanc�s qu'avant m�me de se
poser la question «comment r�soudre le probl�me?».
Analyse structur�e
Analyser un probl�me de fa�on structur�e
peut �tre abord� de plusieurs mani�res. Dans ce cours, nous
chercherons surtout � d�composer un probl�me en plus
petits probl�mes, dans le but de le simplifier.
D�finition, d�composition et solution d'un
probl�me
Lorsque l'on veut appliquer une solution informatique pour r�soudre
un probl�me, il faut �viter de se pr�cipiter devant un
�cran d'ordinateur.
Programmer sans r�fl�chir a priori ne cause que des probl�mes.
On risque, en programmant sans analyse au pr�alable, d'aboutir �
une solution incompl�te (dans la mesure o� on arrive effectivement
� une solution).
En effet, le processus qui permet de r�soudre un probl�me
en informatique comporte habituellement deux (2)
phases principales:
- La phase de r�solution du
probl�me, qui permet d'�laborer une solution
th�orique au probl�me;
- La phase
de mise en oeuvre, qui permet d'implanter la solution
th�orique sur ordinateur.
Chacune de ces phases comporte un certain nombre d'op�rations qu'on
peut regrouper en �tapes.
La phase de r�solution du probl�me peut
�tre scind�e en trois (3)
�tapes :
- La compr�hension du
probl�me;
- L'analyse des
donn�es et des �l�ments du probl�me pour
explorer diff�rentes m�thodes de solution
possibles;
- Le choix d'une
m�thode de solution, puis la conception et le
d�veloppement d'une s�quence ordonn�e
d'op�rations (algorithme) menant � la solution du
probl�me.
La phase de mise en oeuvre peut �tre scind�e
en deux (2) �tapes :
- La traduction de la s�quence
ordonn�e des op�rations dans un langage de programmation
(codification de l'algorithme);
- La mise
au point du ou des programmes r�sultants, par le biais de tests et
des essais sur des jeux de donn�es fictives (jeux
d'essais).
Le sch�ma suivant
d�note les relations entre ces diverses �tapes:
Il est � relever que le processus de d�veloppement est cyclique.
Un sch�ma plus complet (le temps m'a manqu� cette fois-ci) en
ferait �tat.
�nonc� du probl�me et donn�es
Nous l'avons soulign� auparavant: il n'y a
pas de plaisir sans probl�me. C'est pourquoi il nous faut
d'abord et avant tout deux choses:
- un probl�me,
c'est-�-dire une description d'une situation servant de point
de d�marrage � la r�flexion, et une description de
l'objectif vis�, g�n�ralement une transformation
� appliquer � la situation
initiale;
- des donn�es, les
�l�ments objectifs et factuels sur lesquels repose
l'instance pr�cise du probl�me sur lequel nous
travaillons.
Dans le cas d'un meuble �
assembler, le probl�me serait de passer de l'�tat
d�sassembl� d'un meuble � celui assembl�, et
les donn�es seraient les objets � composer pour constituer
le meuble lui-m�me. Les instructions... sont du ressort de
l'algorithme
La phase de r�solution du probl�me
Une fois l'�tape de la compr�hension du probl�me r�solue
(ce qui n'est pas toujours simple), il faut passer � l'�tape
suivante qui consiste � examiner diff�rentes approches g�n�rales
permettant de r�soudre le probl�me.
Une des m�thodes les plus employ�es en informatique (et qui
sera, comme mentionn� pr�c�demment) est l'approche par
sous-objectifs.
Cette m�thode consiste � fractionner un probl�me difficile
en plusieurs petits probl�mes plus simples. On dit d'elle qu'elle est
une «m�thode descendante» (top down method), du
fait qu'elle part du probl�me g�n�ral pour en faire une
d�composition.
Le terme algorithme est utilis� en l'honneur d'un math�maticien
persan, Mohammed ibn Musa al-Khuwarizmi (825
A.D.), dont le 2�me livre nous a donn�
le mot alg�bre (Al-jabr). |
�tant donn� un probl�me sp�cifique, un algorithme
est la s�quence compl�te et ordonn�e de toutes les op�rations
(actions) � faire pour en obtenir la solution. Cette s�quence
d'op�rations est dict�e par le probl�me � r�soudre
et par la m�thode de r�solution choisie.
Exemples d'algorithmes:
- Les indications donn�es �
quelqu'un pour trouver son chemin;
- La liste
des instructions d'assemblage (mode d'assemblage) d'un avion
� coller ou d'un bureau �
assembler;
- Les instructions d'une recette
de p�ches flamb�es au Grand Marnier.
En informatique, ce terme se r�f�re � une m�thode
de r�solution de probl�mes, comme nous l'avons mentionn�
pr�c�demment. Nous faisons usage d'un ordinateur pour implanter
nos algorithmes dans le but d'automatiser le processus de r�solution
de probl�mes. L'id�e est donc, fondamentalement, de se simplifier
la vie pour longtemps en se la compliquant une fois.
Un algorithme se compose d'une s�rie finie
d'�tapes, chacune n�cessitant une ou plusieurs
op�rations. Chaque op�ration doit:
- Être pr�cise et bien
d�finie (sans
ambigu�t�);
- Produire les
m�mes r�sultats avec le m�me jeu de
donn�es;
- Se terminer
apr�s un nombre fini
d'op�rations.
- Une
op�ration est une action pouvant �tre effectu�e par
un ordinateur.
Par exemple, l'ordinateur
peut:
- Lire un
nombre;
- Comparer 2 nombres;
- Additionner, soustraire 2 nombres;
- R�p�ter une s�rie
d'op�rations;
- Afficher un
nombre;
- etc.
Les �tapes d'un algorithme
Un algorithme comprend g�n�ralement trois (3)
�tapes:
- La pr�paration du traitement qui consiste
� d�finir ou identifier les donn�es
n�cessaires � la r�solution du
probl�me;
- Le traitement qui consiste
� d�composer le probl�me en op�rations et
structures de
contr�le;
- L'�dition ou
l'affichage des r�sultats qui consiste � identifier et
afficher les r�sultats que l'ordinateur devra nous faire
conna�tre.
Exemple: le calcul du volume d'une sph�re.
- Identifier le rayon;
- Formule pour le calcul du volume de
la sph�re : 4/3 * PI * r3;
- Affichage de la valeur du volume
|
Repr�sentation de l'algorithme
Un algorithme peut �tre pr�sent� sous deux
(2) formes:
- Le pseudo-code ou fran�ais
structur�, qui est la repr�sentation textuelle de
l'algorithme, se pr�sente sous la forme d'instructions
br�ves utilisant un vocabulaire limit� mais
pr�cis;
- Le morphogramme ou
ordinogramme, qui est la repr�sentation graphique de
l'algorithme, se pr�sente sous la forme d'un ensemble de
symboles conventionnels reli�s par des
fl�ches.
D�finition des actions de base (op�rations, instructions)
Il existe trois grandes cat�gories
d'op�rations :
- La lecture qui permet l'entr�e des donn�es (LIRE...);
- L'�criture qui permet la sortie des r�sultats (ECRIRE...);
- L'affectation qui permet d'assigner � une variable le r�sultat
d'une expression arithm�tique (Variable
<-- Expression
arithm�tique).
D�finition des structures de contr�le (structures de base)
En programmation structur�e, pour construire des
algorithmes, on se sert des trois structures de base suivantes:
- La s�quence, qui est une succession ordonn�e d'op�rations;
- L'alternative, qui est une structure dans laquelle, suivant l'�valuation
d'une condition, l'une ou l'autre de deux op�rations est ex�cut�e;
et
- La r�p�titive, qui est une structure permettant de
r�p�ter une op�ration (ou un groupe d'op�rations)
un certain nombre de fois, en fonction d'une condition.
La s�quence
La structure de contr�le qu'on nomme la
s�quence se r�clame de ce qui suit: une suite
d'op�rations cons�cutives et ordonn�es.
Puisqu'on parle d'algorithmique, la s�quence aura un
d�but, une fin, et aura un objectif pr�cis.
Formes de la s�quence
L'exemple suivant d�crit la structure de contr�le «s�quence»
� la fois sous la forme de morphogramme et de pseudo-code.
Exemple de probl�me � r�soudre:
se faire une tasse de th�.
Pseudo-code
|
Morphogramme
|
Faire bouillir de l'eau
Prendre une tasse
Y d�poser un sachet de th�
Y verser de l'eau bouillante
Presser le sachet et le retirer
Ajouter un peu d'eau froide
|
|
Remarques
Au sujet de la s�quence, remarquez les choses
suivantes:
- � partir du moment o� une
s�quence est �nonc�e, chaque op�ration qu'elle
contient est obligatoire. C'est donc dire qu'on ne peut pas sauter
d'�tapes dans l'ex�cution des op�rations
(d'o� le terme s�quence, en fait: une suite finie
d'op�rations);
- Dans le cas
d'une s�quence, chaque ligne du pseudo-code correspond � un
rectangle dans le morphogramme (une op�rations simple: un
rectangle);
- Une s�quence se lit toujours
de haut en bas (ou de gauche � droite: l'id�e est de
refl�ter la s�quence de lecture normale des individus... du moins,
des nord-am�ricain(e)s);
- Dans le
morphogramme, les rectangles sont reli�s les uns aux autres par une ligne
qui marque leur encha�nement obligatoire. Puisque la lecture d'une
s�quence se fait de haut en bas, cette ligne arrive toujours au centre
sup�rieur (point d'entr�e) d'un rectangle et le quitte
toujours par son centre inf�rieur (point de sortie). De plus, prise
globalement, la s�quence n'a qu'un point
d'entr�e et un point de
sortie;
- Chaque op�ration d'une
s�quence est soit �l�mentaire, soit
d�composable.
Types d'op�rations
- Une op�ration
�l�mentaire est celle qu'on ne juge pas utile de
d�composer;
- une op�ration est
d�composable[1] si on peut
la d�couper en un ensemble d'op�rations plus
d�taill�es.
Par exemple, pour faire bouillir de l'eau, on peut:
Mettre de l'eau dans
la bouilloire;
Brancher la bouilloire;
attendre que l'eau bouille.
|
Exercices sur les s�quences
Une personne utilise sa voiture pour se rendre au travail. �crire
le pseudo-code et le morphogramme repr�sentant l'algorithme qui permet
� cette personne de calculer et d'afficher son co�t de d�placement.
Pour cela votre algorithme devra pr�alablement lire les
trois (3) renseignements suivants
:
- La distance �
parcourir;
- La performance de la voiture en
km/litre;
- Le prix de l'essence au
litre.
Exercice 2
Les ouvriers d'une entreprise ont re�u une augmentation de salaire
de 4%. Cette augmentation est
r�troactive de 6 mois.
�crire le pseudo-code et le morphogramme
repr�sentant l'algorithme qui lit:
et affiche:
- Le montant r�troactif auquel l'ouvrier a
droit;
- Le nouveau salaire
annuel;
- Le nouveau salaire
mensuel.
�crire le pseudo-code et le morphogramme de l'algorithme permettant
d'�changer le contenu de deux variables,
X et Y.
Vous devrez donc:
- Lire les valeurs de X et
Y;
- �changer le contenu de ces deux variables;
- Afficher la valeur finale de X et
de Y.
Exercice 4
�crire le pseudo-code et le morphogramme de l'algorithme permettant
de calculer et d'afficher et d'afficher le salaire net d'un employ�.
Pour cela, il vous faudra lire les informations
suivantes:
- Le nombre d'heures
travaill�es;
- Le taux
horaire.
Il vous faudra tenir compte que l'employ�
devra payer:
- 15% d'imp�t f�d�ral;
- 20% d'imp�t provincial.
Exercice 5
Un chef d'entreprise veut conna�tre combien lui co�te la fabrication
d'un exemplaire de son produit. �crire le pseudo-code et le morphogramme
repr�sentant l'algorithme qui permet � d'ex�cuter ce
calcul et d'afficher le r�sultat.
Pour cela votre algorithme devra pr�alablement lire les
trois (3) renseignements suivants
:
- Le co�t des mat�riaux
n�cessaire � la fabrication d'un
exemplaire;
- Le salaire horaire du
machiniste;
- Le nombre d'exemplaire produit par le
machiniste en une heure.
Exercice 6
�crire le pseudo-code et le morphogramme de l'algorithme permettant
d'�changer le contenu de trois variables:
X, Y et
Z.
Vous devrez donc:
- Lire les valeurs de X,
Y et Z;
- �changer le contenu de ces trois
variables;
- Afficher la valeur finale de X,
de Y et de
Z.
�crire le pseudo-code et le morphogramme de l'algorithme permettant
de calculer et d'afficher le salaire net d'un employ� ainsi que le
d�tail des d�ductions.
Pour cela, il vous faudra lire les informations
suivantes:
- Le nombre d'heures
travaill�es;
- Le taux
horaire.
Il vous faudra tenir compte que l'employ�
devra payer:
- 15% d'imp�t f�d�ral;
- 20% d'imp�t provincial;
- 2,5% d'assurance emploi;
- 2% de r�gime des rentes.
L'alternative
La structure de contr�le qu'on nomme
l'alternative se r�clame de ce qui suit:
- un pr�dicat qu'on
doit �valuer, duquel on peut dire qu'il est vrai ou
qu'il est faux, sans ambigu�t� ni
contradiction;
- un choix, d�pendant
de l'�valuation du pr�dicat, entre une
s�quence d'op�rations � accomplir s'il
s'av�re vrai, et une s�quence d'op�rations
� faire s'il s'av�re faux.
Un exemple de pr�dicat serait «Jean
est plus grand que Roger». En effet, cet �nonc�
est soit vrai, soit faux, au moment o� il est formul�,
et pour un Jean et un Roger bien pr�cis.
Un exemple de choix de s�quences �tant donn�
la valeur d'un pr�dicat serait «s'il
pleut dehors, alors rester � la maison et lire un livre, sinon aller
au parc».
En effet, le pr�dicat
«il pleut dehors»
est �valu�, et dans le cas o� il est vrai (s'il pleut
effectivement dehors) la s�quence
«rester(maison);
lire(livre)» sera suivie. Dans le cas o� le
pr�dicat s'av�re faux (si le temps est ensoleill�),
la s�quence «aller au
parc» sera plut�t celle suivie dans le
d�roulement du programme.
- Les mots cl� d'une alternative sont
si,
alors et
sinon.
La forme g�n�rale de l'alternative pr�te
aux �nonc�s suivant le mod�le «si
(condition) alors (op�rations) sinon (op�rations)».
Formes de l'alternative
L'alternative peut se pr�senter sous deux
formes:
- dans la premi�re forme, une ou plusieurs
op�rations sont effectu�es si la condition est vraie, et une ou
plusieurs op�rations sont effectu�es si la condition est
fausse;
- dans la seconde forme, aucune
op�ration n'est pr�vue si la condition est
fausse[2].
Premi�re forme de l'alternative
Exemple de probl�me � r�soudre en
premi�re forme d'alternative: la pause
caf�.
Pseudo-code
|
Morphogramme
|
s'il y a du caf� frais, alors
|
|
On remarquera (avec justesse) que ceci repr�sente une pause caf�
bien incompl�te. Par exemple, s'il n'y a pas de caf� frais lors
de l'�valuation de la condition, on fera du caf�, mais on ne
le boira pas.
Nous reviendrons � une solution plus satisfaisante
(dans tous les sens du mot) sous peu, qui impliquera de composer et
d'imbriquer dans notre algorithme � la fois la s�quence et
l'alternative.
Seconde forme de l'alternative
Exemple de probl�me � r�soudre en seconde
forme d'alternative: le noctambule.
Variante sur la seconde forme d'alternative
La seconde forme d'alternative peut aussi se pr�ter � une s�quence
d'op�rations seulement dans le cas d'une �valuation du pr�dicat
comme faux, avec un r�sultat �quivalent; par contre, on tend
dans ce cas � perdre un peu en �l�gance.
Par exemple:
Pseudo-code
|
Morphogramme
|
si le plancher est propre, alors
|
|
La m�me expression aurait pu s'�crire «si
le plancher est sale, alors passer le balai» et �viter
la suite «si le plancher est propre,
alors (rien) sinon ...».
Le r�sultat aurait �t� le m�me,
toutefois, en terme d'exactitude et de r�alisation de
l'objectif fix�. Au sens algorithmique, les deux variantes
pr�sent�es sont �quivalentes; mais au sens de la
programmatique, nous privil�gierons la premi�re des
deux.
Remarques
- Comme pour les autres structures de base, le
morphogramme de l'alternative comporte un point d'entr�e (en
haut) et un point de sortie (en bas), qui sont
align�s;
- Le losange
repr�sente la condition �valuer. Dans ce cours, nous convenons de
situer la branche du oui (vrai) � droite et la branche du
non (faux) � gauche. Il est toujours possible de d�roger
� cette convention en inscrivant un signe appropri� sur
l'une des sorties lat�rales du losange. Ce signe peut �tre
o ou n, pour oui ou non, ou encore v ou f, pour vrai
ou faux;
- Le pseudo-code d'une alternative
comporte la particularit� suivante: les op�rations sont
pr�sent�es d�cal�es sur la droite (comme pour la
r�p�titive, que nous aborderons sous peu). Cette forme de
d�calage se nomme indentation, et nous reviendrons sous peu sur sa
signification et son
utilit�.
Imbrication des structures de contr�le: �tude de la pause
caf�
Bien entendu, nombreux seront les algorithmes qui combineront
plus d'une structure de contr�le dans la poursuite m�thodique
d'un objectif. Le cas de la pause caf� se pr�te bien �
un petit exercice d'analyse � ce sujet.
Nous avons:
Pseudo-code
|
Morphogramme
|
s'il y a du caf� frais, alors
|
|
Pour s'assurer de jouir des fruits de nos efforts, cet algorithme n'est pas
tout � fait suffisant: en effet, dans le cas o� nous devons
faire nous-m�mes le caf�, l'algorithme n'indique pas que nous
en boirons.
Ainsi, mieux vaut enrichir la s�quence rencontr�e dans le cas
o� le pr�dicat «il y a
du caf� frais» s'av�re faux, surtout si
nous sommes de fervents amateurs du breuvage en question.
Par exemple:
Pseudo-code
|
Morphogramme
|
s'il y a du caf� frais, alors
|
|
Mais on se retrouve � ins�rer une forme de redondance dans
notre algorithme: en effet, peu importe le chemin emprunt�, on finit
dans chaque cas par «prendre un caf�»,
et ce en dernier lieu dans chaque cas.
On pourra tirer avantage de cette r�alisation pour
simplifier notre algorithme:
Pseudo-code
|
Morphogramme
|
s'il n'y a pas de caf� frais, alors
|
|
La beaut� de tout ceci, c'est que la
s�quence et l'alternative se joignent l'une �
l'autre et se combinent tout naturellement. Nous tirerons d'ailleurs
continuellement avantage de cette propri�t�.
Exercices sur l'alternative
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de:
- Lire un
nombre;
- Calculer la valeur absolue de ce
nombre;
- Afficher cette valeur
absolue.
Exercice 9
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de:
- Lire deux
nombres;
- Calculer la somme de ces deux
nombres;
- Calculer la valeur absolue de cette
somme;
- Afficher cette valeur
absolue.
Exercice 10
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de:
- Lire les valeurs de X,
B et C;
- Calculer la valeur absolue de l'expression
BX+C;
- Afficher cette valeur
absolue.
Exercice 11
Vous devez calculer et afficher la note finale d'un �tudiant, ainsi
que la mention succ�s ou �chec. Cet �tudiant
a pass� trois (3) examens
et la note de passage est soixante (60).
La note finale est calcul�e comme �tant la moyenne des examens.
Cr�ez le pseudo-code et le morphogramme de
l'algorithme permettant de r�soudre ce probl�me.
Vous devez calculer et afficher la note finale d'un �tudiant,
ainsi que la mention succ�s ou �chec. Cet �tudiant
a pass� trois (3) examens
ayant les pond�rations suivantes:
- 20% pour le premier;
- 35% pour le deuxi�me;
- 45% pour le troisi�me.
La note de passage est soixante (60%).
La note finale est calcul�e comme �tant la moyenne des examens
en tenant compte de la pond�ration de chaque examen. Cr�ez le
pseudo-code et le morphogramme de l'algorithme permettant de r�soudre
ce probl�me.
Exercice 13
Vous devez calculer et afficher la note finale d'un �tudiant, ainsi
que la mention succ�s ou �chec. Cet �tudiant
a pass� trois (3) examens
et la note de passage est soixante (60).
La note finale est calcul�e comme �tant la moyenne des examens.
Si l'�tudiant obtient une note finale se situant entre 55%
et 60%, il a droit �
un examen de reprise, et obtiendra la note de
60% dans la mesure o� il r�ussit ce dernier.
Cr�ez le pseudo-code et le morphogramme de
l'algorithme permettant de r�soudre ce probl�me.
Exercice 14
�crire le pseudo-code et le morphogramme de l'algorithme
permettant de lire deux (2) nombres
et d'afficher le plus grand des deux. Il ne peut y avoir d'�galit�
entre les nombres.
Exercice 15
�crire le pseudo-code et le morphogramme de l'algorithme
permettant de lire deux (2) nombres
et d'afficher le plus petit des deux. Pr�sumez que ces nombres ne sont
pas �gaux entre eux.
Exercice 16
�crire le pseudo-code et le morphogramme de l'algorithme
permettant de lire trois (3)
nombres et d'afficher le plus grand des trois. Pr�sumez que ces nombres
ne sont pas �gaux entre eux.
Exercice 17
�crire le pseudo-code et le morphogramme de l'algorithme
permettant de lire trois (3)
nombres et d'afficher le plus petit des trois. Pr�sumez que ces nombres
ne sont pas �gaux entre eux.
Exercice 18
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de lire le rayon d'un cercle, ainsi que le choix
de l'utilisateur et imprime:
- soit la circonf�rence du
cercle;
- soit la surface du
cercle.
Le choix de l'utilisateur peut
�tre:
- 1 pour la circonf�rence;
- 2 pour la surface.
Tout autre choix doit g�n�rer un
message d'erreur.
Exercice 19
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de lire la largeur et la longueur d'un rectangle,
ainsi que le choix de l'utilisateur et affiche:
- Soit le p�rim�tre du
rectangle;
- Soit la surface du
rectangle.
Le choix de l'utilisateur peut
�tre:
- 1 pour le p�rim�tre;
- 2 pour la surface.
Tout autre choix doit g�n�rer un
message d'erreur.
Exercice 20
On donne � un vendeur le choix suivant:
- un salaire fixe de 300 $ par
semaine;
- un salaire fixe de 140 $ par
semaine plus 10% de commission
sur les ventes;
- 15% de commission sur les
ventes.
�crire le pseudo-code et le morphogramme de
l'algorithme permettant de lire:
- Le num�ro du
vendeur;
- Le montant des ventes du
vendeur;
et d'afficher:
- Le salaire qui lui reviendrait selon les choix
1, 2,
3;
- Le meilleur choix pour
lui.
La r�p�titive
La structure de contr�le qu'on nomme la
r�p�titive se r�clame de ce qui suit:
- un pr�dicat qu'on
doit �valuer, duquel on peut dire qu'il est vrai ou
qu'il est faux, sans ambigu�t� ni
contradiction;
- un choix, d�pendant
de l'�valuation du pr�dicat, entre une
s�quence d'op�rations � accomplir s'il
s'av�re vrai, et la terminaison de la
r�p�titive;
- un retour au
point de l'�valuation du pr�dicat tant que celui-ci demeure
vrai.
Le principe de revenir au point
d'�valuation du pr�dicat jusqu'� ce que
celui-ci devienne faux �voque l'image d'une boucle; on dira
d'ailleurs souvent des r�p�titives qu'elles sont,
simplement, des boucles.
- Le terme cl� d'une
r�p�titive est tant
que.
La forme g�n�rale de la r�p�titive se pr�te
aux �nonc�s suivant le mod�le «tant
que (condition) faire (op�rations)».
Exemple: surveillance de la cr�me en cours
de cuisson.
Pseudo-code
|
Morphogramme
|
tant que la cr�me ne bout pas
|
|
Le morphogramme d'une r�p�titive est int�ressant car
il permet de bien saisir son aspect dynamique. La figure pr�c�dente
permet de bien repr�senter le mouvement qui anime cette structure.
Le point d'entr�e est en haut. Tant que la condition �
�valuer repr�sent�e par le losange reste vraie, il y
a ex�cution de l'op�ration repr�sent�e par le
rectangle. La ligne qui remonte � gauche indique qu'il faut retourner
�valuer la condition.
Le terme boucle qu'on emploie dans le cas de r�p�titives
d�signe surtout ce mouvement quasi circulaire.
Quand que la condition devient fausse, on quitte la r�p�titive
en passant par la voie � droite du losange pour atteindre le point
de sortie en bas (voir l'exemple de la pile d'examens � corriger, plus
bas).
Dans notre exemple, le pr�dicat � satisfaire est «la
cr�me ne bout pas». Tant que ce pr�dicat
est vrai, l'algorithme indique que la s�quence d'op�rations
� ex�cuter comprend une seule op�ration, soit «brasser
la cr�me».
Bien entendu, s'il y a des s�quence d'op�rations simples comme
«brasser la cr�me», il y en a aussi de plus longues et
de plus complexes.
Prenons par exemple le cas d'un pauvre professeur face � une pile
d'examens � corriger, o� chaque examen comporte quatre questions.
Il est possible, si l'on sait combien d'examens se trouvent dans la pile,
de r�diger un algorithme permettant la correction de chacun d'entre
eux avec une s�quence. Toutefois, cette s�quence pourrait
devenir arbitrairement longue en fonction du nombre d'examens dans la pile.
Toutefois, avec une r�p�titive, nous pouvons
arriver � un algorithme relativement simple et �l�gant pour
r�soudre ce probl�me:
Pseudo-code
|
Morphogramme
|
Tant qu'il reste au moins une copie
inscrire le total sur la 1i�re page
|
|
Question pi�ge: |
si on voulait �crire l'algorithme pr�c�dent �
l'aide d'une s�quence seulement, en sachant qu'il y a cinquante
(50) examens dans la pile,
combien notre s�quence comporterait-elle d'�tapes? |
Remarques
- Le morphogramme indique clairement que cette
structure ne poss�de qu'un seul point d'entr�e (en
haut) et un seul point de sortie (en bas). Il faut toujours prendre soin, lors
de la conception d'un morphogramme de r�p�titive,
d'aligner ces deux points;
- Les
op�rations d'une r�p�titive ne seront pas
ex�cut�es si la condition est fausse au
d�part;
- Au niveau de l'algorithmique
et de certains langages de programmation, il existe des variantes de la
r�p�titive qui seront �tudi�es plus
tard;
- Le pseudo-code d'une
r�p�titive comporte la particularit� suivante: les
op�rations � r�p�ter sont pr�sent�es
d�cal�es sur la droite. Ce d�calage porte le nom
d'indentation.
- Ici,
l'indentation permet de distinguer les op�rations faisant
partie de la r�p�titive de celles qui suivent. L'indentation
est une composante essentielle des principes fondamentaux de la
programmatique.
On peut consid�rer les traits
verticaux ajout�s au pseudo-code comme les marques des niveaux
d'indentation.
Exercices sur la r�p�titive
Exercice 21
�crire le pseudo-code et le morphogramme d'un algorithme
de compte � rebours qui aura pour objet d'�crire successivement
les valeurs enti�res de 10
� 0 inclusivement.
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�crire successivement les nombres pairs de
2 � 50
inclusivement.
Exercice 23
�crire le pseudo-code et le morphogramme d'un algorithme
de compte � rebours qui aura pour objet d'�crire successivement
les valeurs enti�res de 20
� 10 inclusivement.
Exercice 24
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�crire successivement les nombres impairs de
3 � 49
inclusivement.
Exercice 25
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�tablir la somme des nombres impairs de
1 � 99
inclusivement et d'�crire cette somme.
Exercice 26
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�tablir la somme des nombres impairs de
77 � 7
inclusivement et d'�crire cette somme.
Exercice 27
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�tablir la somme des nombres pairs de
64 � 32
inclusivement et d'�crire cette somme.
Exercice 28
�crire le pseudo-code et le morphogramme d'un algorithme
qui aura pour objet d'�tablir la somme des nombres pairs de
2 � 32
inclusivement et des nombres impairs de
33 � 65.
Votre algorithme devra faire afficher cette somme.
Vous devez calculer la moyenne des examens d'un groupe de dix-huit (18)
�tudiants. Chaque �tudiant a pass� trois (3)
examens.
Vous d�sirez obtenir la moyenne de chacun des
�tudiants aux examens, ainsi qu'un commentaire qui variera selon la
moyenne obtenue (voir tableau ci-dessous). Cr�ez le pseudo-code et le
morphogramme de l'algorithme permettant de r�soudre ce
probl�me.
Condition
|
Commentaire
|
0 <= Moyenne < 60 ( 0 �
59)
|
�chec
|
60 <= Moyenne < 70 (60 �
69)
|
Bien
|
70 <= Moyenne < 85 (70 �
84)
|
Tr�s Bien
|
85 <= Moyenne <= 100 (85 �
100)
|
Formidable
|
Exercice 30
Vous devez calculer la moyenne des examens d'un groupe
d'�tudiants. Le nombre d'�tudiants dans le groupe peut varier
selon la demande de l'utilisateur.
Chaque �tudiant a pass� trois (3)
examens dont la pond�ration est la suivante:
- 25% pour le premier;
- 35% pour le deuxi�me;
- 40% pour le troisi�me.
Vous d�sirez obtenir la moyenne aux examens de chacun des �tudiants,
ainsi qu'un commentaire qui variera selon la moyenne obtenue (voir tableau
de la question pr�c�dente). Cr�ez le pseudo-code
et le morphogramme de l'algorithme permettant de r�soudre ce probl�me.
La m�thode du d�veloppement graduel
La m�thode du d�veloppement graduel (ou
d�veloppement progressif) permet de percevoir un probl�me
complexe comme une probl�me plus simple mais compos� de sous
probl�mes. L'id�e derri�re ce concept est de parvenir
� r�soudre le probl�me malgr� son apparence abrupte.
Changer de lunettes
R�soudre un probl�me par voie de d�veloppement graduel
ne signifie pas concr�tement de changer le probl�me rencontr�
pour un autre, du moins pas en changeant sa nature. On a plut�t en
t�te de changer le regard que l'on pose sur le probl�me.
Cela peut se faire de plusieurs mani�res. Les plus
fr�quemment rencontr�es sont:
- formuler diff�remment un probl�me donn� en posant
la question autrement. Certaines questions paraissent tr�s complexes
(ou m�me, � la limite, insolubles) � moins que l'on
les aborde sous un autre angle;
- sch�matiser le probl�me, le traduire, utiliser
un langage diff�rent pour l'exprimer. On peut ainsi concevoir la
r�solution d'un probl�me sous forme de pseudo-code ou de morphogramme,
sans le changer en tant que tel, mais voir graphiquement le flot de notre
m�thode de r�solution de probl�me peut d�finitivement
�tre un pas dans la bonne direction;
- subdiviser le probl�me en modules, soit des sous probl�mes
du probl�me initial qui peuvent se r�soudre en eux-m�mes.
En fait, puisqu'on peut subdiviser un probl�me en modules, et qu'un
module est aussi un probl�me � r�soudre, on peut subdiviser
un module en modules plus simples, et ainsi de suite, dans la mesure o�
il y a une fin � cette subdivision.
La m�thode du d�veloppement graduel s'inspire
de chacune de ces m�thodes, en les int�grant dans un tout coh�rent:
- poser la bonne question est n�cessaire: ai-je toutes les donn�es
pour r�pondre au probl�me qui m'est pr�sent�?
Comprends-je l'�nonc� du probl�me? Sa formulation est-elle
ambigu�? Parfois, la question porte en elle sa r�ponse...;
- la subdivision en modules du probl�me permet de prendre celui-ci
«de haut», pour en voir d'abord l'essentiel et se pr�occuper
seulement par la suite des d�tails;
- la traduction du probl�me en un langage se pr�tant �
un formalisme accru, comme les morphogrammes ou le pseudo-code, aide �
formuler le raisonnement qui m�ne � une solution claire et
pouvant �tre reproduite.
Exercices de d�veloppement graduel
Pour r�soudre les exercices
31 � 35, inspirez-vous
de cet exemple de la technique du d�veloppement
graduel.
Exercice 31
�crire le pseudo-code et le morphogramme d'un algorithme qui aura
pour objet de produire � l'�cran un rectangle de 10
lignes sur 8 colonnes
identique � celui pr�sent� ci-dessous:
********
********
********
********
********
********
********
********
********
********
|
Exercice 32
�crire, en utilisant la technique du d�veloppement graduel,
le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire
� l'�cran un triangle identique � celui pr�sent�
ci-dessous:
*
**
***
****
*****
******
*******
********
*********
|
Exercice 33
�crire, en utilisant la technique du d�veloppement graduel,
le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire
� l'�cran un triangle identique � celui pr�sent�
ci-dessous:
**********
*********
********
*******
******
*****
****
***
**
*
|
Exercice 34
�crire, en utilisant la technique du d�veloppement graduel,
le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire
� l'�cran un triangle identique � celui pr�sent�
ci-dessous:
<****>
<<****>>
<<<****>>>
<<<<****>>>>
<<<<<****>>>>>
<<<<<<****>>>>>>
<<<<<<<****>>>>>>>
<<<<<<<<****>>>>>>>>
<<<<<<<<<****>>>>>>>>>
<<<<<<<<<<****>>>>>>>>>>
|
Exercice 35
�crire, en utilisant la technique du d�veloppement graduel,
le pseudo-code et le morphogramme d'un algorithme qui aura pour objet de produire
� l'�cran un triangle identique � celui pr�sent�
ci-dessous:
*
---
*****
-------
*********
-----------
*************
---------------
*****************
-------------------
|
[1] Nous reviendrons sur la
notion de d�composition lors de l'�tude du
d�veloppement graduel.
[2] ... ou vraie, c'est
selon; les deux formes sont, en fait, �quivalentes entre elles.
[3] Incr�menter est
un anglicisme pour «
augmenter de
1». L'op�ration est tellement commune en informatique
qu'on en est venu � utiliser un terme sp�cifique pour la d�noter.