Programmation Algorithmique/Tableaux

Un livre de Wikibooks.

Algorithmique
Algorithmique
Sommaire
Modifier ce modèle

Sections

[modifier] Algorithmes sur les tableaux

[modifier] 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 \N avec N \in \N \land N\ge 1
  • Paramètres en sortie : l'entier min. min \in \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 \le 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 \le t(x))

t[N] : Tableau d'Entier
// Soit t \in 1 \ldots N \to \N
min : Entier
// Soit min \in \N
i : Entier
// Soit i \in \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
//mint(m,1,N)

[modifier] 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

[modifier] 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

[modifier] 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

[modifier] 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é

[modifier] 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

[modifier] Algorithmes de tri à Bulles

Algorithme TriBulles (t : tableau d'entiers ; n : entier) { Trie par ordre croissant le tableau t contenant n éléments } Lexique i,j : entier Début

 Pour i := 1 à n-1 faire
   Pour j := 1 à n-i faire
     Si t[j] > t[j+1]
     Alors Echange(t,j,j+1)
     Fin Si
   Fin Pour
 Fin Pour

Fin

Récupérée de « http://fr.wikibooks.org/wiki/Programmation_Algorithmique/Tableaux »