Programmation algorithmique/Tableaux

Maths 1

Tris

Programmation algorithmique

Version imprimable

[ Modifier le sommaire ]

Maths 1

Tris

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\ldots N\to \mathbb {N}$ avec $N\in \mathbb {N} \land N\geq 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)\land \forall x\cdot (x\in 1\ldots N\Rightarrow min\leq t(x))$ . Avec $ran$ le co-domaine (range en anglais)de t.

Algorithme :

Soit $min_{t}(m,a,b)=m\in ran(t)\land \forall x\cdot (x\in a\ldots b\Rightarrow m\leq t(x))$

t[N] : Tableau d'Entier
// Soit  $t\in 1\ldots 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\ldots N\land min_{t}(m,1,i-1)$ 
      si t[i] < min alors
            //  $i\in 2\ldots N\land min_{t}(m,1,i-1)\land t(i)<min$ 
            min := t[i]
            //  $i\in 2\ldots N\land min_{t}(m,1,i)\land t(i)=min$ 
      finsi
      //  $i\in 2\ldots N\land min_{t}(m,1,i)$ 
finPour
// $min_{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