Exemples d'algorithmes

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

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

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.

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

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

Sélectionnez

' 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.

 

Sélectionnez

' 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

Sélectionnez

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▲

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▲

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

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.)

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.

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

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