Cours Algorithme PDF : la base de la programmation
Dans ce cours algorithme, nous présentons différentes notions d’algorithme afin de donner envie aux débutants. La maîtrise de l’algorithme est indispensable pour le métier de la programmation.
Cours Algorithme PDF : Initiation et présentation de quelques notions de bases
Dans cette partie nous allons voir des notions variées, un peu en “Vrac” pour vous donner envie et vous encourager à lire le cours.
Cours algorithme : un sous-prgramme ?
Un sous-programme est une partie du programme qui porte
une donné spécifique et qui peut être appelé par ce nom,
selon les besoins, pour exécuter une tâche bien déterminée.
Lorsque les problèmes se révèlent complexes et longs, on
peut utiliser plusieurs sous-programmes différents. Un sous-
programme peut appeler à son tour un sous-sous-programme qui
lui aussi peut appeler un sous-sous-sous-programme et ainsi de
suite.
En programmation, on distingue deux types de sous-
programmes :
Les fonctions qui renvoient des valeurs résultats et qui
peuvent faire partie d’une expression;
– Les procédures qui ne renvoient pas directement des valeurs
résultats et qui ne peuvent pas faire partie d’une expression,
mais qui sont appelées pour réaliser des taches précises.
Objectifs des sous-programmes: rappelons que la méthodologie utilisée à fin de résoudre des problèmes algorithmiquement était de les décomposer en sous problèmes moins compliqués : méthode descendante.
Une des solutions utilisées pour réaliser cela est les sous- programmes.
Les problèmes les plus élémentaires seront représentés par des sous-programmes.
Algorithme de tri
Trier : c’est ordonner un ensemble d’éléments, c’est-à-dire, les
ranger en ordre croissant ou décroissant :
Tri croissant: si l’élément d’indice I est inférieur ou égal à
l’élément d’indice I + 1,
Tri décroissant: si l’élément d’indice I est supérieur ou
égal à l’élément d’indice I + 1,
Le but du tri est de faciliter l’utilisation d’un ensemble de
données, par exemple pour un algorithme de recherche, fusion
…etc.
TRI INTERNE – TRI EXTERNE.
Un tri interne s’effectue sur des données présentes en mémoire centrale. L’accès aux informations ne prend que peu de temps. Pour évaluer le temps de calcul, on ne considère que le nombre de combinaisons et de permutations.
TABLEAUX A DEUX DIMENSIONS.
Définition.
Le type de base d’un tableau à une dimension est quelconque, il peut être en particulier de type tableau. On parlera alors d’un tableau de tableau. Ce dernier peut se déclarer de la manière suivante:
Var
T:tableau [T1] de tableau [T3] de T2;
Où:
T : la variable tableau à deux dimensions,
T1: type indice de la première dimension(lignes),
T3:type indice de la deuxième dimension (colonnes),
T2:type de base des éléments du tableau.
Pour simplifier, cette déclaration peut se faire de la manière suivante:
Var
T:tableau [T1,T3] de T2;
Exemple 5:
Var
T:tableau [1..3,1..4] d’entiers;
T sera donc une variable tableau à deux dimensions de 3 lignes et 4 colonnes.
Cours Algorithme : NOTION DE RECURSIVITE
On a vu dans le chapitre précédent qu’un sous-programme peut appeler un autre sous-programme.
Lorsqu’un sous-programme s’appelle lui même, on parle alors d’appel récursif.
La récursivité est donc la capacité d’une procédure ou fonction à s’appeler elle-même. Elle permet de résoudre
beaucoup de problèmes contenant des itérations complexes.
Lorsqu’un algorithme s’appelle lui-même, on parle de récursivité simple ou directe. Mais la récursivité peut être
cachée: lorsqu’un algorithme A appelle un algorithme B et que B appelle ensuite A, on parle alors de récursivité croisée ou indirecte.
Lorsqu’un algorithme s’appelle lui même, il est nécessaire que l’enchaînement des appels successifs connaisse une fin. La suite des actions à exécuter doit être finie : tout algorithme récursif doit contenir une condition qui assure la fin du nombre d’appels.
Exemple d’algorithmes
Algorithme Tri_Décroissant;
Var
T : tableau[1..100] de réels;
N,ij :entiers;
Aux :réel;
Début
SiN=0 alors
Ecrire(‘le tableau est vide)
Sinon
Pouri<-1àN-1 Faire
Pourj < i+1àN Faire
Si T[i] <T[j] Alors
1
← Tj];
Aux;
FinSi
FinPourj
FinPour i
FinSi
Fin
Algorithme Somme_deux_tableau;
Algorithme modification
Algorithme suppression d’un élément d’un tableau
Cet algorithme permet de supprimer, après confirmation, un élément connaissant sa position dans le tableau.
Algorithme Fusion_quelconque
Dans cet algorithme, on va copier les éléments d’un tableau T1 dans un tableau T et à leur suite, on copie ceux d’un autre tableau T2.
On note M : le nombre de cases remplies dans le tableau T2.
Var
T1,T2,T : tableau[1..100] de réels;
N,M,i :entiers;
Si(N=0)et(M=0)alors
Début Ecrire(‘Les deux tableaux sont vides’)
Sinon
Pouri<-1àN Faire
T1[]
T[]←
Finpour i
Pouri←-1àM Faire
T[N+i] <T2[];
Finpour i
FinSi
Fin
Algorithme :fusion de deux tableaux ordonnés
Dans ce cas les deux tableaux T1 et T2 sont déjà triés par ordre croissant ou décroissant. Le résultat de la fusion doit être un tableau T trié dans le même ordre.
Nous allons utiliser un compteur par tableau i, j, k. On va balayer les deux tableaux T1 et T2 en comparant leurs éléments, le plus petit (ou grand) va prendre sa place dans le tableaux T, puis on avance dans le tableau correspondant et dans le tableau T. Une fois qu’on a épuisé les éléments d’un tableau (T1 ou T2), on recopie le reste des éléments de l’autre tableau dans T.
Dans cet algorithme, on va fusionner deux tableaux triés par ordre croissant.
Var
T1,T2,T3 : tableau[1..100] de réels;
N,M,i,j,k,h :entiers;
Début
Si (N=0) et (M=0) alors
Ecrire(‘Les deux tableaux sont vides’)
Sinon
1;
1;
k 1;
Tantque (i<=N)et(j<= M) Faire
Si T1[i]>T2[j] alors
Sinon
T[k] T2[0]; j<j +1;
T[k]<-T1[]; i←-i+1;
FinSi
k<-k+1;
FinTantque
(*on a atteint soit N: la fin du tableau T1 ou M: la fin du tableauT2. Dans le premier cas, il faut compléter par le reste des éléments de T2 qui est (N+M-(k-1)) éléments.Dans le deuxième cas, il faut compléter par le reste des éléments de T1 qui est (N+M-(k-1)) éléments*)
Si i < N alors (*dans ce cas obligatoirement J>M*)
Pour h< iàN Faire
T[k]<T1[h];
k<-k+1;
FinPour h
Sinon (*dans ce cas obligatoirement i>N et j<M*)
Pour h < jà M Faire
T[k]< T2[h];
k<-k+1;
FinPour h
FinSl
FinSi
Autres articles
