Developpez.com

Plus de 2 000 forums
et jusqu'à 5 000 nouveaux messages par jour

Developpez.com - Autres
X

Choisissez d'abord la catégorieensuite la rubrique :


Exemples d'algorithmes

Date de publication : 05/03/2005 , Date de mise a jour : 05/03/2005

Par Selkis (selkis.developpez.com)
 

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


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.1. Le tri à bulles
IV.2. Le tri par sélection
IV.3. Le tri par Permutation
IV.4. Le tri par comptage
V. Factorielle, recursivité 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 ecrire '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ère 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 Ecrire ('donnez une phrase terminée par un carctère ',carterm) Lire (phrase) //calcul de la longueur de la phrase j : = 1; Tantque (phrase[j]<>charterm) faire //arrêt sur le charactè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 Ecrire ('c'est un palindrome') sinon Ecrire ('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'occurences 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

4) La lettre recherchée est le terminateur
lettre '.'
Terminateur "."
Phrase "mon chien est gentil."
résultat 0

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

Programme compter_une_lettre Constantes charfind = 'a' // caractère dont les occurences sont comptées. charfin = "." //caractère de fin de chaîne. taille = 80 //nbr maximum de caractère 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 Ecrire('donnez une phrase terminée par un carctère ',charfin) Lire(phrase) i : = 1 compteur=0 //Parcours de la phrase avec recherche des carctères charfind //Il y a 0 ou plusieurs caractère à parcourir Tantque (phrase[i]<>charfin) faire //arrêt sur le charactè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 soit divisible par 400 alors elle est bissextile, sinon elle ne l'est pas.

Algorithme de principe
Entier annee Debut Programme Ecrire "Veuillez saisir l'année" lire annee si (annee mod 4=0) et ((annee mod 100>0) ou (A mod 400=0)) alors Ecrire "L'année ", annee, "est bissextile." sinon Ecrire "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 tri en vb.net

IV.1. 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 a 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 tout les élements 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édiare permetttant l'inversion de 2 entier du tableau faire inversion = faux Pour i allant de 0 a 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 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 i 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édiare permetttant l'inversion de 2 entier 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 pa la fin du tableau (déja trié) Fin tant que
Télécharger la source exemple Les différents tri en vb.net

IV.2. Le tri par sélection

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

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 élement dans le reste et de le mettre en second, etc…
On stock dans la variable petit le 1er élément du tableau puis on reparcour le tableau en partant de l'indice en cours jusqu'à la fin pour chercher si un élement est plus petit que lui.
Si c'est le cas on va remplacer la valeur de la variable petit par la nouvelle valeur trouvé puis stocker dans la variable position à quelle position du tableau on l'a trouvé . La deuxieme boucle va nous permettre de mettre le plus petit élément trouvé à la bonne place et de décaler les autres élement.

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
Télécharger la source exemple Les différents tri en vb.net

IV.3. 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écedent 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
1ere boucle 10 52 1 25 62 3 8 55 3 23
2ieme boucle 1 10 52 25 62 3 8 55 3 23
3ieme boucle 1 10 25 52 62 3 8 55 3 23
4ieme boucle 1 3 10 25 52 62 8 55 3 23
5ieme boucle 1 3 8 10 25 52 62 55 3 23
6ieme boucle 1 3 8 10 25 52 55 62 3 23
7ieme boucle 1 3 3 8 10 25 52 55 62 23
8ieme boucle 1 3 3 8 10 23 25 52 55 62
Algorithme
i,j,k,permute : entier POUR i ALLANT DE 1 A 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 A j+1 PAS -1 FAIRE TAB(k)<--TAB(k-1) FIN POUR TAB(j)<--permute; FSI FINPOUR
Télécharger la source exemple Les différents tri en vb.net

IV.4. Le tri par comptage

le tri par comptage consiste pour chaque élément du tableau à compter combien d'élément sont plus petit que lui, grâce à ce chiffre 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
Resultat 1 3 3 8 10 23 25 52 55 62
Le tableau [nb] contient le nombre d'element plus petit que celui passé en index
Position est egal au nombre d'element plus petit que celui passé en parametre + 1 (+ 2 pour le cas des doubles)
Algorithme
Pour i allant de 1 a (fin de tableau) Res(i) = 0 Nb(i) = 0 'calcule des compteurs Pour j allant de 1 a (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 a (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
Télécharger la source exemple Les différents tri en vb.net

V. Factorielle, recursivité et répétitive

Le principe de la fonction factorielle et de multiplier un chiffre donnée (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 appelle 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 RECURSIF
Factorielle(nb_donnée) si nb_donnée=1 alors factorielle(1)=1 sinon factorielle=nb_donnée * factorielle (nb_donnée-1) fin si fin fonction
Pour mieux comprendre imaginer une tele qui transmet une image dans laquelle il y a une tele qui transmet une image..et ainsi de suite , ou un miroir refletant un miroir refletant lui même un autre miroir et ainsi de suite..

Une fonction récursive peut etre transformée en répétitive chaque fois que la recursivité est terminale.
Une fonction est dite terminale lorsque dans le bloc de la fonction ou de la procédre, il n'y a pas d'instructions qui suivent l'appel récursif comme c'est le cas dans l'exemple recursif.

EXEMPLE REPETITIF
factorielle(nb_donnée) résultat =1 pour k=1 à nb_donnée 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 ou se trouve un prénom dans ce dit tableau ,si 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 a faux.

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

La boucle consiste a délimiter le tableau et a le redimensionner de plus en plus petit a 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.
Si 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.
Si 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 debut

DEBUT PROGRAMME LIRE tableau LIRE prenom 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 Trouvé=milieu Fin de si Fin de tant que FIN PROGRAMME

Liste de mes articles :
Algorithmes : Notions d'objets et d'actions
Algorithmes : Régles de programmation
Algorithmes : Les instructions répétitives, alternatives...


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.

Contacter le responsable de la rubrique Autres