Exemples d'algorithmes

selkis

Dans le cours qui va suivre, nous allons utiliser un pseudolangage, comportant toutes les structures de base d'un langage de programmation. ♪

- Titre : Exemples d'algorithmes

- Auteur : selkis

- Parution : 5 mars 2005

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2005 selkis. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Rechercher une symétrie dans une chaine de caractères

- II. Compter une lettre dans une phrase

- III. Savoir si une année est bissextile ou pas

- IV. Les tris

- IV-A. Le tri à bulles

- IV-B. Le tri par sélection

- IV-C. Le tri par Permutation

- IV-D. Le tri par comptage

- V. Factorielle, récursivité et répétitive

- VI. Recherche Dichotomique

I - Rechercher une symétrie dans une chaine de caractères

Un palindrome est une chaîne de caractères que l'on peut lire identiquement de droite à gauche et de gauche à droite.

Par exemple :

AA ;

38783 ;

LAVAL A ETE A LAVAL.

Soit une chaîne de caractères terminée par un point.

Nous allons écrire l'algorithme d'un programme permettant d'affirmer si cette phrase est ou non un palindrome.

Jeu d'essai

'.' c'est un palindrome

'a.' c'est un palindrome

'aba' c'est un palindrome

'acb.' ce n'est pas un palindrome

'aacba.' ce n'est pas un palindrome

'aacab.' ce n'est pas un palindrome

Constantes
charterm = "." //caractère marquant la fin de la chaîne
taille = 80 //nbr maximum de caractères dans la chaîne
Types chaîne = tableau[taille]de caractères //type des chaînes de caractères traitées
Variables phrase : chaine //phrase dans laquelle on va déterminer la symétrie
i : entier //indice de parcours de la phrase par le debut
j : entier //indice de parcours de la phrase par la fin

Début Programme //saisie de la phrase
Écrire ('donnez une phrase terminée par un caractère ',carterm)
Lire (phrase) //calcul de la longueur de la phrase
j : = 1;
Tantque (phrase[j]<>charterm) faire //arrêt sur le caractère de terminaison
j := j + 1
Fintantque
j := j -1 //Parcours de la phrase par les 2 bouts pour ne pas ..
i := 1 //..compter le caractère de terminaison
Tantque (i < j) et (phrase[i]=phrase[j]) faire //arrêt quand les indices se croisent ou quand il n'y a pas de symétrie
i:= i +1
j := j -1
Fintantque//fin du parcours, il y a symétrie

Si i>=j alors //affichage du résultat
Écrire ('c'est un palindrome')
sinon
Écrire ('ce n'est pas un palindrome')
Fsi
Fin Programme

II - Compter une lettre dans une phrase

Soit une chaîne de caractères terminée par le caractère « . ».

Nous allons donner l'algorithme d'un programme qui compte le nombre d'occurrences d'une lettre donnée ('a' par exemple).

Création du jeu d'essai

1) Pas de lettre

lettre 'a'

Terminateur « . »

Phrase « . »

résultat 0

2) Pas de bonne lettre

lettre 'a'

Terminateur « . »

Phrase « etoiles. »

résultat 0

3) Que des bonnes lettres

lettre 'a'

Terminateur « . »

Phrase « aaaaaa. »

résultat 6

4) Mixtes

lettre 'a'

Terminateur « . »

Phrase « mon chat est amusant. »

résultat 3

5) La lettre recherchée est le terminateur

lettre '.'

Terminateur « . »

Phrase « mon chien est gentil. »

résultat 0

N.B. Le terminateur ne fait pas partie des caractères à traiter, il est juste présent, nous ne nous en occuperons donc pas dans le cadre de cet algorithme.

Programme compter_une_lettre
Constantes  charfind = 'a' // caractère dont les occurrences sont comptées.
charfin = "." //caractère de fin de chaîne.
taille = 80 //nbr maximum de caractères dans la chaîne

