Exemples d'algorithmesDate 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
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.
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.
IV. Les tris
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.
Principe (tableau (4)= 9 1 4 2 )
  
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.
IV.2. Le tri par sélection
Dans cet algorithme nous allons travailler sur un tableau de 10 entier.
Jeu d'essai
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. 
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.
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.
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).
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.
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
|
Copyright © 2005 selkis. Aucune reproduction, même partielle, ne peut être faite de ce site ni 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.
