Programmation algorithmique/Tableaux

Algorithmes sur les tableaux

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

• 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 $t\in 1\dots N\to \mathbb{N}$ avec $N\in \mathbb{N}\wedge N\ge 1$
• Paramètres en sortie : l'entier min. $min\in \mathbb{N}$
• Spécifications : min doit contenir la valeur du plus petit élément du tableau. Formellement : $min\in ran(t)\wedge \mathrm{\forall }x\cdot (x\in 1\dots N\Rightarrow min\le t(x))$. Avec $ran$ le co-domaine (range en anglais)de t.

• Algorithme :

Soit $mi{n}_t(m,a,b)=m\in ran(t)\wedge \mathrm{\forall }x\cdot (x\in a\dots b\Rightarrow m\le t(x))$

t[N] : Tableau d'Entier
// Soit $t\in 1\dots N\to \mathbb{N}$
min : Entier
// Soit $min\in \mathbb{N}$
i : Entier
// Soit $i\in \mathbb{N}$
min := t[1];
// $min=t(1)$
pour i de 2 à N
      // $i\in 2\dots N\wedge mi{n}_t(m,1,i-1)$
      si t[i] < min alors
            // $i\in 2\dots N\wedge mi{n}_t(m,1,i-1)\wedge t(i)<min$
            min := t[i]
            // $i\in 2\dots N\wedge mi{n}_t(m,1,i)\wedge t(i)=min$
      finsi
      // $i\in 2\dots N\wedge mi{n}_t(m,1,i)$
finPour
//$mi{n}_t(m,1,N)$

Recherche d'une valeur dans un tableau

• 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

• 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

• 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

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

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

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