Algorithmique - Pearson...Exercice 1 : Conversion des francs en euros Énoncé Écrivez l’algorithme qui convertit en euros une somme exprimée en francs. Le résultat en euros sera

© 2013 Pearson France – Algorithmique. Applications aux langages C, C++ et Java

Algorithmique. Applications aux langages C, C++ et Java

Jean-Michel LÉRY

ISBN : 978-2-7440-7672-5

Exercices supplémentaires

Chapitre 1 – Les traitements logiques

L’exercice 1 montre comment obtenir un arrondi par une solution analytique.

Exercice 1 : Conversion des francs en euros

Énoncé

Écrivez l’algorithme qui convertit en euros une somme exprimée en francs. Le résultat en euros sera arrondi à la deuxième décimale. Le taux de conversion est de 6,55957 francs pour un euro, et la seule fonction algorithmique

dont on dispose pour effectuer l’arrondi est partie_entière(x) qui retourne la valeur entière strictement inférieure

au nombre réel x (la partie entière de 2,6 est 2). Le problème sera décomposé en deux sous-problèmes : trouver

comment obtenir un arrondi entier à partir de la fonction partie_entière(), puis généraliser le calcul pour qu’il

effectue un arrondi à la deuxième décimale.

1. Faites l’analyse du problème de l’arrondi entier en travaillant sur des exemples de nombres réels. Pour cela, mettez en correspondance une série de nombre réels (2,0, puis 2,1, puis 2,2, etc.) avec leur arrondi entier connu, et déduisez-en le calcul algorithmique générique qui permet de passer de la

valeur réelle à son arrondi.

2. Modifiez ce calcul pour effectuer l’arrondi à 2 décimales près, et écrivez l’algorithme de conversion des francs en euros qui utilise cette méthode.

Solution

1. Cet exercice montre que l’analyse des données est très importante. La plupart des développeurs auront tendance à proposer une solution basée sur leurs connaissances techniques, en comparant la partie décimale à la valeur 0,5. Si la partie décimale est inférieure à 0,5, l’arrondi correspond à la partie entière ; sinon, l’arrondi correspond à la partie entière augmentée de la valeur 1. Cette solution construite autour d’un test s’écrit :

pent partie_entière(x)

pdéci x - pent

Si (pdéci < 0,5) alors

Arrondi pent

Sinon

Arrondi pent + 1

FinSi

Or un test est plus coûteux en temps d’exécution qu’un simple calcul arithmétique. Il est donc préférable d’étudier les données avant de se lancer dans une solution technique, comme le propose la figure 1.1.

En prenant une suite de nombres réels consécutifs, et en mettant en correspondance leur arrondi entier connu, on peut faire le constat suivant. L’arrondi change à partir du nombre dont la décimale est 0,5 (ce nombre est 2,5 pour la suite présentée). Si on ajoute simplement 0,5 à la valeur centrale 2,5, on obtient le

résultat attendu (schéma de gauche de la figure). Généralisons ce calcul en ajoutant 0,5 à tous les nombres réels présentés et regardons le résultat obtenu (schéma de droite de la figure 1.1). Ce résultat est presque celui qui est attendu, à la partie décimale près. Il suffit donc de ne conserver que la partie entière. Le calcul précédent basé sur un test se réécrit ainsi beaucoup plus simplement :

Arrondi partie_entière(x+0,5)

2

L’analyse des données, même dans les cas élémentaires comme celui qui est présenté, ne doit jamais être négligée. Elle fournit souvent des solutions plus simples à programmer.

Figure 1.1

Analyse de l’arrondi entier d’un réel.

2. Pour obtenir un arrondi à deux décimales près en utilisant la formule précédente, il suffit de multiplier le nombre réel par 100, d’appliquer la partie entière au résultat obtenu, puis de diviser la valeur résultante par 100. La syntaxe algorithmique de ce calcul est :

Arrondi_décimal (partie_entière((x*100)+0,5))/100

Voici la décomposition de ce calcul sur le nombre 15,2449017 (conversion de 100 francs en euros). La valeur obtenue est 15,24.

15,2449017 1524,49017 1524,49017 +0,5 1524,99017 1524 1524/100 15,24

L’algorithme conv_francs_euros utilise ce calcul pour convertir en euros une somme exprimée en francs.

Programme conv_francs_euros

Déclarations

Constante TAUX = 6,55957

Variables Euros, Francs en Réels

Début

Écrire("Entrez la valeur en Francs (ex 97.5) : ")

Lire(Francs)

Euros (partie_entière((Francs/TAUX)*100)+0.5))/100

Écrire ("Valeur en Euros :",Euros);

Fin

Les programmes sources C, C++ et Java téléchargeables qui implémentent cet algorithme se nomment

respectivement : conv_francs_euros.c, conv_francs_euros.cpp, conv_francs_euros.java.

La commande de compilation pour les programmes C et C++ est :

$ make conv_francs_euros

Voici un exemple d’exécution de ce programme :

$ conv_francs_euros

Entrez la valeur en Francs (ex 97.5) : 100

Valeur en euros : 15.24

La commande de compilation pour le programme Java est :

$ javac conv_francs_euros.java

La syntaxe pour exécuter le programme compilé Java est :

$ java conv_francs_euros


3

Chapitre 2 – Les traitements logiques

Les exercices proposés étudient la conception des boucles. L’exercice 4 porte sur la complexité algorithmique et montre son incidence directe sur le temps de calcul. Les exercices 9 à 12 traitent du problème mathématique du dénombrement.

Exercice 1 : Boucles POUR imbriquées

Énoncé

Écrivez un programme qui affiche les N premières tables de multiplication. Le programme demandera la valeur N à l’utilisateur. Il utilisera deux boucles POUR imbriquées : la première parcourra les numéros des tables, et la seconde effectuera la multiplication de 1 à 10 pour une table donnée. L’affichage sera de la forme :

Table de 1: 1 2 3 4 5 6 7 8 9 10

Table de 2: 2 4 6 8 10 12 14 16 18 20

...

Solution

La première boucle POUR utilise la variable table comme compteur. La boucle s’exécute de 1 à N. La seconde

boucle interne s’exécute 10 fois pour chaque valeur de N.

« PSEUDO-CODE »

Programme tables_de_multiplication

Déclarations

Variables table,i, N en Entier

Début

Écrire("Entrez le numéro de la dernière table :")

Lire(N)

Pour table variant de 1 à N Faire

Écrire("Table de ",table)

Pour i variant de 1 à 10 Faire

Écrire(table*i)

FinPour

FinPour

Fin


respectivement : tables_de_multiplication.c, tables_de_multiplication.cpp, tables_de_multiplication.java.


$ make tables_de_multiplication


$ tables_de_multiplication

Entrez le numéro de la dernière table :3

Table de 1: 1 2 3 4 5 6 7 8 9 10

Table de 2: 2 4 6 8 10 12 14 16 18 20

Table de 3: 3 6 9 12 15 18 21 24 27 30


$ javac tables_de_multiplication.java


$ java tables_de_multiplication

Exercice 2 : Détermination d’un nombre factoriel

Énoncé

Un entier positif x est un nombre factoriel s’il existe un autre entier y, tel que x = y!. Faites un programme qui détermine si le nombre entré par l’utilisateur est un nombre factoriel. Réécrivez le calcul de la factorielle présenté à l’exercice 2 du chapitre 2 du livre, en une fonction fact().

4

Solution

L’algorithme suivant utilise la fonction fact(j) qui retourne le résultat du calcul de la factorielle de l’entier j. Une

boucle principale teste les factorielles successives 2!, 3!, …, et compare le résultat au nombre entier demandé à

l’utilisateur, i. La boucle s’arrête quand la factorielle calculée dépasse le nombre i. Comme le nombre d’itérations

n’est pas connu à l’avance, la boucle utilisée est l’instruction TANT QUE.

« PSEUDO-CODE »

Programme nombre_factoriel

Déclarations

Variables nb, fact, j en Entier

Variable trouvé en Booléen

Début

Écrire("Entrez un nombre entier positif :")

Lire(nb)

fac 1

trouvé FAUX

j 0