Types chaîne=tableau[taille]de caractères //type des chaînes de caractères traitées

Variables phrase : chaine //phrase dans laquelle les charfind sont comptés
i : entier //indice de parcours de la phrase
compteur : entier //compteur des charfind dans la phrase

Début  //initialisation des compteurs et lecture de la phrase
Écrire('donnez une phrase terminée par un caractère ',charfin)
Lire(phrase)
i : = 1
compteur=0

//Parcours de la phrase avec recherche des caractères charfind

//Il y a 0 ou plusieurs caractères à parcourir
Tantque (phrase[i]<>charfin) faire //arrêt sur le caractère de fin
Si phrase[i]=charfind Alors
compteur : = compteur + 1 //1 caractère recherché trouvé
Finsi
i : = 1+ 1 //on passe au caractère suivant
Fintantque
Ecrire('le nombre de caractères ',charfin,' dans la phrase est de : ', compteur) //résultat du parcours
Fin

III - Savoir si une année est bissextile ou pas

En fait c'est très simple : si l 'année est divisible par 4 et quand même temps elle n'est pas divisible par 100 ou au contraire qu'elle est divisible par 400, alors elle est bissextile, sinon elle ne l'est pas.

Algorithme de principe

Entier annee
Debut Programme
Écrire "Veuillez saisir l'année"
lire annee
si (annee mod 4=0) et ((annee mod 100>0) ou (A mod 400=0)) alors
Écrire "L'année ", annee, "est bissextile."
sinon
Écrire "L'année ", annee, "n'est pas bissextile."
fin de si
fin Programme

IV - Les tris

