Connaissance élémentaire des ordinateurs
Apprentissage de la programmation impérative
(sauf pointeurs, récursivité)
Initiation à l'algorithmique et à la conception de programmes
Cours : 5/10, 12/10, 19/10, 26/10, 9/11, 23/11, 7/12
TD/TP : 13 semaines
Pa Partiel le samedi 25 novembre à 13h30.
Ej Examen en janvier
Es Examen de septembreCC 4 tests de 30 minutes effectués pendant les TP.
Chaque test est noté sur 5
La présence aux tests est obligatoireEcrit : NE = max (Ej, (Pa+Ej) / 2)
Note finale janvier : (2NE + CC) / 3
Note finale septembre : max(Es, (2Es + CC) / 3)
Méthodologie de la programmation en langage C, J.-P. Braquelaire,Programmation en C++
Masson, 1994. ISBN 2-225-84353-8
Le langage C++, B. Stroustrup,Et aussi
Addison-Wesley, 1992. ISBN 2-87908-013-4L'essentiel du C++, S.B. Lippman,
Addison-Wesley, 1992. ISBN 2-87908-002-9
Concepts fondamentaux de l’informatique, A. Aho, J. Ullman,
Dunod, 1998. ISBN 2-10-003127-9
flex miniC.lEnsuite, il suffit de compiler les programmes avec la commande
bison -d miniC.y
gcc lex.yy.c miniC.tab.c -o miniC
g-- programme.C
Informatique = Science de l'information
Computer science = science de l'ordinateur
En fait, traitement automatisé de l'information.
Algorithmique : élaboration d'une solution automatiséePour concevoir une solution informatique, il faut savoir ce que l'on peut faire avec un ordinateur.Choix des structures de donnéesProgrammation :
Conception des algorithmestraduction dans un langage compréhensible par l'ordinateur des structures de données et algorithmes
BUS : véhicule les données
CPU : Central Processing Unit
UC : Unité de contrôle
UAL : Unité arithmétique et logique
Registres
Mémoire cache
Mémoire principale : rapide, volatile, stocke le programme et les données
Mémoire secondaire : plus lente, permanente, grande capacité : Disque dur, CDROM, DVD, bandes, ...
Périphériques d'E/S : Clavier, souris, scanner, écran, imprimante, modem, réseau
Bit, octet, mot, Ko, Mo, Go, To
MHz
Matériel : logique numérique, microprogrammes
Langage machine : ajouter 2 entiers, déplacer une donnée, ...
Langage assembleur : représentation symbolique des instructions et données
Langage de programmation de haut niveau : C, C++, Fortran, Java, Lisp, ...
Générateurs d'applications
Gère les ressources de l'ordinateur (mémoire, périphériques, cpu, ...)
langage de commandes : shell, interface graphique
Édition
Compilation
Exécution
Hello world!
PGCD
Puissance
Sierpinski
pas de contraintes syntaxiques
niveau d'abstraction adapté aux problèmes et aux connaissanceslire les données
trier les données
afficher les données triées
CONSTANTE Max=100C++ :
const int Max=100;
TYPE polynôme = tableau de Max réelsC++ :
TYPEDEF float polynome[Max];
FONCTION nomFonction (liste de paramètres) : typeRésultatC++ :
blocPROCEDURE nomProcédure ( liste de paramètres )
bloc
nomType nomFonction ( liste de paramètres )
bloc
PROGRAMME nomProgrammeC++ :
bloc
void main ()
bloc
DEBUT nom Fonction/Procédure/ProgrammeC++ :
déclarations de constantes
déclarations de variables
liste d'instructions
FIN nom Fonction/Procédure/Programme
{ // nom Fonction/Procédure/Programme
déclarations de constantes
déclarations de variables
liste d'instructions
} // nom Fonction/Procédure/Programme
Opérations :
Opérations :
En machine, les données sont codées par une suite de bits et l'ensemble de valeurs est fini
Opérations :
Utilisation des tables de vérité pour évaluer les expressions booléennes.lecture, écriture et (&&), ou (||), implique, équivaut (==), … non (!)
Opérations :
Comparaisons : NxN->Booléens
Littéraux (comment écrire les constantes) :
L'intervalle dépend du nombre de bits utilisés pour coder un entier.
Il y a aussi des entiers non signés
Les calculs sur les entiers sont exacts si on ne dépasse pas la capacité.
Opérations :
Notation virgule flottante : 3.14159 1000. 0.0 -.125
Notation exponentielle : 2.31e+5 1E10 -3.5E-3
En C++, on ne représente qu'un intervalle de réels et avec une certaine précision.
Standard IEEE simple précision sur 32 bits :float : simple précision double : double précision long double : réels longs
Les calculs sur les réels ne sont pas exacts car la précision est limitée.Signe 1 bit Mantisse 23 bits Exposant 8 bits
3 * (1 / 3) - 1 ? 0 !
Opérations :
'a','b',…,'A','B',…,'1','2',…,'!','?',';',…
séquences d'échappement pour les caractères
spéciaux
| \n | newline | \\ | backslash | \b | backspace |
| \r | retour chariot | \? | ? | \f | form feed |
| \t | tabulation | \' | ' | \a | bell |
| \v | tab. verticale | \" | " |
Opérations :
"Bonjour" + " " + "tout le monde."
"Ligne 1\nLigne 2"
En C++, la longueur des chaînes est en général limitée.
Codage "Pascal" : longueur sur 8 bits suivie de la
chaîne
Codage "C" : chaîne suivie d'un caractère
spécial de terminaison (\0).
Il y a des identificateurs réservés : int, float, if, while, …
Il faut choisir soigneusement les identificateurs.
Le compilateur alloue des zones mémoire et mémorise les triplets (nom,type,adresse).
On peut initialiser une variable lors de sa déclaration.
C++ : nomVariable = expression
L'expression doit être compatible avec le type de la variable.
x <- 1.25
x = 1.25;
i <- 5
i = 5;
j <- 3*i*i+2*i+4
j = 3*i*i+2*i+4;
x <- sin(Pi/5)
x = sin(Pi/5);
x <- (1+racine(5))/2
x = (1+sqrt(5))/2;
trouve <- (i<j) et (i>0)
trouve = (i<j) && (i>0);
Certaines instructions modifient cet enchaînement séquentiel.
void sierpinski(int a, int x, int y)
/*
* Dessine un triangle de Sierpinski de cote
"a"
* au point (x,y).
*
*/
{
const int coteMin=4; //
en dessous de cette valeur,
// on dessine un triangle plein.
int i;
if (a < coteMin)
for (i=0;i<=a;i++) Drawline(x,y+i,x+i,y+i);
else {
sierpinski(a/2,x,y);
sierpinski(a/2,x,y+a/2);
sierpinski(a/2,x+a/2,y+a/2);
}
}
si condition alors
liste d'instructions
finsi
programme valeur_absolue
variable y : réel
début programme valeur_absolue
lire y
si y<0 alors y <- -y finsi
ecrire "La valeur absolue est ", y
fin programme valeur_absolue
si condition alors
liste d'instructions 1
sinon
liste d'instructions 2
finsi
programme maximum
variables x,y : réels
début programme maximum
lire x,y
si x<y alors
ecrire "Le maximum est : ", y
sinon
ecire "Le maximum est : ", x
finsi
fin programme maximum
programme trinôme
variables
a,b,c,delta : réels
début programme trinôme
ecrire "donner les coefficients du trinôme"
lire a,b,c
si a=0 alors
ecrire "Ce n'est pas un trinôme"
sinon
delta <- b*b-4*a*c
si delta < 0 alors
ecrire "pas de racine réelle"
sinonsi delta = 0 alors
ecrire "une racine double : ",-b/(2*a)
sinon
ecrire "deux racines réelles : ",
(-b+racine(delta))/(2*a),
(-b-racine(delta))/(2*a)
finsi
finsi
fin programme trinôme
| a | -1 | 0 | 1 |
| affichage | 1 | 2 | 3 |
La présentation améliore la lisibilité mais ne change pas le comportement du compilateur. Pour avoir un programme qui correspond à la présentation ci-dessus, il faut écrire :
| a | -1 | 0 | 1 |
| affichage | 3 | 2 | 1 |
#include <iostream.h>
void main ()
// calcule la date du lendemain
{ // programme mainint jour, mois, annee;
cout << "Calcul du successeur d'une date." << endl;
cout << "Donner la date sous forme de 3 entiers : ";
cin >> jour >> mois >> annee ;// on suppose que la date donnée est valide.
if (jour==31 && mois==12) { // changement d'année
jour=1;
mois=1;
annee=annee+1;
} else if (jour==31) { // changement de mois
jour=1;
mois=mois+1;
} else if (jour==30 &&
(mois==4 || mois==6 || mois==9 || mois==11)) {
jour=1;
mois=mois+1;
} else if (jour==29 && mois==2) {
jour=1;
mois=mois+1;
} else if (jour==28 && mois==2 && annee % 400 != 0 &&
(annee % 4 != 0 || annee % 100 == 0)) {
jour=1;
mois=mois+1;
} else// changement de jour
jour=jour+1;cout << "Le successeur de cette date est : ";
cout << jour << "/" << mois << "/" << annee << endl;} // programme main
Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : 12 10 2000
Le successeur de cette date est : 13/10/2000Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : 31 12 1999
Le successeur de cette date est : 1/1/2000Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : 28 2 2000
Le successeur de cette date est : 29/2/2000Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : 29 2 1900
Le successeur de cette date est : 1/3/1900Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : 30 2 2000
Le successeur de cette date est : 31/2/2000Calcul du successeur d'une date.
Donner la date sous forme de 3 entiers : -5 22 43
Le successeur de cette date est : -4/22/43
#include <iostream.h>
void main ()
// calcule la date du lendemain
{ // programme mainint jour, mois, annee;
cout << "Calcul du successeur d'une date." << endl;
cout << "Donner la date sous forme de 3 entiers : ";
cin >> jour >> mois >> annee ;// on suppose que la date donnée est valide.
if (jour==31 && mois==12) { // changement d'année
jour=1;
mois=1;
annee=annee+1;
} else if ( // changement de mois
(jour==31)
|| (jour==30 &&
(mois==4 || mois==6 || mois==9 || mois==11))
|| (jour==29 && mois==2)
|| (jour==28 && mois==2 && annee % 400 != 0 &&
(annee % 4 != 0 || annee % 100 == 0))
) {
jour=1;
mois=mois+1;
} else // changement de jour
jour=jour+1;cout << "Le successeur de cette date est : ";
cout << jour << "/" << mois << "/" << annee << endl;} // programme main
programme conversion
variable
val : entier initialisé à 0
ch : caractèredébut programme conversion
ecrire "conversion hexadécimal -> décimal"
lire chtant que ch != '.' faire
cas ch parmi
'0' : val <- 16*val+0
'1' : val <- 16*val+1
...
'9' : val <- 16*val+9
'a','A' : val <- 16*val+10
...
'f','F' : val <- 16*val+15
défaut : ecrire "erreur : ", ch , " n'est pas un chiffre hexadecimal"
fin cas
lire ch
fin tant queecrire "La valeur décimale est ", val
fin programme conversion
#include <iostream.h>void main ()
// Conversion hexadécimal -> décimal
{ // programme main
int val=0;
char ch;cout << "Conversion hexadécimal -> décimal." << endl;
cout << "Donner le nombre hexadécimal : ";
cin >> ch;while (ch!='.') {
switch (ch) {
case '0' : val = 16*val+0; break;
case '1' : val = 16*val+1; break;
...
case '9' : val = 16*val+9; break;
case 'a': case 'A': val = 16*val+10; break;
...
case 'f': case 'F': val = 16*val+15; break;
default: cout << "Erreur." << endl;
} // end switch
cin >> ch;
} // end whilecout << "La valeur décimale est : " << val << endl;
} // programme main
Selon que
jour=31 et mois=12 : // changement d'année
jour<-1
mois<-1
annee<-annee+1
jour=31 et mois<12 :// changement de mois
jour<-1
mois<-mois+1
jour=30 et mois dans {4,6,9,11} :
jour<-1
mois<-mois+1
jour=29 et mois=2 :
jour<-1
mois<-mois+1
jour=28 et mois=2 et annee non divisible par 400
et non (annee divisible par 4 mais pas par 100) :
jour<-1
mois<-mois+1
sinon// changement de jour
jour<-jour+1
fin selon
Il y a 4 formes de boucles :
tant que m != 0 faire
r <- n mod m
n <- m
m <- r
fin tant que
Ecrire n
while (n > 0) {
if (n % 2 != 0) p = p
* a;
a = a * a;
n = n / 2;
} // end while
cout << p;
tant que n != 0 faire
p <- p * a
n <- n - 1
fin tant que
Ecrire p
Exécution à la main pour a = 2 et n = -3.
Définir une fonction qui dépend des variables à valeurs dans N Montrer qu'à chaque passage dans la boucle, cette fonction décroît strictement. Montrer que la condition devient fausse en dessous d’une certaine valeur.
Il faut donc faire précéder la boucle d'un test :
si n >= 0 et m >= 0 alors
tant que m != 0 faire
r <- n mod m
n <- m
m <- r
fin tant que
finsi
Ecrire n
si a < 0 ou b < 0 ou (a = 0 et b = 0) alors
Ecrire "Erreur dans les données."
sinon
n <- a
m <- b
// Invariant : pgcd(a,b)=pgcd(n,m) et n>=0 et m>=0
tant que m != 0 faire
// pgcd(a,b)=pgcd(n,m)
et n>=0 et m>0
r <- n mod m
// pgcd(a,b)=pgcd(r,m)
et r>=0 et m>0
n <- m
// pgcd(a,b)=pgcd(r,n)
et r>=0 et n>0
m <- r
// pgcd(a,b)=pgcd(m,n)
et m>=0 et n>0
fin tant que
// pgcd(a,b)=pgcd(n,m)
et n>=0 et m=0
// Donc, n=pgcd(a,b)
Ecrire n
finsi
si n < 0 alors
Ecrire "Erreur dans les données."
sinon
p <- 1
// On note b et m les valeurs
initiales de a et n
// Invariant : b^m = p*a^n
et n>=0
tant que n > 0 faire
// b^m = p*a^n et n>0
si n est impair alors
// b^m = p*a^n et n=2k+1>0
p <- p * a
// b^m = p*a^(2k) et n=2k+1>0
sinon
// b^m = p*a^(2k) et n=2k>0
finsi
// b^m = p*a^(2k) et n>0
et k=n div 2
a <- a * a
// b^m = p*a^k et n>0
et k=n div 2
n <- n div 2
// b^m = p*a^n et n>=0
fin tant que
// b^m = p*a^n et n>=0
et n<=0
// Donc b^m = p
Ecrire p
finsi
faireOn commence par effectuer la liste d'instructions.
liste d'instructions
tant que condition
do {
Liste d'instructions
} while (condition)
écrire "Donner un entier positif"
répéter lire n jusqu'à n >= 0
s <- 0
// Inv : S = 1*1 + … + (i-1)*(i-1) et i <=
n+1
pour i <- 1 à n faire
s <- s + i*i
fin pour
afficher s
écrire "Donner un entier positif"
répéter lire n jusqu'à n >= 0
a <- 1; b <- 1
// Inv : a = F(i) et b = F(i-1) et 1 <=
i <= n
pour i <- 1 à n-1 faire
a <- a + b
b <- a - b
fin pour
afficher a
a=1; b=1;
// Inv : a = F(i) et b = F(i-1) et 1 <=
i <= n
for (i=1; i<n; i++) {
a = a+b;
b = a-b;
}
cout << a;
// Inv : 1 <= i <= j <= N et t trié
et
// x dans t si et seulement si x dans t[i..j]
tant que i < j faire
// 1 <= i < j <=
N et t trié et ...
m <- (i+j) div 2
// 1 <= i <= m <
j <= N et t trié et ...
si x > t[m] alors
// 1 <= i <= m <
j <= N et t trié et
// x dans t si et seulement
si x dans t[m+1..j]
i <- m+1
// Inv
sinon
// 1 <= i <= m <
j <= N et t trié et
// x dans t si et seulement
si x dans t[i..m]
j <- m
// Inv
finsi
// Inv
fin tant que
// Inv et i >= j
// donc : 1 <= i = j <= N et t trié
et
// x dans t si et seulement si x = t[i]
si x = t[i] alors
afficher x, " se trouve en position ", i
sinon
afficher x, " ne se trouve pas dans le tableau"
finsi
Diviser pour régnerPour cela, une procédure ou fonction doit être
procédure échange(référence x,y:réel)
// Echange les valeurs de x et y
Dans une fonction, il doit y avoir une instruction
lireTab(t,1,N)
trierTab(t,1,N)
écrireTab(t,1,N)
début pgcd
tant que b ? 0 faire
c <- a Mod b
a <- b
b <- c
fin tant que
retourner a
fin pgcd
p <- pgcd(2*n+1,3*m-2)
afficher n, m, p
a <- 48; b <- 21; p <- a/pgcd(a,b); q <- b/pgcd(a,b)
afficher "fraction irréductible : ", p, q
lire n,m
si pgcd(n,m)=1 alors
afficher n, " et ", m, " sont premiers entre
eux"
fsi
début échange
z <- x; x <- y; y <- z
fin échange
a <- 48; x <- 21; z <- 12; échange(a,x)
afficher a, x, z
x <- 48; y <- 21; z <- 12;
échange(2*x,3*y) // Erreur
procédure P(valeur x:entier, référence y:entier)
variables
z:entier
n: réels // La
variable n masque la constante n
début P
y <- 3*x+2
z <- 2
n <- 0.3 // OK. Ici n est une variable
réelle
b <- 8 // Erreur : b n'existe pas ici
fin P // fin de la portée de x,y,z,n
programme Q
variables
a,b : entiers
x : réel
début Q
a <- n // il s'agit de la constante n
y <- 8 // erreur : la portée de
y et z
z <- 2*a+b // se limite à la procédure
P
x <- 0.5 // OK. C'est le x de Q
fin Q
début P
z <- y div 2; y <- x*x; x <- y*y + z*z
fin P
programme Test
variables a,b,x,y,z : entiers
début Test
a <- 3; b <- 0; x <- 5; y <- -2; z <- 8
P(a,b)
afficher a, b, x, y, z
a <- 4; P(a,a)
afficher a, b, x, y, z
P(x,y)
afficher x, y, z
x <- 2; z <- 3; P(x,y)
afficher x, y, z
fin Test
procédure échange(référence x,y:réel)
// Echange les valeurs de x et y
variable z:réel
début échange
z <- x; x <- y; y <- z
fin échange
fonction posmin(valeur t:Tab, valeur i,j:entier):entier
// Retourne la position du minimum de t[i..j]
// On doit avoir 1 <= i <= j <=
dimension(t)
variable k:entier
début posmin
// Invariant : t[i] <= t[i_0..k-1] et
k <= j+1
// i_0 dénote la valeur initiale de
i
pour k <- i+1 à j faire
si t[k] < t[i] alors i <- k fsi
fin pour
retourner i
fin posmin
procédure tri(référence t:Tab, valeur i,j:entier)
// tri de t[i..j]
// On doit avoir 1 <= i <= j <=
dimension(t)
variable k:entier
début tri
// Invariant : t[i..k-1] est trié
et
// t[1..k-1] <= t[k..j] et i <= k <=
j
pour k <- i à j-1 faire
échange(t[k],t[posmin(t,k,j)])
fin tri
programme tri_sélection
variable a:Tab
début tri_sélection
lire a
tri(a,1,N)
afficher a
fin tri_sélection
La déclaration de paramètre
Tab t
correspond à une transmission
par référence.
Ne pas utiliser la déclaration
Tab &t
Pour interdire la modification
d'un paramètre tableau par une procédure ou une fonction
on utilise la déclaration de paramètre
const Tab t
Il s'agit toujours d'une transmission
par référence (pas de copie) mais le compilateur interdit
toute modification du paramètre.
Remarque : on peut aussi utiliser la déclaration
const pour un paramètre d'un autre type.
const double &x
Le paramètre est transmis par référence
(pas de copie) mais ne peut pas être modifié.
Ceci est utile pour éviter de copier un gros
paramètre (e.g. une structure) qui ne doit pas être modifié.
void echange(float &x, float &y)
// Echange les valeurs de x et y
{ // echange
float z;
z = x; x = y; y = z;
} // echange
int posmin(const Tab t, int i, int
j)
// Retourne la position du minimum de t[i..j]
{ // posmin
int k;
for(k=i+1;k<=j;k++)
if (t[k] < t[i]) i <- k;
return i;
} //posmin
void tri(Tab t, int i, int j)
// tri de t[i..j]
{ // tri
int k;
for(k=i;k<j;k++)
echange(t[k],t[posmin(t,k,j)]);
} // tri
void lireTab(Tab t, int i, int j)
// lecture de t[i..j]
{ // lireTab
int k;
for(k=i;k<=j;k++)
cin >> t[k];
} // lireTab
void ecrireTab(const Tab t, int i,
int j)
// écriture de t[i..j]
{ // ecrireTab
int k;
for(k=i;k<=j;k++)
cout << t[k];
} // ecrireTab
void main()
{ // tri_sélection
Tab a;
lireTab(a,1,N);
tri(a,1,N);
ecrireTab(a,1,N);
} // tri_sélection
Tdate = structure
jour : entier
mois : chaîne
de caractères
année : entier
fin structure
Tfiche = structure
nom, prénom :
chaîne de caractères
né_le : Tdate
adresse : chaîne
de caractères
fin structure
TabCoef = tableau de 100 réels
Tpolynôme = structure
degré : entier
coef : TabCoef
fin structure
variables
x,y : Tcomplexe
date : Tdate
fiche : Tfiche
p : Tpolynôme
début test
lire x.re, x.im, y.re, y.im
afficher "somme : ", x.re + y.re, x.im + y.im
lire date.jour, date.mois
si date.jour>30 et date.mois = "novembre" alors
afficher "date erronée"
finsi
lire fiche.nom, fiche.né_le.jour
répéter lire p.degré jusqu'à 0 <= p.degré <= 100
pour i <- 1 à p.degré faire
lire p.coef[i]
finpour
fin test
typedef struct {
float re, im;
} Tcomplexe;
typedef struct {
int jour;
string mois;
int annee;
} Tdate;
typedef struct {
string nom, prenom;
Tdate ne_le;
string adresse;
} Tfiche;
typedef float TabCoef[100];
typedef struct {
int degre;
TabCoef coef;
} Tpolynome;
void main () {
Tcomplexe x,y;
Tdate date;
Tfiche fiche = {"Frigand", "Elyse",
{20,"mai",1970},
"Paris"};
Tpolynome p;
int i;
cin >> x.re >> x.im >> y.re >> y.im;
cout << "somme : " << x.re + y.re << x.im + y.im
<< endl;
cin >> date.jour >> date.mois;
if (date.jour>30 && date.mois == "novembre")
cout << "date erronée" <<
endl;
do cin >> p.degre; while (p.degre<0 || p.degre>100);
for(i=1;i<=p.degre;i++)
cin >> p.coef[i];
}
const int N=10;
typedef struct {
string nom; // nom étudiant
int numet; // numéro
étudiant
int rang; // rang à
l'examen
} fiche;
// un tableau de structures sera notre base
de données
typedef fiche base[N];
void main()
{ // initialisation de la base
de données:
// une entrée par
case du tableau;
// les cases étant
des sructures,
// une entrée par
champ de la structure
base b = {{"Toto",1,3},{"Titi",2,4},{"Tata",3,5},
{"Tutu",4,1},{"Tete",5,2},{"Toto2",6,8},
{"Titi2",7,9},{"Tata2",8,10},
{"Tutu2",9,6},{"Tete2",10,7}};
base bc; /* bc sera notre base classée
*/
int i;
// écriture de la
base avant classement
for (i=0;i<N;i++){
cout << b[i].nom
<< "\t" << b[i].numet << "\t";
cout << b[i].rang
<< endl;
}
// classement
for (i=0;i<N;i++) bc[b[i].rang-1]=b[i];
// écriture de la
base classée
cout << endl << "Base classée."
<< endl << endl;
for (i=0;i<N;i++){
cout << bc[i].nom
<< "\t" << bc[i].numet << "\t";
cout << bc[i].rang
<< endl;
}
}
type tour = énumération (Gauche, Droite, Milieu)procédure déplace( valeur n: entier; valeur orig,dest,tmp: tour)
// déplace une tour de n disques de orig à dest
// en utilisant tmp comme tour auxiliaire
début déplace
si n = 1 alors
imprime "déplacer un disque de " orig " à " dest
sinon
déplace(n-1, orig, tmp, dest)
imprime "déplacer un disque de " orig " à " dest
déplace(n-1, tmp, dest, orig)
finsi
fin déplaceprogramme Hanoi
variables ndisques: entier
début Hanoi
lire ndisques
déplace(ndisques, Gauche, Droite, Milieu)
fin Hanoi
#include <iostream.h>
#include <string>typedef enum tour {Gauche, Droite, Milieu};
string chaine(tour t) {
if (t==Gauche)
return "Gauche";
else if (t==Droite)
return "Droite";
else
return "Milieu";
}void deplace(int n, tour orig, tour dest, tour tmp)
// déplace une tour de n disques de orig à dest
// en utilisant tmp comme tour auxiliaire
{ // deplace
if (n == 1)
cout << "déplacer un disque de " << chaine(orig)
<< " à " << chaine(dest) << endl;
else {
deplace(n-1, orig, tmp, dest);
cout << "déplacer un disque de " << chaine(orig)
<< " à " << chaine(dest) << endl;
deplace(n-1, tmp, dest, orig);
}
} // deplacevoid main () Hanoi
{ int nb;
cout << "Combien de disques?"; cin >> nb;
deplace(nb,Gauche,Droite,Milieu);
}