Programmation algorithmique/Tableaux

Algorithmes sur les tableaux

modifier

Recherche du plus petit élément d'un tableau

modifier
  • Paramètres en entrée : un tableau t de N entiers. On pourra identifier ce tableau à une fonction totale de l'intervale entier de 1 à N vers les nombres naturels (on identifie les entiers machines aux nombres naturels). Ce qu'on l'on peut noter   avec  
  • Paramètres en sortie : l'entier min.  
  • Spécifications : min doit contenir la valeur du plus petit élément du tableau. Formellement :  . Avec   le co-domaine (range en anglais)de t.
  • Algorithme :

Soit  

t[N] : Tableau d'Entier
// Soit  
min : Entier
// Soit  
i : Entier
// Soit  
min := t[1];
//  
pour i de 2 à N
      //  
      si t[i] < min alors
            //  
            min := t[i]
            //  
      finsi
      //  
finPour
// 

Recherche d'une valeur dans un tableau

modifier
  • Paramètres en entrée : un tableau t de N entiers (indicé de 1 à N) et une valeur v
  • Paramètres en sortie : le booléen trouvé et l'entier indice.
  • Spécifications : le booléen trouvé doit être à vrai si v se trouve dans le tableau. La valeur d' indice est alors le plus petit indice de la case contenant la valeur v dans le tableau.
  • Algorithme :
t[N] : Tableau d'Entier
v : Entier
i, indice : Entier
trouve : Booleen;

trouve := FAUX
indice := -1
i := 0
tant que non trouve ET i <= N
    si t[i] = v alors 
          trouve := true
          indice := i
    sinon 
          i := i+1
    finsi
fin tant que

Somme des éléments d'un tableau

modifier
  • Paramètres en entrée : un tableau de N entiers
  • Paramètres en sortie : l'entier s.
  • Spécifications : s doit être égal à la somme des éléments du tableau.
  • Algorithme :
t[N] : Tableau d'Entier
i : Entier

s := 0;
pour i de 1 à N
  s := s + t[i]
fin pour

Recherche du nombre d'occurrences

modifier
  • Paramètres en entrée : un tableau de N entiers et une valeur v
  • Paramètres en sortie : l'entier nb.
  • Spécifications : nb doit être égal au nombre de fois que la valeur v apparait dans le tableau.
  • Algorithme :
t[N] : Tableau d'Entier
v : Entier
i, nb : Entier

nb := 0
pour i de 1 à N
   si t[i] = v alors
        nb := nb+1
   finsi
fin pour

Algorithme Recherche Dichotomique

modifier

fonction rechercheDicho(e : entier, n : entier, t : tableau entier[0..n-1]):entier

   début
       debut <- 0
       fin <- n-1
       trouve <- faux
       tant que debut <= fin et non trouve faire
           i <- (debut+fin)÷2
           si t[i] = e
               alors trouve <- vrai
               sinon si t[i] > e
                   alors fin <- i-1
                   sinon debut <- i+1
               fsi
           fsi
       ftant
       si trouve
           alors indice <- i
           sinon indice <- -1
       fsi
       retourne indice
   fin

Lexique :

   - e : entier, élément recherché
   - n : entier, taille du tableau
   - t : tableau entier[0..n-1], tableau trié par ordre croissant
   - debut : entier, début de la zone de recherche
   - fin : entier, fin de la zone de recherche
   - trouve : booléen, faux tant que l'élément cherché n'est pas trouvé
   - i : entier, indice de la case du milieu de la zone de recherche
   - indice : entier, indice de l'élément recherché ou -1 s'il n'est pas trouvé

Algorithme d'échange

modifier

Algorithme Echange (t : tableau d'entiers ; i,j : entiers) { Echange le contenu des cases i et j dans le tableau t } Lexique pro : entier Début

 pro  := t[i]
 t[i] := t[j]
 t[j] := pro

Fin

Algorithmes de tri à Bulles

modifier

Algorithme TriBulles

Var i, X, c, n: Entier;
    tableau t[100]: Entier;
Début
    Ecrire("Saisir la borne supérieur du tableau :");
    Lire(n);
    Pour i := 1 à n Faire
        Ecrire("Donner la valeur de l’élément :");
        Lire(t[i]);
    Fin de Pour
    Faire
       Pour i := 1 à n-1 Faire
           c := 0;
           Si t[i] > t[i+1] Alors
               X := t[i];
               t[i] := t[i+1];
               t[i+1] := X; 
               c := 1;
           Fin de Si
       Fin de Pour
    Tant que (c = 1)
Fin