Télécharger la source exemple Les différents tris en vb.net [ftp://www.ftp-developpez.com/selkis/fichiers/lestris.zip].

IV-A - Le tri à bulles

Plus astucieux que le tri_par selection, le principe du tri à bulle est de faire remonter petit a petit un élément trop grand vers le haut du tableau en comparant les éléments 2 à 2.

Si l 'élément de gauche est supérieur à son voisin de droite on les inverse et on continue avec le suivant.

Lorsque l'on est en haut du tableau, on repart au début et on s'arrête lorsque tous les éléments sont bien placés.

J.Essai 1

taille = 0

éléments du tableau : 4 1 3 9 6 8 7 0 5 2

J.Essai 2

taille = 1

éléments du tableau : 0 4 3 1 2 8 5 6 7 9

J.Essai 3

taille = 10

éléments du tableau : 2 3 4 5 1 6 7 8 9 0

Principe (tableau (4)= 9 1 4 2 )

Algorithme

' i: entier // indice de parcours de la table d'entiers
' inversion : booléen //vrai quand il y a eu au moins 1 inversion
' tampon : entier : variable intermédiaire permettant l'inversion de 2 entiers du tableau

faire
inversion = faux
Pour i allant de 0 à FinTableau -1
// comparaison de l'élément en cours à son suivant
Si tableau(i) > tableau(i + 1) alors
// il faut inverser les deux éléments du tableau
tampon = Tableau(i)
Tableau(i) = Tableau(i + 1)
Tableau(i + 1) = tampon
//il y a eu au moins une inversion
inversion = vrai
Fin de si
Fin de pour
Jusqu'à (inversion=faux)

Optimisation de l'algorithme

Cette version du tri à remontée des bulles arrête de trier le tableau quand il ne reste plus de nombre à trier.

L'emplacement de dernière inversion donne la longueur utile pour le prochain parcours.

' i: entier // indice de parcours de la table d'entiers
' der_inversion : entier //indique l'endroit de la dernière inversion ou 0
' tampon : entier : //variable intermédiaire permettant l'inversion de 2 entiers du tableau

tant que fintableau >1 faire
der_inversion : = 0
i : = 1 // début du nouveau parcours
Répéter
// comparaison de l'élément en cours à son suivant
Si tableau(i) > tableau(i + 1) alors
// il faut inverser les deux éléments tableau
tampon = Tableau(i)
Tableau(i) = Tableau(i + 1)
Tableau(i + 1) = tampon
//il y a eu au moins une inversion
der_inversion : = 1 // note l'emplacement de la dernière inversion
Fin de si
i : = i + 1 //passage à l'élément suivant
jusqu'à i = fintableau //arrêt sur le dernier élément
fintableau : = der_inversion // le prochain parcours ne triera pas la fin du tableau (déjà trié)
Fin tant que

IV-B - Le tri par sélection

Dans cet algorithme nous allons travailler sur un tableau de 10 entiers.

Jeu d'essai

52

10

1

25

62

3

8

55

3

22

Principe

Le tri par sélection consiste à chercher le plus petit élément du tableau pour le placer en 1er, puis de chercher le plus petit élément dans le reste et de le mettre en second, etc.

On stocke dans la variable petit le 1er élément du tableau, puis on reparcourt le tableau en partant de l'indice en cours jusqu'à la fin pour chercher si un élément est plus petit que lui.

Si c'est le cas, on va remplacer la valeur de la variable petit par la nouvelle valeur trouvée puis stocker dans la variable position à quelle position du tableau on l'a trouvée . La deuxième boucle va nous permettre de mettre le plus petit élément trouvé à la bonne place et de décaler les autres éléments.

Algorithme

Pour i allant de 1 à (findutableau) -1 faire
Petit = tableau(i)
Pour j allant de i à (findutableau) faire
Si tableau(j) < petit alors
Petit = tableau(j)
Position=J
Fsi
Fin de pour
Pour j allant de position à ( i + 1) pas -1
tableau(j) = tableau(j - 1)
Fin de pour
Tableau(i)=petit
Prochain i

IV-C - Le tri par Permutation

Le tri par permutation est le tri du jeu de cartes.

Principe

On parcourt le tableau jusqu'à ce que l'on trouve un élément plus petit que le précédent donc mal placé.

On prend cet élément et on le range à sa place dans le tableau, puis on continue la lecture.

On s'arrête à la fin du tableau.

Jeu d'essai

52

10

1

25

62

3

8

55

3

23

1re boucle

10

52

1

25

62

3

8

55

3

23

2e boucle

1

10

52

25

62

3

8

55

3

23

3e boucle

1

10

25

52

62

3

8

55

3

23

4e boucle

1

3

10

25

52

62

8

55

3

23

5e boucle

1

3

8

10

25

52

62

55

3

23

6e boucle

1

3

8

10

25

52

55

62

3

23

7e boucle

1

3

3

8

10

25

52

55

62

23

8e boucle

1

3

3

8

10

23

25

52

55

62

Algorithme

i,j,k,permute : entier

POUR i ALLANT DE 1 À 9
FAIRE
SI(TAB(i+1)<TAB(i)) ALORS
permute    <--TAB(i+1);
j<--1;
TANTQUE ((j<i) ET (TAB(j)<TAB(i+1)))
FAIRE j<--j+1
FTQ
POUR k ALLANT DE i+1 À j+1 PAS -1
FAIRE
TAB(k)<--TAB(k-1)
FIN POUR
TAB(j)<--permute;
FSI
FINPOUR

IV-D - Le tri par comptage

Le tri par comptage consiste pour chaque élément du tableau à compter combien d'éléments sont plus petits que lui, grâce à ce nombre, on connaît la position dans le tableau résultat.

Jeu d'essai

52

10

1

25

62

3

8

55

3

23

Nombre tableau [nb]

7

4

0

6

9

1

3

8

1

5

Position

8

5

1

7

10

2

4

9

3

6

Résultat

1

3

3

8

10

23

25

52

55

62

Le tableau [nb] contient le nombre d'éléments plus petits que celui passé en index.

Position est égal au nombre d'éléments plus petits que celui passé en paramètre + 1 (+ 2 pour le cas des doubles).

Algorithme

Pour i allant de 1 à (fin de tableau)
Res(i) = 0
Nb(i) = 0
'calcul des compteurs
Pour j allant de 1 à (fin de tableau)
Si tableau(j) < tableau(i) alors
Nb(i) = nb(i) + 1
Fin de si
Fin de pour
Fin de pour
Pour i allant de 1 à (fin de tableau)
j = nb(i)
Tant que res(j) <> 0 'cas des doubles
j = j + 1
Fin de tant que
Res(j) = tableau(i)
Fin de pour

V - Factorielle, récursivité et répétitive

Le principe de la fonction factorielle et de multiplier un nombre donné (nb_donnée) par tous ses inférieurs.

Exemple factorielle(4) = 4 * 3 * 2 * 1 = 24.

Pour faire ce genre de calcul en informatique, on fait appel en général à une fonction récursive…

Une fonction récursive est une fonction qui s'appelle d'elle-même, phénomène infini dont la question essentielle est de trouver la condition d'arrêt. (Ici nb_donnée.)

EXEMPLE RÉCURSIF

Factorielle(nb_donné)
si nb_donné=1 alors
factorielle(1)=1
sinon
factorielle=nb_donné * factorielle (nb_donnée-1)
fin si
fin fonction

Pour mieux comprendre imaginer une télé qui transmet une image dans laquelle il y a une télé qui transmet une image… et ainsi de suite, ou un miroir reflétant un miroir reflétant lui-même un autre miroir… et ainsi de suite.

Une fonction récursive peut être transformée en répétitive chaque fois que la récursivité est terminale.

Une fonction est dite terminale lorsque dans le bloc de la fonction ou de la procédure, il n'y a pas d'instruction qui suit l'appel récursif comme c'est le cas dans l'exemple récursif.

EXEMPLE RÉPÉTITIF

factorielle(nb_donné)
résultat =1
pour k=1 à nb_donné
résultat=résultat * k
next k
factorielle= résultat
fin fonction

VI - Recherche Dichotomique

Soit une table contenant des prénoms, classés par ordre alphabétique, nous désirons chercher l'indice de la case du tableau où se trouve un prénom dans ce dit tableau ,s'il s'y trouve.

Le principe est assez simple…

On va commencer par lire le tableau, le prénom à rechercher, stocker la valeur 1 dans la variable inférieur et la longueur du tableau dans la variable supérieur.

Ensuite on va déterminer le milieu du tableau et initialisé la valeur trouve à faux.

Il nous reste plus qu'a écrire la boucle qui va nous permettre de trouver notre élément

La boucle consiste à délimiter le tableau et à le redimensionner de plus en plus petit à chaque fois que l'on fait un tour de boucle.

La première fois on se positionne sur le milieu du tableau et on regarde le prénom, si c'est le bon c'est du bol trouvé du premier coup, sinon on regarde si notre prénom est plus grand ou plus petit.

S'il est plus grand, alors on va lui dire que la nouvelle borne de départ est le milieu du tableau + 1 élément pour pouvoir se positionner sur le prochain.

S'il est plus petit alors c'est l'inverse, c'est notre borne de fin qui va changer, elle va remonter jusqu'au milieu du tableau -1 cette fois.

Puis on remonte, comparer notre condition : est-ce que ma borne de fin est toujours plus grande que le début.

DÉBUT PROGRAMME
LIRE tableau
LIRE prénom
inferieur =1
superieur = longueur du tableau
Tant que superieur >inferieur ET trouve <> 0 faire
milieu = PartieEntiere (inferieur + superieur) / 2
Si prenom(milieu) <> prenom alors
Si prenom > prenom(milieu) alors
Inferieur=milieu + 1
Sinon
Superieur=milieu - 1
Fin si
Sinon
Trouve=milieu
Fin de si
Fin de tant que
FIN PROGRAMME