Tant que ((fact


5

Exercice 3 : Calcul d’une fonction sin(x)

Énoncé

Cet exercice propose de réécrire le calcul de fonctions mathématiques à partir du développement en séries entières d’après la méthode de Taylor-Mac-Laurin. Ces mathématiciens ont montré que toute fonction peut s’écrire comme une suite d’additions (ou de soustractions) de facteurs de x. Ainsi, sinus(x) correspond au calcul :

sin(x) = x-x3

3!+

x5

5!-

x7

7!+...+ (-1)n

x2n+1

(2n+1)!

Écrivez l’algorithme qui calcule sinus(x), x étant indiqué en radians (valeur entre 0 et 2 ). La boucle de traitement devra s’arrêter quand la précision obtenue sera suffisamment grande, ce qui se traduit par une valeur très faible du nouveau facteur de x. La précision sera définie à la 15

e décimale.

Solution

La boucle de traitement est une boucle TANT QUE, puisqu’on ne connaît pas le nombre de calculs nécessaires pour obtenir le résultat. La boucle continue tant que le nouveau facteur calculé est supérieur à la précision voulue. La précision définie à la 15

e décimale correspond à la valeur 0,000000000000001. Dans la boucle TANT QUE, le

nouveau facteur est calculé séparément, car il sert de critère d’arrêt à la boucle. Sa valeur initiale (en dehors de la

boucle) est fixée arbitrairement afin de démarrer la boucle. L’alternance des + et des – est obtenue par le calcul (–

1)n qui multiplie le facteur calculé précédemment, pour obtenir le nouveau terme à additionner aux résultats

précédents. Le premier calcul (–1)0 donne +1 ; le deuxième, (–1)

1, donne –1 ; le troisième, (–1)

2, donne +1, etc.

« PSEUDO-CODE »

Programme sinus

Déclarations

Variables x, res, facteur, terme, précision en Réel

Variable n en Entier

Début

Écrire("Entrez la valeur de x:")

Lire(x)

précision 0,000000000000001

Écrire("--- calcul par séries entières ---")

res 0

n 0

facteur 9999

Tant que (facteur>précision) Faire

facteur (x**((2*n)+1))/factorielle((2*n)+1)

terme ((-1)**n)*facteur

res res + terme

Écrire(n,": sinus= ",res, " terme=",terme)

n n+1

FinTantQue

Fin

// --- fonction factorielle

Fonction factorielle(N)

Déclarations

Paramètres N en Entier

Variables i, résultat en Entier

Début

résultat 1

Pour i variant de 1 à N Faire

résultat résultat * i

FinPour

Retourner résultat

Fin


respectivement : sinus.c, sinus.cpp, sinus.java.

La commande de compilation pour le programme C est :

$ cc -o sinus sinus.c -lm

6

La commande de compilation pour le programme C++ est :

$ make sinus

Voici un exemple d’exécution de ce programme issu du programme source C :

$ sinus

Entrez la valeur de x : 0.5

sin(0.50)= +0.479425538604203 (librairie C)

--- calcul par séries entières ---

0: sinus= +0.500000000000000 terme= +0.500000000000000

1: sinus= +0.479166666666667 terme= -0.020833333333333

2: sinus= +0.479427083333333 terme= +0.000260416666667

3: sinus= +0.479425533234127 terme= -0.000001550099206

4: sinus= +0.479425538616416 terme= +0.000000005382289

5: sinus= +0.479425538604183 terme= -0.000000000012232

6: sinus= +0.479425538604203 terme= +0.000000000000020

7: sinus= +0.479425538604203 terme= -0.000000000000000


$ javac sinus.java


$ java sinus

Entrez la valeur de x : 0,5

sin(0,50)= +0,479425538604203 (librairie JAVA)


0: sinus= +0,500000000000000 terme= +0,500000000000000

1: sinus= +0,479166666666667 terme= -0,020833333333333

2: sinus= +0,479427083333333 terme= +0,000260416666667

3: sinus= +0,479425533234127 terme= -0,000001550099206

4: sinus= +0,479425538616416 terme= +0,000000005382289

5: sinus= +0,479425538604183 terme= -0,000000000012232

6: sinus= +0,479425538604203 terme= +0,000000000000020

7: sinus= +0,479425538604203 terme= -0,000000000000000

Exercice 4 : Les N premiers nombres premiers

Cet exercice fait suite à l’exercice 4 du livre sur la complexité algorithmique.

Énoncé

Modifiez le programme premier2 pour afficher la liste des N premiers nombres premiers. La valeur N est

demandée à l’utilisateur. Utilisez une fonction est_nbpremier() qui effectue la détection du nombre premier passé

en argument. Cette fonction sera construite à partir de la dernière version de l’algorithme du nombre premier, présentée à l’exercice 4 du livre.

Solution

La boucle principale gère un compteur j qui progresse de 1 en 1. La fonction est_nbpremier() détecte si j, qui est

passé en argument, est un nombre premier. À chaque détection d’un nombre premier, un compteur nbtrouvé est

incrémenté. La boucle s’arrête quand ce compteur atteint la valeur N fournie par l’utilisateur.

« PSEUDO-CODE »

Programme premier3

Déclaration

Variables N, j, nbtrouvé en Entier

Début

nbtrouvé 0

j 1

Écrire("Combien de nombres premiers à trouver ? ")


7

Lire(N)

Tant que (nbtrouvé < N) Faire

j j+1

Si (est_nbpremier(j)) Alors

Écrire(j)

nbtrouvé nbtrouvé+1

FinSi

FinTantQue

Fin

// --- fonction est_premier

Fonction est_nbpremier(nb)

Déclarations

Paramètres nb en Entier

Variables reste, nb_itérations, i,limite en Entier

Variable trouvé en Booléen

Début

// partie entière de la racine carrée+1

limite partie_entière(racine_carrée(nb)+1)

trouvé FAUX

Si (nb 2) Alors // on exclut 2 qui est premier

// on retire le cas des nombres pairs

reste nb MOD 2

Si (reste = 0) Alors

trouvé VRAI

Sinon

// on teste tous les diviseurs impairs

i 3

Tant que ((NON trouvé) ET (i

8

gagner quelques secondes, ce n’est rien comparé au gain provenant de l’algorithme. Si on utilise la version de l’algorithme qui teste tous les diviseurs impairs jusqu’au nombre –1, la détection des 200 000 premiers nombres premiers sur le Macintosh Intel i7 prend alors 9 minutes et 8 secondes, au lieu des 0,96 seconde avec l’algorithme qui arrête la recherche à la racine carrée du nombre. Le gain avec la dernière version de l’algorithme est de plus de 9 minutes ! L’algorithmique est fondamentale. C’est la seule méthode qui permet de réduire efficacement le temps de traitement de l’information.

Exercice 5 : Calcul d’une fonction cos(x)

Énoncé

Comme l’exercice 3, cet exercice propose de réécrire le calcul de la fonction cosinus à partir du développement en séries entières d’après la méthode de Taylor-Mac-Laurin. Ainsi, cosinus(x) correspond au calcul :

cos(x) =1-x2

2!+

x4

4!-

x6

6!+...+ (-1)n

x2n

(2n)!

Écrivez l’algorithme qui calcule cosinus(x), x étant indiqué en radians (valeur entre 0 et 2 ). La boucle de traitement devra s’arrêter quand la précision obtenue sera suffisamment grande, ce qui se traduit par une valeur très faible du nouveau facteur de x. La précision sera définie à la 15

e décimale.

Solution

La boucle de traitement TANT QUE continue tant que le nouveau facteur calculé est supérieur à la précision

définie à la 15e décimale, soit la valeur 0,000000000000001. Dans la boucle TANT QUE, le nouveau facteur est

calculé séparément, car il sert de critère d’arrêt à la boucle. Sa valeur initiale (en dehors de la boucle) est fixée arbitrairement afin de démarrer la boucle. L’alternance des + et des – est obtenue par le calcul (–1)

n qui multiplie le

facteur calculé précédemment, pour obtenir le nouveau terme à additionner aux résultats précédents. Le premier

calcul (–1)0 donne +1 ; le deuxième, (–1)

1, donne –1 ; le troisième (–1)

2 donne +1, etc.

« PSEUDO-CODE »

Programme cosinus

Déclarations

Variables y, x, res, facteur, terme, précision en Réel


Début


Lire(x)

précision 0,000000000000001


res 0

n 0

facteur 9999


facteur ← (x**(2*n))/factorielle((2*n))

terme ((-1)**n)*facteur

res res + terme

Écrire(n,": cosinus= ",res, " terme=",terme)

n n+1

FinTantQue

Fin



Déclarations



Début

résultat 1



FinPour


9

Retourner résultat

Fin


respectivement : cosinus.c, cosinus.cpp, cosinus.java.


$ cc -o cosinus cosinus.c -lm


$ make cosinus


$ cosinus


cos(0.50)= +0.877582561890373 (librairie C)


0: cosinus= +1.000000000000000 terme= +1.000000000000000

1: cosinus= +0.875000000000000 terme= -0.125000000000000

2: cosinus= +0.877604166666667 terme= +0.002604166666667

3: cosinus= +0.877582465277778 terme= -0.000021701388889

4: cosinus= +0.877582562158978 terme= +0.000000096881200

5: cosinus= +0.877582561889864 terme= -0.000000000269114

6: cosinus= +0.877582561890373 terme= +0.000000000000510

7: cosinus= +0.877582561890373 terme= -0.000000000000001


$ javac cosinus.java


$ java cosinus


cos(0,50)= +0,877582561890373 (librairie JAVA)


0: cosinus= +1,000000000000000 terme= +1,000000000000000

1: cosinus= +0,875000000000000 terme= -0,125000000000000

2: cosinus= +0,877604166666667 terme= +0,002604166666667

3: cosinus= +0,877582465277778 terme= -0,000021701388889

4: cosinus= +0,877582562158978 terme= +0,000000096881200

5: cosinus= +0,877582561889864 terme= -0,000000000269114

6: cosinus= +0,877582561890373 terme= +0,000000000000510

7: cosinus= +0,877582561890373 terme= -0,000000000000001

Exercice 6 : Calcul d’une fonction exp(x)

Énoncé

Réécrivez le calcul de la fonction exponentielle à partir du développement en séries entières d’après la méthode de Taylor-Mac-Laurin. Ainsi, exponentielle(x) correspond au calcul :

exp(x) =x0

0!+

x1

1!+

x2

2!+...+

xn

n!

Écrivez l’algorithme qui calcule exponentielle(x). La boucle de traitement devra s’arrêter quand la précision obtenue sera suffisamment grande, ce qui se traduit par une valeur très faible du nouveau facteur de x. La précision sera définie à la 15

e décimale.

Solution

La boucle de traitement TANT QUE continue tant que le nouveau facteur calculé est supérieur à la précision

définie à la 15e décimale, soit la valeur 0,000000000000001. Dans la boucle TANT QUE, le nouveau facteur est

calculé séparément, car il sert de critère d’arrêt à la boucle. Sa valeur initiale (en dehors de la boucle) est fixée arbitrairement afin de démarrer la boucle.

10

Il n’y a pas de changement de signe dans cette série, le terme à additionner est exactement identique au facteur

qui sert de critère d’arrêt. La variable terme est donc superflue, elle est conservée par analogie aux algorithmes

des sinus et cosinus.

« PSEUDO-CODE »

Programme exponentielle

Déclarations

Variables y, x, res, facteur, terme, précision en Réel


Début


Lire(x)

précision 0,000000000000001


res 0

n 0

facteur 9999


facteur ← (x**n)/factorielle(n)

terme ← facteur

res res + terme

Écrire(n,": exponentielle= ",res, " terme=",terme)

n n+1

FinTantQue

Fin



Déclarations



Début

résultat 1



FinPour

Retourner résultat

Fin


respectivement : exponentielle.c, exponentielle.cpp, exponentielle.java.


$ cc -o exponentielle exponentielle.c -lm


$ make exponentielle


$ exponentielle


exp(3.40)= +29.964100047397011 (librairie C)


0: exponetielle= +1.000000000000000 terme= +1.000000000000000









11
























$ javac exponentielle.java


$ java exponentielle


exp(3,40)= +29,964100047397010 (librairie JAVA)


0: exponentielle= +1,000000000000000 terme= +1,000000000000000






























12

Exercice 7 : Ébauche d’un sapin

Énoncé

Écrivez un programme qui dessine le début d'un sapin (triangle) selon le nombre de lignes (N) saisies au clavier. Le triangle sera placé au milieu de l'écran (de 80 colonnes). Vous tracerez des espaces et des étoiles sur chaque ligne puis vous passerez à la ligne suivante. Voici l’affichage demandé pour N = 3, 4 ou 5.

N=3 N=4 N=5

* * *

*** *** ***

***** ***** *****

******* *******

*********

Solution

Le programme triangle dessine un triangle centré au milieu d’un écran. Il trace des espaces puis des étoiles sur

chaque ligne puis passe à la ligne suivante. L’analyse de ce problème montre que le nombre d’espaces et d’étoiles à tracer sur chaque ligne dépend uniquement du numéro de la ligne. Sur la i

e ligne, on trace MILIEU-i espaces,

puis (2*i) – 1 étoiles. MILIEU vaut 40 pour un écran de 80 colonnes.

« PSEUDO-CODE »

Programme triangle

Déclarations

Constante MILIEU = 40

Variables nbespaces, nbétoiles, N, ligne en Entier

Début

Écrire("Entrez le nombre de lignes : ")

Lire(N)

// tracé de toutes les lignes

Pour ligne variant de 1 à N Faire

// pour chaque ligne

// --- dessine MILIEU-ligne espaces ---

Pour nbespaces variant de 1 à MILIEU-ligne Faire

Écrire(" ")

FinPour

// --- dessine (2*ligne)-1 étoiles ---

Pour nbétoiles variant de 1 à (2*ligne)-1 Faire

Écrire("*")

FinPour

// --- saut de lignes ---

Écrire(SAUT_DE_LIGNE)

FinPour

Fin


respectivement : triangle.c, triangle.cpp, triangle.java.


$ make triangle


$ triangle

Entrez le nombre de lignes : 5

*

***

*****

*******

*********


13


$ javac triangle.java


$ java triangle

Exercice 8 : Un sapin complet

Énoncé

À partir de l’exercice précédent qui dessine un triangle d’étoiles, concevez un programme qui dessine un sapin

complet. Le programme utilisera une procédure triangle(), qui dessinera un seul triangle d’étoiles. Cette

procédure sera appelée dans une boucle qui s’exécutera autant de fois qu’il y aura d’étages au sapin. Ce nombre sera fourni par l’utilisateur. Le sapin sera terminé par un rectangle d’étoiles formant le pied du sapin, dessiné par une procédure rectangle. Si l’utilisateur demande un sapin de trois étages, le dessin attendu sera le suivant :

*

***

*****

*******

***

*****

*******

*********

*****

*******

*********

***********

***

***

***

Solution

Le programme sapin appelle la procédure triangle(), qui trace des triangles de quatre lignes, dans une boucle de

Nbétages.

Le premier appel à la procédure trace un triangle de la ligne N° 1 (contenant une étoile) à la ligne N° 4 (contenant sept étoiles). Le deuxième appel trace un triangle de la ligne N° 2 (contenant trois étoiles) à la ligne N° 5 (contenant neuf étoiles), etc.

Une fois tous les étages du sapin dessinés, la procédure rectangle() est appelée pour tracer le pied du sapin.

« PSEUDO-CODE »

// ---- programme sapin ----

Programme sapin

Déclarations

Constante MILIEU = 40

Variables Nbétages , i ,début, fin en Entier

Début

Écrire("Entrez un nombre d'étages du sapin : ")

Lire(Nbétages)

Pour i variant de 0 à Nbétages-1 Faire

début i+1

fin i+4

triangle(début,fin)

FinPour

rectangle(Nbétages)

Fin

// ---- procédure triangle ----

Procédure triangle (PremL,int DernL)

Déclarations

Paramètres PremL, DernL en Entiers

Variables ligne, nbespace, nbétoiles en Entiers

Début

Pour ligne variant de PremL à DernL Faire

// --- dessine MILIEU-ligne espaces ---

Pour nbespaces variant de 1 à MILIEU-ligne Faire

Écrire(" ")

14

FinPour

// --- dessine (2*ligne)-1 étoiles ---

Pour nbétoiles variant de 1 à (2*ligne)-1 Faire

Écrire("*")

FinPour

// --- saut de lignes ---


FinPour

Fin

// ---- procédure rectangle ----

Procédure rectangle (hauteur)

Déclarations

Paramètre hauteur en Entier

Variables ligne, nbespace, nbétoiles en Entiers

Début

Pour ligne variant de 1 à hauteur Faire

Pour nbespace variant de 1 à (MILIEU-(hauteur/2))-1 Faire

Écrire(" ")

FinPour

Pour nbétoiles variant de 1 à hauteur Faire

Écrire("*")

FinPour


FinPour

Fin


respectivement : sapin.c, sapin.cpp, sapin.java.


$ make sapin


$ sapin

Entrez un nombre d'étages du sapin : 4

*

***

*****

*******

***

*****

*******

*********

*****

*******

*********

***********

*******

*********

***********

*************

****

****

****

****


$ javac sapin.java


$ java sapin


15

Exercice 9 : Nombre d’ensembles de k éléments parmi n éléments

Énoncé

Le dénombrement des parties de k éléments parmi un ensemble de n éléments avec k n est un problème classique en mathématiques qui débouche sur de multiples applications. On peut citer, par exemple, le jeu du Loto pour évaluer le nombre de chances de gagner un lot selon le nombre de numéros gagnants, ou les jeux de cartes comme le poker pour déterminer la probabilité d’obtenir une composition particulière de 5 cartes parmi 52 cartes.

Le nombre de sous-ensembles appelés parties de k éléments parmi un ensemble de n éléments avec k n, se nomme coefficient binomial. Il possède deux notations, et est déterminé par la formule suivante :

n

k

æ

èç

ö

ø÷ = Cn

k =n!

k!(n-k)!avec k £ n

Écrivez l’algorithme qui calcule le coefficient binomial de deux entiers saisis au clavier.

Solution

Le programme suivant implémente cet algorithme. La variable coeff_bin reçoit le résultat du calcul qui appelle la

fonction factorielle sur N, K et N–K.

« PSEUDO-CODE »

Programme coefficient_binomial

Déclarations

Variables N, K, coeff_bin en Entier

Début

Écrire("Entrez le nombre total N d'éléments dans l'ensemble : ")

Lire(N)

Écrire("Entrez le nombre K inférieur ou égal à N pour lequel vous voulez

connaître")

Écrire("le nombre de combinaisons de K éléments dans un ensemble de ",N,"

éléments : ")

Lire(K)

// --- calcul du coefficient binomial ---

coeff_bin factorielle(N) / (factorielle(K)*factorielle(N-K))

Écrire("il y a ",coeff_bin," combinaisons de ",K," éléments dans un ensemble de

",N," éléments")

Fin



Déclarations



Début

résultat 1



FinPour

Retourner résultat

Fin


respectivement : coefficient_binomial.c, coefficient_binomial.cpp, coefficient_binomial.java.


$ make coefficient_binomial

Voici un exemple d’exécution de ce programme issu du programme source C. Il montre que dans le cas du Loto français, il y a 1 906 884 grilles possibles de 5 numéros parmi 49 numéros. Ce nombre est augmenté d’un facteur 10 via le numéro supplémentaire comme nous le verrons dans l’exercice suivant.

16

$ coefficient_binomial

Entrez le nombre total N d'éléments dans l'ensemble : 49

Entrez le nombre K inférieur ou égal à N pour lequel vous voulez connaître

le nombre de combinaisons de K éléments dans un ensemble de 49 éléments : 5

il y a 1906884 combinaisons de 5 éléments dans un ensemble de 49 éléments


$ javac coefficient_binomial.java


$ java coefficient_binomial

Exercice 10 : Nombre de chances de gagner au Loto

Énoncé

Le jeu du Loto de la société la Française des Jeux, dans sa version actuelle, permet à chaque joueur de remplir une grille en cochant 5 numéros parmi 49, et un numéro supplémentaire appelé « chance » parmi 10 numéros.

En vous aidant de l’exercice précédent, écrivez l’algorithme qui affiche le nombre de chances de gagner avec 5, 4, 3, 2 et 1 bon(s) numéro(s), et un ou zéro numéro supplémentaire. L’affichage aura la forme suivante :

5 numéro(s)+1 numéro supplé: XXX chance(s) sur YYY = 1 chance sur ZZZ










Pour évaluer le nombre de chances de gagner (1 chance sur ZZZ), il faut d’abord calculer le nombre de combinaisons de 5 numéros parmi 49 et le multiplier avec le nombre de combinaisons de 1 numéro supplémentaire parmi 10 pour obtenir la valeur YYY qui sera identique pour toutes les lignes.

Il faut ensuite calculer le nombre de grilles gagnantes (XXX) pour 4, 3, 2, 1 numéro(s) avec et sans numéro supplémentaire. Cette valeur change pour chaque ligne, elle dépend du nombre de numéro gagnant et du numéro supplémentaire obtenu ou non.

Enfin, la valeur ZZZ recherchée est égale à YYY divisé par XXX.

Les formules suivantes permettent de calculer ces éléments.

Le nombre de combinaisons de k numéros parmi n numéros est donné par la formule du coefficient binomial :

n

k

æ

èç

ö

ø÷ = Cn

k =n!

k!(n- k)!

Par exemple, pour le Loto, le nombre de combinaisons de 5 numéros parmi 49 est :

49

5

æ

èç

ö

ø÷ = C49

5 =49!

5!(49 - 5)!

Le nombre de combinaisons gagnantes de j numéros dans un tirage de k numéros parmi n numéros est donné par la formule :

Ckj ´Cn-k

k- j


17

Par exemple, pour le Loto, le nombre de combinaisons gagnantes de 4 numéros dans une grille de 5

numéros parmi 49 est :

C54 Ć49-5

5-4 = C54 Ć44

1

Solution

Le nombre de combinaisons de k = 5 numéros parmi n = 49 numéros est donné par la formule suivante :

n

k

æ

èç

ö

ø÷ = Cn

k =n!

k!(n- k)! soit

49

5

æ

èç

ö

ø÷ = C49

5 =49!

5!(49 - 5)!=

49!

5!(44)!=1906884

Pour le numéro supplémentaire, le nombre de combinaison de k = 1 numéro parmi n = 10 numéros est donné par la même formule :

10

1

æ

èç

ö

ø÷ = C10

1 =10!

1!(10 -1)!=

10!

9!=10

Le nombre total de combinaisons du Loto (YYY) est égal au nombre de combinaisons de 5 numéros parmi 49,

multiplié par le nombre de combinaisons de 1 numéro parmi 10, soit YYY = 1 906 884 10 = 19 068 840. Il y a donc une chance sur 19 millions de remporter le gros lot !

Il faut ensuite évaluer le nombre de grilles gagnantes pour connaître le nombre de chances de gagner autre chose que le gros lot !

En effet, s’il n’y a qu’une seule combinaison gagnante de 5 numéros, il y en aura plusieurs de 4 numéros. C’est également le cas pour 3, 2 ou 1 numéro(s), ce qui augmente votre chance de gagner un gain, même s’il est plus faible.

Par exemple, le nombre de combinaisons gagnantes de j = 4 numéros dans un tirage de k = 5 numéros parmi n = 49 numéros est :

Ckj Ćn-k

k- j = C54 Ć49-5

5-4 = C54 Ć44

1 =5!

4!(5- 4)!´

44!

1!(44-1)!=

5!

4!!´

44!

43!= 5´ 44 = 220

Il faut effectuer ce calcul pour chaque valeur de j pour déterminer le nombre de grilles gagnantes de 4, 3, 2 et 1 numéro(s).

Pour chaque cas précédent, il faut multiplier le résultat obtenu avec le nombre de combinaisons gagnantes de 1 numéro (j) supplémentaire dans un tirage de 1 numéro (k) parmi 10 numéros (n), puis refaire le calcul avec le nombre de combinaisons gagnantes de 0 numéro (j) supplémentaire dans un tirage de 1 numéro (k) parmi 10 numéros (n).

Le calcul pour 0 numéro supplémentaire gagnant est :

Ckj Ćn-k

k- j = C10 Ć10-1

1-0 = C10 Ć9

1 =1!

0!(1-0)!´

9!

1!(9 -1)!=

1!

1!´

9!

8!=1´9 = 9

Le calcul pour 1 numéro supplémentaire gagnant est :

Ckj Ćn-k

k- j = C11 Ć10-1

1-1 = C11 Ć9

0 =1!

1!(1-1)!´

9!

1!(9 - 0)!=

1!

1!´

9!

9!=1´1=1

On obtient ainsi le nombre total de combinaisons gagnantes (XXX) pour 4, 3, 2 ou 1 numéro, avec 0 ou 1 numéro

supplémentaire. Dans notre exemple, il y a 220 9 = 1980 grilles gagnantes de 4 numéros n’ayant aucun numéro

supplémentaire, et 220 1 = 220 grilles gagnantes de 4 numéros et un numéro supplémentaire.

Pour chaque ligne, la dernière partie de l’affichage est obtenue en divisant le nombre total de combinaison YYY par le nombre de combinaisons gagnantes de chaque cas XXX, donnant ainsi le rapport de 1 chance sur ZZZ.

Voici le programme qui implémente cet algorithme. La variable NbCombinaisonsLoto contient le nombre total de

combinaisons (YYY). Les variables NNbLoto, KNbLoto indiquent respectivement le nombre de numéros (49) et le

nombre de numéros à cocher par grille (5). Les variables NSupplLoto, KSupplLoto indiquent respectivement le

nombre de numéros supplémentaires (10) et le nombre de numéros supplémentaires à cocher par grille (1). La

18

variable NbChancesTotal contient le nombre total de grilles gagnantes (XXX) pour chaque valeur de nbNum et de

nbSuppl. La variable NbChancesRéduit contient la valeur correspondant au champ ZZZ représentant les chances de

gagner.

« PSEUDO-CODE »

Programme loto_5Numéros_1Suppl

Déclarations

Variables N, K, coeff_bin en Entier

Variables NNbLoto, KNbLoto, NSupplLoto, KSupplLoto en Entier

Variables NbChancesRéduit, NbChancesTotal en Entier

Variables NbChancesNuméros, NbChancesNumSuppl en Entier

Variables nbNum, nbSuppl, NbCombinaisonsLoto en Entier

Début

NNbLoto 49

KNbLoto 5

NSupplLoto 10

KSupplLoto 1

NbChancesRéduit 1

// --- Nombre total de combinaisons : 5 numéros + numéro supplémentaire

NbCombinaisonsLoto C(NNbLoto,KNbLoto) * C(NSupplLoto,KSupplLoto)

// --- Calcul du nombre de chances ---

Pour nbNum variant de KNbLoto à 1 par pas de -1 Faire

Pour nbSuppl variant de KSupplLoto à 0 par pas de -1 Faire

NbChancesNuméros C(KNbLoto,nbNum) * C(NNbLoto-(KNbLoto),KNbLoto-nbNum)

NbChancesNumSuppl C(KSupplLoto,nbSuppl) * C(NSupplLoto-

(KSupplLoto),KSupplLoto-nbSuppl)

NbChancesTotal NbChancesNuméros * NbChancesNumSuppl

NbChancesRéduit NbCombinaisonsLoto / NbChancesTotal

Écrire(nbNum," numéro(s)+",nbSuppl," numéro supplé: ",NbChancesTotal,"

chance(s) sur ",NbCombinaisonsLoto)

Écrire(" = 1 chance sur ",NbChancesRéduit)

FinPour

FinPour

Fin

// --- fonction coefficient_binomial ---

Fonction C(N,K)

Déclarations

Paramètres N, K en Entier

Variable coeff_bin en Entier

Début


Retourner coeff_bin

Fin

// --- fonction factorielle ---


Déclarations



Début

résultat 1



FinPour

Retourner résultat

Fin


respectivement : loto_5numeros_1Suppl.c, loto_5numeros_1Suppl.cpp, loto_5numeros_1Suppl.java.


$ make loto_5numeros_1Suppl


19


$ loto_5numeros_1Suppl

5 numéro(s)+1 numéro supplé: 1 chance(s) sur 19068840 = 1 chance sur 19068840











$ javac loto_5numeros_1Suppl.java


$ java loto_5numeros_1Suppl

Exercice 11 : Nombre de chances de gagner à l’Euro Millions ou au Powerball États-Unis

Énoncé

Adaptez le programme précédent pour afficher les chances de gagner à l’Euro Millions. Dans ce jeu, chaque joueur doit cocher 5 numéros parmi 50, et deux numéros « étoiles » supplémentaires parmi 11 numéros.

Faites une seconde adaptation pour le loto Powerball des U.S.A dans lequel le joueur doit cocher 5 numéros parmi 59, et un numéro supplémentaire parmi 35 numéros.

Solution

Cet exercice démontre l’importance de faire l’analyse avant d’écrire l’algorithme. En effet, dans ces différents jeux de loto, la problématique du dénombrement ne change pas. Il n’y aura donc pas de modification de l’algorithme, juste une adaptation des données !

En effet, que ce soit pour le Loto français, l’Euro Millions ou le Powerball des États-Unis, on doit cocher K numéros sur N numéros sur une première grille, puis K' numéros supplémentaires sur N' numéros sur une seconde grille.

Au Loto français, on choisit 5 numéros sur 49 sur la première grille, puis 1 sur 10 sur la grille des numéros supplémentaires ;

À l’Euro Millions, on choisit 5 numéros sur 50 sur la première grille, puis 2 sur 11 sur la grille des numéros supplémentaires.

Au loto Powerball des États-Unis on choisit 5 numéros sur 59 sur la première grille, puis 1 sur 35 sur la grille des numéros supplémentaires.

L’adaptation du programme se résume à modifier les valeurs initiales des variables NNbLoto (N), KNbLoto (K),

NSuppLoto (N'), KSuppLoto (K'), ce qui ne change pas la logique du programme, donc de l’algorithme !

Voici la partie du programme de l’exercice précédent concernant ces variables pour le Loto français :

« PSEUDO-CODE »

NNbLoto 49

KNbLoto 5

NSupplLoto 10

KSupplLoto 1

Voici les valeurs de ces variables pour l’Euro Millions :

« PSEUDO-CODE »

NNbLoto 50

KNbLoto 5

NSupplLoto 11

KSupplLoto 2

20

Voici les valeurs de ces variables pour le loto Powerball des États-Unis :

« PSEUDO-CODE »

NNbLoto 59

KNbLoto 5

NSupplLoto 35

KSupplLoto 1

Les programmes sources C, C++ et Java téléchargeables qui implémentent l’algorithme de l’Euro Millions se

nomment respectivement : euromillions.c, euromillions.cpp, euromillions.java.


$ make euromillions


$ euromillions

5 numéro(s)+2 numéro sup: 1 chance(s) sur 116531800 = 1 chance sur 116531800













1 numéro(s)+1 numéro sup:13409550 chance(s) sur 116531800 = 1 chance sur 9


Il y a donc une chance sur 116 millions de remporter le gros lot de l’Euro Millions !


$ javac euromillions.java


$ java euromillions

Les programmes sources C, C++ et Java téléchargeables qui implémentent l’algorithme du loto Powerball des

États-Unis se nomment respectivement : loto_powerball_usa.c, loto_powerball_usa.cpp,

loto_powerball_usa.java.


$ make loto_powerball_usa


$ loto_powerball_usa











Il y a donc une chance sur 175 millions de remporter le gros lot du Powerball États-Unis !


21

Exercice 12 : Nombre de chances de gagner au Loto avec 6 numéros et tirage d’un numéro complémentaire

Énoncé

Cet exercice ressemble beaucoup aux deux exercices précédents. Cependant, s’il travaille aussi sur le dénombrement des jeux de loto, son approche diffère, ce qui modifie sa logique et donc l’algorithme.

Le jeu du Loto de la société la Française des Jeux, dans sa version précédente, permettait à chaque joueur de remplir une grille en cochant 6 numéros parmi 49. Et c’était tout !

Lors du tirage du Loto, on procédait au tirage des 6 numéros gagnants et d’un 7e numéro dit « complémentaire »

parmi les 49 numéros. Ce numéro « complémentaire » permettait d’augmenter les chances de gagner en autorisant les combinaisons gagnantes, par exemple avec 4 bons numéros et le numéro complémentaire.

À la différence des exercices précédents, il n’y a pas de numéro supplémentaire à cocher sur une seconde grille de 10 (Loto), 11 (Euro Millions) ou 35 (Powerball États-Unis) numéros. Le joueur ne coche que 6 numéros sur une seule grille. Le numéro complémentaire obtenu au tirage doit être l’un de ces 6 numéros cochés.

Nous proposons d’écrire l’algorithme qui affiche le nombre de chances de gagner avec : 6 numéros, 5 numéros plus le complémentaire, 5 numéros, 4 numéros avec le complémentaire, 4 numéros…, lors d’un tirage de 6 numéros et du complémentaire sur un total de 49.

Solution

Par rapport à l’exercice 10 qui propose l’algorithme de la version actuelle du Loto de la Française des Jeux, dans la version précédente de ce jeu, le nombre de total de combinaisons diffère, puisqu’il n’y a plus aucun numéro supplémentaire. C’est aussi le cas du nombre de grilles gagnantes, puisqu’un 7

e numéro dit « complémentaire »

permet d’augmenter les chances de gagner. Voici la comparaison des calculs à effectuer pour ces deux versions du jeu.

Calcul du nombre de combinaisons

Dans la version actuelle du Loto de la Française des Jeux, il y a 5 numéros à choisir parmi 49 et 1 numéro à choisir parmi 10. Le nombre total de combinaisons est de 19 068 840. Il est calculé à partir de la formule :

C495 Ć10

1 =1906884´10=19068840

Dans la version précédente, il n’y avait que 6 numéros à choisir parmi 49. Le nombre total de combinaisons était de 13 993 816. Il est calculé à partir de la formule :

C496 =13983816

Calcul du nombre de grilles gagnantes

Pour la version actuelle du Loto, le nombre de combinaisons gagnantes de 4 numéros dans une grille de 5 numéros parmi 49, avec 0 numéro (aucun) supplémentaire dans une grille de 1 numéro parmi 10, est donné par le calcul :

C54 Ć49-5

5-4( )´ C10 Ć10-11-0( ) = C54 Ć441( )´ C10 Ć91( )= 5´ 44( )´ 1´ 9( ) = 5´ 44( )´ 1´ 9( ) = 220´ 9 =1980

Pour la version précédente du Loto, il faut calculer le nombre de combinaisons gagnantes de 4 numéros

dans une grille de 6 numéros parmi 49 avec un 7e numéro complémentaire. Si la grille contient le 7e numéro complémentaire, alors le nombre de numéros gagnants est de 4 + 1. Le calcul est donné par la formule :

C64 Ć49-7

6-(4+1)( ) = C64 Ć421( ) =15´ 42 = 630

Si la grille ne contient pas le 7e numéro complémentaire, alors le nombre de numéros gagnants est seulement de 4 + 0, soit 4. Le calcul est donné par la formule :

C64 Ć49-7

6-(4+0)( ) = C64 Ć422( ) =15´861=12915

22

On reproduit ces calculs pour, 5, 4, 3, 2 et 1 numéro(s) gagnant(s) avec à chaque fois la combinaison ou non du numéro complémentaire. Voici le programme effectuant ce traitement :

« PSEUDO-CODE »

Programme loto_6numeros

Déclarations

Variables NNbLoto, KNbLoto, KComplLoto en Entier

Variables NbChancesRéduit, NbChances en Entier

Variables nbnum, nbcompl, NbCombinaisionsLoto en Entier

Début

NNbLoto 49

KNbLoto 6

KComplLoto 1

NbChancesRéduit 1

NbChances 1

NbCombinaisionsLoto C(NNbLoto,KNbLoto)

NbChancesRéduit NbCombinaisionsLoto/NbChances

// --- Loto Français : 6 numéros avec complémentaire au tirage ---

Écrire("6 numéros : ",NbChances," chance(s) sur ",NbCombinaisionsLoto)


Pour nbnum variant de KNbLoto-1 à 1 par pas de -1 Faire

Pour nbcompl variant de KComplLoto à 0 par pas de -1 Faire

NbChances C(KNbLoto,nbnum)*C(NNbLoto-(KNbLoto+1),KNbLoto-nbnum-nbcompl)

NbChancesRéduit NbCombinaisionsLoto/NbChances

Si (nbcompl = 1) Alors

Écrire(nbnum," numéros + numéro compl: ",NbChances," chance(s) sur

",NbCombinaisionsLoto)

Sinon

Écrire(nbnum," numéros : ",NbChances," chance(s) sur

",NbCombinaisionsLoto)

FinSi


FinPour

FinPour

Fin

// --- fonction coefficient_binomial ---

Fonction C(N,K)

Déclarations

Paramètres N, K en Entier

Variable coeff_bin en Entier

Début


Retourner coeff_bin

Fin

// --- fonction factorielle ---


Déclarations



Début

résultat 1



FinPour

Retourner résultat

Fin


respectivement : loto_6numeros.c, loto_6numeros.cpp, loto_6numeros.java.


23


$ make loto_6numeros


$ loto_6numeros

6 numéros : 1 chance(s) sur 13983816 = 1 chance sur 13983816

5 numéros + numéro compl: 6 chance(s) sur 13983816 = 1 chance sur 2330636










Il y avait donc une chance sur 13,9 millions de remporter le gros lot dans la version précédente du Loto !


$ javac loto_6numeros.java


$ java loto_6numeros

Chapitre 3 – La gestion des données

Le premier exercice montre comment utiliser le type caractère pour lire tout type de données. Les exercices 2 à 8 présentent la réécriture de fonctions de traitement de chaînes de caractères. L’exercice 9 détecte les doublons dans un tableau. L’exercice 10 montre comment sauvegarder une liste de notes dans un fichier.

Exercice 1 : Calculette simplifiée

Énoncé

Écrivez un programme qui affiche le résultat d'une expression arithmétique contenant des additions et des soustractions. Le programme lira chaque élément caractère par caractère, retrouvera la valeur numérique et exécutera les opérations lorsqu’un signe '+' ou '–' sera rencontré. La boucle générale sera une boucle de lecture d'un caractère TANT QUE la fin de ligne n'est pas atteinte (le caractère fin de ligne est le caractère LF ou Line feed, de code ASCII 10 et noté '\n' en C). Les expressions auront la forme suivante : 102 + 28 – 329 – 10 + 124.

Solution

L’algorithme suivant lit chaque caractère saisi, retrouve la valeur numérique et effectue les opérations lorsqu’un signe '+' ou '–' est rencontré. La boucle générale est une boucle de lecture d'un caractère TANT QUE la fin de ligne n'est pas atteinte.

Le premier type de traitements concerne les cas où le caractère lu est un signe. Il faut alors additionner le nombre qui vient d’être lu à la somme actuelle pour produire la nouvelle somme, puis remettre le nombre à 0. Il faut enfin mémoriser le caractère lu dans la variable signe, car il correspond à la prochaine opération à effectuer, quand le

nombre suivant sera lu.

Le second type de traitements concerne les cas où le caractère lu est un chiffre. Il faut retrouver la valeur

numérique correspondante (code_ascii(caract)-48), et l’ajouter au nombre. Cet ajout ressemble à une

« concaténation » numérique, afin que ce chiffre soit ajouté en tant qu’unité au nombre précédent, lequel doit être

considéré comme une dizaine : nb (nb*10)+chiffre.

« PSEUDO-CODE »

Écrire("Entrez une expression arithmétique : ");

nb 0

chiffre 0

somme 0

signe '+'

24

// on boucle TANT QUE la fin de ligne n'est pas atteinte

Tant que (NON fin_de_ligne()) Faire

Lire(caract)

Selon (caract) Faire

Cas '+', '-' : // somme ou soustraction selon le signe précédent

Si (signe = '+') Alors

somme somme+nb

Sinon

somme somme-nb

FinSi

nb 0 // On remet nb à 0

signe caract // On mémorise le signe actuel

Cas '0'...'9': // On récupère la valeur numérique

chiffre code_ascii(caract)–48

nb (nb*10)+chiffre // On calcule le nouveau nombre

FinSelon

FinTantQue

// Quand on sort, la dernière somme n'est pas faite

Si (signe = '+') Alors

somme somme+nb

Sinon

somme somme–nb

FinSi

Écrire("Résultat : ",somme)

Les programmes sources C, C++ et Java téléchargeables qui implémentent cet algorithme se nomment respectivement : calculateur.c, calculateur.cpp, calculateur.java.


$ make calculateur


$ calculateur

Entrez une expression arithmétique : 123-76+14

Résultat = 61


$ javac calculateur.java


$ java calculateur

Exercice 2 : Éditeur de mot

Énoncé

Écrivez un éditeur de mot. L’algorithme saisira un mot, puis demandera une action à effectuer. L’action « d » détruira le caractère dont le numéro sera précisé par l’utilisateur. L’action « i » insérera un caractère avant la position indiquée. L’action « t » terminera le programme. Le mot sera affiché après chaque traitement. Le mot sera assimilé à un tableau de caractères ayant un caractère particulier de fin de chaîne. Voici un exemple d’exécution attendue :

Entrez un mot:Fctilex

Action (d=destruction,i=insertion,t=terminer) :d

Numéro du caractère à détruire : 3

Résultat : Fcilex

Action (d=destruction,i=insertion,t=terminer) :d

Numéro du caractère à détruire : 6

Résultat : Fcile


25

Action (d=destruction,i=insertion,t=terminer) :i

Insertion avant le caractère numéro: 2

Caractère à insérer : a

Résultat : Facile

Action (d=destruction,i=insertion,t=terminer) :t

Solution

L’algorithme présenté se sert d’une boucle de saisie TANT QUE contenant un choix multiple. Chaque action déclenche le branchement sur l’un des choix qui effectue le traitement désiré. Le choix « d » décale les cases situées à droite de la position vers la gauche, ce qui efface le caractère à détruire. Le choix « i » décale les cases à partir de la position indiquée d’une case vers la droite, ce qui libère une case, puis affecte le caractère à insérer dans cette case.

« PSEUDO-CODE »

Programme édition_mot

Déclarations

Variables mot en Chaîne

Variable car, saisie, action en Caractère

Variables numéro en Entier

Début

action 'i'

Tant Que (action 't') Faire

Écrire("Action (d=destruction, i=insertion, t=terminer : ")

Lire(saisie)

Selon (saisie) faire

Cas 'd' :

Écrire("Numéro du caractère à détruire : ")

Lire(numéro)

Pour i variant de 1 à longueur(mot)-1 Faire

mot[i] mot[i]+1

FinPour

Écrire("Résultat : ", mot)

FinCas

Cas 'i' :

Écrire("Insertion avant le caractère numéro : ")

Lire(numéro)

Écrire("Caractère à insérer : ")

Lire(car)

Pour i variant de longueur(mot)-1 à numéro-1 Par Pas de -1 Faire

mot[i+1] mot[i]

mot[numéro-1] car

FinPour

Écrire("Résultat : ", mot)

FinCas

Cas 't' :

Écrire("Au revoir ")

FinCas

FinSelon

FinTantQue

Fin


respectivement : edition_mot.c, edition_mot.cpp, edition_mot.java.


$ make edition_mot


$ javac edition_mot.java


$ java edition_mot

Le programme source Java téléchargeable edition_mot_StringBuffer.java propose une version utilisant les

méthodes de la classe StringBuffer.

26

Exercice 3 : Comparaison de chaînes

Énoncé

Écrivez un algorithme qui saisit deux chaînes de caractères et qui indique si elles sont identiques ou non. Le traitement utilisera la gestion des chaînes en tant que tableaux de caractères et comparera les caractères respectifs des deux chaînes.

Solution

Les instructions suivantes effectuent la comparaison des deux chaînes, caractère par caractère. Un premier test vérifie si la taille des deux chaînes est identique. Si c’est le cas, une boucle TANT QUE compare chaque caractère et s’arrête quand la comparaison devient fausse ou que la fin de chaîne est atteinte. Si la fin de chaîne est atteinte sans jamais trouver de différence, alors les deux chaînes sont identiques.

« PSEUDO-CODE »

Programme comparaison_chaine

Déclaration

Variables nom1, nom2 en Chaîne

Variable est_identique en Booléen

Variables taille1, taille2, i en Entier

Début

Écrire("Entrez un premier nom :")

lire(nom1)

Écrire("Entrez un deuxième nom :")

Lire(nom2)

est_identique VRAI

i 0

taille1 longueur(nom1)

taille2 longueur(nom2)

Si (taille1 taille2) Alors

est_identique FAUX

Sinon

i 0

Tant que ((i


27

Voici deux exemples d’exécution de ce programme issu du programme source C :

$ comparaison_chaine

Entrez un premier nom :dupont

Entrez un deuxième nom :dupont

Les noms sont identiques

$ comparaison_chaine

Entrez un premier nom :dupont

Entrez un deuxième nom :Dupont

Les noms sont différents


$ javac comparaison_chaine.java


$ java comparaison_chaine

Le programme source Java téléchargeable comparaison_chaine_String.java propose une version utilisant les

méthodes de la classe String.

Exercice 4 : Extraction d’une sous-chaîne

Énoncé

Écrivez un algorithme qui saisit un nom et fait l’extraction d’une sous-chaîne à partir d’une position et sur un nombre de caractères fournis par l’utilisateur. Le programme travaillera sur le tableau de caractères que constitue la chaîne.

Solution

La variable schaine contient la sous-chaîne extraite à partir de la variable nom. Un premier test vérifie que

l’extraction est possible en comparant le début et le nombre de caractères (début+nbcar) avec la taille du nom. Une

boucle TANT QUE affecte chaque caractère du nom à partir de la position initiale dans la variable schaine sur

nbcar caractères.

« PSEUDO-CODE »

Programme sous_chaîne

Déclaration

Variables nom, schaine en Chaine

Variables début, nbcar, taille, i en Entier

Début

i 0

Écrire("Entrez un nom :");

Lire(nom)

Écrire("Numéro du caractère débutant la sous-chaîne :")

Lire(début)

Écrire("Nombre de caractères :")

Lire(nbcar)

taille longueur(nom)

début début-1

Si ((début+nbcar)

28


$ sous_chaine

Entrez un nom :dupont

Numéro du caractère débutant la sous-chaîne :2

Nombre de caractères :4

sous-chaîne :upon


$ javac sous_chaine.java


$ java sous_chaine

Le programme source Java téléchargeable sous_chaine_String.java propose une version utilisant les méthodes

de la classe String.

Exercice 5 : Position d’un caractère dans une chaîne

Énoncé

Écrivez un algorithme qui saisit un nom, puis un caractère à rechercher, et affiche la position de sa première occurrence dans le nom. Le programme travaillera sur le tableau de caractères que constitue la chaîne.

Solution

Le programme index_chaine parcourt chaque caractère du nom et le compare au caractère saisi. Il affiche la

position du caractère s’il est trouvé.

« PSEUDO-CODE »

Programme index_chaine

Déclarations

Variable nom en Chaîne

Variable car en Caractère

Variables taillenom, i, numéro en Entier

Début

Écrire("Entrez un nom :")

Lire(nom)

Écrire("Entrez un caractère :")

Lire(car)

numéro 0

i 0

taillenom longueur(nom)

Tant que ((numéro = 0) ET (i


29

Voici deux exemples d’exécution de ce programme issu du programme source C :

$ index_chaine

Entrez un nom : dupont

Entrez un caractère : p

p trouvé en position 3

$ index_chaine


Entrez un caractère : R

R non trouvé


$ javac index_chaine.java


$ java index_chaine

Le programme source Java téléchargeable index_chaine_String.java propose une version utilisant les méthodes

de la classe String.

Exercice 6 : Longueur d’une chaîne

Énoncé

Écrivez un algorithme qui calcule la longueur d’une chaîne de caractères. Le programme travaillera sur le tableau

de caractères que constitue la chaîne. Un caractère particulier FIN_DE_CHAINE indique la fin de la suite de

caractères.

Solution

Le calcul de la longueur d’une chaîne se résume à indiquer le nombre de caractères qui la constitue. Les différents

langages de programmation disposent d’une fonction spécifique que nous nommerons longueur(). Le programme

suivant affiche la longueur d’une chaîne grâce à cette fonction, puis par l’intermédiaire d’une boucle de comptage des caractères. On suppose alors que la constante FIN_DE_CHAINE contenue dans la chaîne indique la fin des

caractères.

« PSEUDO-CODE »

Programme longueur_chaine

Déclarations

Variable mot en Chaîne

Variables taille1, taille2 en Entier

Début

Écrire("Entrez un mot :")

Lire(mot)

taille1 longueur(mot)

taille2 0

Tant que (mot[taille2] FIN_DE_CHAINE) Faire

taille2 taille2+1

FinTantQue

/* --- affichage --- */

Écrire("taille1=",taille1," taille2=",taille2)

Fin


respectivement : longueur_chaine.c, longueur_chaine.cpp, longueur_chaine.java.


$ make longueur_chaine


$ longueur_chaine

Entrez un mot : dupont

taille1=6 taille2=6


$ javac longueur_chaine.java

30


$ java longueur_chaine

Exercice 7 : Concaténation de deux chaînes

Énoncé

Écrivez un algorithme qui saisit le nom et le prénom d’une personne, les concatène avec un caractère espace entre les deux et affiche le résultat. Les chaînes de caractères seront traitées comme des tableaux de caractères.

Solution

La concaténation met bout à bout deux chaînes de caractères. Ce traitement est souvent présenté dans les différents langages de programmation comme une fonction. Ce n’est pas le cas en langage C. Si deux chaînes contiennent respectivement « Dupont » « Jean », le résultat de la concaténation sera « DupontJean », sans aucun espace séparateur. La taille de la variable accueillant le résultat doit être suffisamment grande. Les syntaxes suivantes concatènent un nom et un prénom avec un caractère espace entre les deux, le résultat est rangé dans

une troisième chaîne nommée NomComplet.

NomComplet concaténation(nom," ")

NomComplet concaténation(NomComplet,prénom)

Ce traitement peut aussi être effectué par des boucles sur les tableaux de caractères comme le montre le programme suivant :

« PSEUDO-CODE »

Programme concatenation_chaine

Déclaration

Variables nom, prénom, NomComplet en Chaîne

Variables taillenom, tailleprenom, i, j en Entier

Début

Écrire("Entrez un nom :")

Lire(nom)

Écrire("Entrez un prénom :")

Lire(prenom)

/* copie du nom dans NomComplet */

taillenom longueur(nom)

Pour i variant de 0 à taillenom-1 Faire

NomComplet[i] nom[i]

FinPour

/* Ajout d’un caractère espace */

i i+1

NomComplet[i] ' '

/* Ajout du prénom à la fin de NomComplet */

tailleprénom longueur(prénom)

Pour j variant de 0 à tailleprénom-1 Faire

i i+1

NomComplet[i] prénom[j]

FinPour

Écrire("NomComplet : ",NomComplet)

Fin


respectivement : concatenation_chaine.c, concatenation_chaine.cpp, concatenation_chaine.java.


$ make concatenation_chaine


31


$ concatenation_chaine


Entrez un prénom : jean

concaténation par les fonctions : dupont jean

gestion des tableaux de caractères: dupont jean


$ javac concatenation_chaine.java


$ java concatenation_chaine

Exercice 8 : Lecture d’une chaîne ayant des espaces

Énoncé

Les langages de programmation considèrent le caractère espace comme un séparateur de mots, comme en français. Ainsi, si on veut lire un nom composé comme « de La Fontaine », alors les fonctions de lecture de chaîne des différents langages liront le nom « de ».

Écrivez l’algorithme qui lit un nom composé, donc ayant des espaces, caractère par caractère, et qui range chaque caractère lu dans une chaîne.

Solution

Le programme suivant lit chaque caractère saisi, tant que la fin de ligne n’est pas atteinte. Chaque caractère lu est rangé dans la i

e case du tableau de caractères, i étant incrémenté à chaque lecture. À la fin de la boucle, on ajoute

le caractère FIN_DE_CHAINE au tableau de caractères, pour définir une chaîne.

« PSEUDO-CODE »

Programme lecture_chaîne_avec_espaces

Déclaration

Variable mot en Chaîne

Variable i en Entier

Variable car en caractère

Début

i 0

Écrire("Entrez un nom composé : ")

// --- boucle de lecture ---

Tant Que (NON Fin_de_Ligne())

Lire(car)

mot[i] car

i i+1

FinTantQue

mot[i] FIN_DE_CHAINE

// --- affichage ---

Écrire ("La chaîne de caractère est : ",mot)

Fin

Les programmes sources C, C++ et Java téléchargeables qui implémentent cet algorithme se nomment respectivement : lecture_chaine_avec_espaces.c, lecture_chaine_avec_espaces.cpp,

lecture_chaine_avec_espaces_nextLine.java.


$ make lecture_chaine_avec_espaces


$ lecture_chaine_avec_espaces

Entrez un mot : de La Fontaine

La chaîne de caractère est : de La Fontaine


$ javac lecture_chaine_avec_espaces_nextLine.java

32


$ java lecture_chaine_avec_espaces_nextLine

Exercice 9 : Détection des doublons dans un tableau

Énoncé

Soit un tableau contenant une liste de N nombres entiers dont la valeur est comprise entre 1 et 100. Écrivez un algorithme qui détecte la présence de doublons (valeurs répétées plusieurs fois) dans le tableau.

Solution

La solution présentée utilise une boucle principale TANT QUE, qui parcourt tous les éléments du tableau tant qu’aucun doublon n’est détecté. Pour chaque valeur de la liste (contenue dans la case i du tableau), on vérifie

qu’elle n’est pas présente dans la partie gauche du tableau, c’est-à-dire du début jusqu’à sa position actuelle. Si

elle est trouvée, le compteur doublons est augmenté.

« PSEUDO-CODE »

Programme doublons_tableau

Déclaration

Constante TAILLE=100

Variable tab_notes en Tableau[TAILLE] d’Entiers

Variables nbnotes, nb,i,j, doublons en Entier

Début

nbnotes 0

nb 0

doublons 0

Écrire("Entrez une liste de nombres entiers positifs terminée")

Écrire("par -1, avec ou sans doublons (ex: 1 2 23 2 6 7 1 19 -1) :")

// --- boucle de chargement ---

Tant Que ((nb -1) ET (nbnotes < TAILLE)) Faire

Lire(nb)

tab_notes[nbnotes] nb

nbnotes nbnotes+1

FinTantQue

Si (nb = -1) Alors

nbnotes nbnotes-1

Sinon

Écrire("nombre de notes limité à ",TAILLE)

FinSi

// --- boucle d'affichage ---

Écrire("Contenu du tableau : ")

Pour i variant de 0 à nbnotes-1 Faire

Écrire(tab_notes[i])

FinPour

// --- boucle de détection des doublons ---

i 0

Tant que ((i


33

Sinon

Écrire("Aucun doublon dans la liste saisie")

FinSi

Fin


respectivement : doublons_tableau.c, doublons_tableau.cpp, doublons_tableau.java.


$ make doublons_tableau

Voici deux exemples d’exécution de ce programme :

$ doublons_tableau

Entrez une liste de nombres entiers positifs terminée par -1

avec ou sans doublons (ex: 1 2 23 2 6 7 1 19 -1) :

8 9 5 4 11 12 7 4 11 36 59 9 8 7 1 11 -1

Contenu du tableau : 8 9 5 4 11 12 7 4 11 36 59 9 8 7 1 11

Il y a des doublons dans la liste saisie

$ doublons_tableau

Entrez une liste de nombres entiers positifs terminée par -1

avec ou sans doublons (ex: 1 2 23 2 6 7 1 19 -1) :

1 2 3 4 5 6 -1

Contenu du tableau : 1 2 3 4 5 6

Aucun doublon dans la liste saisie


$ javac doublons_tableau.java


$ java doublons_tableau

Exercice 10 : Sauvegarde d’une liste de notes dans un fichier

Énoncé

Écrivez un algorithme qui saisit une liste de notes terminée par –1 et qui les sauvegarde dans un fichier texte dont le nom est fourni par l’utilisateur.

Solution

La liste des notes terminée par la valeur –1 est rangée dans un tableau de réels. Une boucle de sauvegarde

parcourt les nbnotes cases du tableau pour les écrire dans le fichier.

« PSEUDO-CODE »

Programme sauvegarde_fichier

Déclarations

Variable nomfichier en Chaîne

Va

Documents

Algorithmique - Pearson...Exercice 1 : Conversion des francs en euros Énoncé Écrivez l’algorithme qui convertit en euros une somme exprimée en francs. Le résultat en euros sera