5 Tableaux

Exercice 1
Décrire une fonction qui calcule la somme des éléments d'un tableau.

fonction sommeElements (n : entier, t : tableau entier [0..n-1]) : entier
début
somme <- 0
pour i de 0 à n-1 faire
somme <- somme + t[i]
fpour
retourne somme
fin

Exercice 2
Décrire une fonction qui calcule l'élément maximal d'un tableau.

fonction maxTab (n : entier, t : tableau entier [O..n-1] : entier
début
max <- t[0]
pour i de 1 à n-1 faire
si max < t[i] alors
max <- t[i]
fsi
fpour
retourne max
fin

Exercice 3
Décrire une fonction qui indique si un élément est dans un tableau.

fonction chercheElement (n : entier, element : entier, t : tableau entier [O.. n-1] : booléen
début
presenceElement <- faux
i <- 0
tant que (presenceElement = faux) et (i < n) faire
si element = t[i] alors
presenceElement <- vrai
fsi
i <- i + 1
ftant
retourne presenceElement
fin

Exercice 4
Décrire une fonction qui donne l'indice du premier élément d'un tableau qui dépasse un seuil donné (-1 si aucun élément ne dépasse ce seuil).

fonction indicePremierSupSeuil (n : entier, t : tableau entier [O..n-1], seuil : entier) : entier
début
i <- 0
indice <- -1
trouver <- faux
tant que (trouver = faux) et (i < n) faire
si t[i] > seuil alors
trouver <- vrai
indice <- i
fsi
i <- i + 1
ftant
retourne indice
fin

Exercice 5 : tri par sélection du minimum
Décrire une fonction qui trie par ordre croissant les éléments d'un tableau selon le principe suivant : on parcourt le tableau pour repérer le minimum puis on l'échange avec la première valeur non encore triée. On répète ce processus (n-1) fois pour un tableau de n éléments.

fonction trie (n : entier, t InOut : tableau entier [O..n-1}
début
pour i de 0 à n-2 faire
min <- t[i]
indice <- i
pour j de i+1 à n-1 faire
si t[j] < min alors
min <- t[j]
indice <- j
fsi
fpour
si indice # i alors
t[indice] <- t[i]
t[i] <- min
fsi
fpour
fin

Exercice 6
Décrire une fonction qui calcule l'élément maximal d'un tableau à 2 dimensions.

fonction maxTab2D (li : entier, co : entier, t : tableau entier [O..li-1, 0..co-1]) : entier
début
max <- t[O,O]
pour i de 0 à li-1 faire
pour j de 0 à co-1 faire
si t[i,j] > max alors
max <- t[i,j]
fpour
fpour
retourne max
fin

Exercice 7
Dans la série de questions qui suit, un certain nombre d'algorithmes et de fonctions seront décrits de façon à permettre la gestion statistique du nombre de connexions à un serveur web. De façon générale, la donnée principale fournie sera un tableau de n entiers contenant le nombre de connexions enregistrée lors des n derniers mois écoulés.

Question 7.1
Ecrire un algorithme qui saisit le nombre n de mois d'étude et les n nombres de connexions mensuelles, les stocke dans un tableau, puis affiche le nombre minimum, maximum et moyen de connexions mensuelles.

Algorithme
début
n <- lire ()
nbrCnx [O] <- lire ()
min <- nbrCnx [O]
max <- nbrCnx [O]
tot <- nbrCnx [O]
pour i de 1 à n-1 faire
nbrCnx [i] <- lire ()
si min > nbrCnx [i]
si max < nbrCnx [i]
tot <- tot + nbrCnx [i]
fpour
moy <- tot / n
écrire (min, max, moy)
fin

Question 7.2
Ecrire une fonction qui permet de corriger nbr éléments successifs d'un tableau de nombres de connexions mensuelles (en cas de saisie erronée). Les nouvelles valeurs sont stockées dans un tableau.

fonction corrigerRelevé (n : entier, nbrCnx InOut : tableau entier [O..n-1], début : entier, nouv : tableau entier [O..nbr-1])
début
fin <- début + nbr-1
si fin > n-1 alors
fin <- n-1
fsi
pour i de début à fin faire
nbrCnx [i] <- nouv [i - début]
fpour
fin

Question 7.3
Ecrire une fonction qui permet d'inverser l'ordre des valeurs stockées dans un tableau de nombres de connexions mensuelles.

fonction inverse (n : entier, nbrCnx : InOut tableau entier [O..n-1])
début
i <- 0
j <- n-1
tant que (i < j) faire
tmp <- nbrCnx[i]
nbrCnx[i] <- nbrCnx[j]
nbrCnx[j] <- tmp
i <- i + 1
j <- j - 1
ftant
fin

Question 7.4
Ecrire une fonction qui permet de rentrer une nouvelle valeur (le nombre de connexions du dernier mois écoulé) dans le tableau, et met à jour le nombre minimum, maximum et moyen de connexions. On supposera que la case i contient toujours le nombre de connexions mensuelles enregistré i mois auparavant. On utilisera des fonctions qui calculent le nombre minimum (resp. maximum) de connexions mensuelles.

fonction ajouterValeur (n : entier, nbrCnx InOut : tableau entier [O..n-1], nouvelle : entier, min InOut entier, max InOut entier, moy InOut réel)
début
ancienne <- nbrCnx[n-1]
pour i décroissant de n-1 à 1 faire
nbrCnx[i] <- nbrCnx[i-1]
fpour
nbrCnx[0] <- nouvelle
total <- moy x n
total <- total + nouvelle - ancienne
moy <- total / n
si nouvelle <= min alors
min <- nouvelle
sinon si ancienne = min alors
min <- calculMin (n, nbrCnx)
fsi
fsi
si nouvelle => max alors
max <- nouvelle
sinon si ancienne = max alors
max <- calculMax (n, nbrCnx)
fsi
fsi
fin

Question 7.5
Un autre outil de traitement des connexions au site web stocke les nombres de connexions quotidiennes dans un tableau à 3 dimensions de taille n x 12 x 31 : la case [i,j,k] correspond au k-ième jour du j-ième mois de l'année 2007-i (si un jour n'existe pas, ou si le relevé n'est pas disponible, la case contient 0). Ecrire une fonction qui permet de transformer ce mode de stockage en un simple tableau de nombres de connexions mensuelles.

fonction transfert (na : entier, nbrCnx3 : tableau entier [0..na-1, 0..11, 0..30]) : tableau entier [0..na*12-1]
début
pour i de 0 à na-1 faire
pour j de 0 à 11 faire
nbrCnx[12*i + 11-j] <- 0
pour k de 0 à 30 faire
nbrCnx [12*i + 11-j] <- nbrCnx[12*i + 11-j] + nbrCnx3[i,j,k]
fpour
fpour
fpour
retourne nbrCnx
fin

Exercice 8 : Tri par sélection croisée
Décrire la fonction triCroissantSelectionCroisée qui réalise le tri du tableau par sélection du minimum et du maximum. On parcourt le tableau pour repérer à la fois son maximum et son minimum, puis on échange ces 2 valeurs avec respectivement la première et la dernière non encore triées. En itérant ce procédé (n-1)/2 fois pour un tableau de dimension n, on obtient un tableau trié. Attention : si l'élément maximum courant se trouve dans la première case encore non triée, et si cette case est d'abord permutée avec cell qui contient l'élément minimal courant, alors l'élément maximal se retrouve dans la case qui contenait l'élément minimal !

fonction triCroissantCroisé (n : entier, t InOut : tableau entier [O..n-1])
début
pour i de 0 à n÷2 -1 faire
min <- t[i]
indicemin <- i
max <- t[i]
indicemax <- i
pour j de i+1 à n-1-i
si t[j] < min alors
min <- t[j]
indicemin <- j
fsi
si t[j] > max alors
max <- t[j]
indicemax <- j
fsi
fpour
permuter t[i], t[indicemin]
si i = indicemax alors permuter t[n-1-i], t[indicemin]
sinon
permuter t[n-1-i], t[indicemax]
fsi
fpour
fin

Exercice 9 : tri bulle
Décrire la fonction triCroissantBulle. On parcourt le tableau en échangeant 2 cases consécutives mal ordonnées. On répète ce procédé tant que le tableau n'est pas trié.

fonction triCroissantBulle (n : entier, t InOut : tableau entier [O.. n-1])
début
i <- 0
changement <- vrai
tant que changement faire
changement <- faux
pour j de 1 à n-1-i faire
si t[j-1] > t[j] alors
tmp <- t[j]
t[j] <- t[j-1]
t[j-1] <- tmp
changement <- vrai
fsi
fpour
i <- i + 1
ftant
fin

Exercice 10 : fusion de tableaux triés
Décrire la fonction fusionTabTriésCroissant qui réalise la fusion de deux tableaux déjà triés par ordre croissant et retourne le tableau résultat.

fonction fusionTriésCroissant (n1 : entier, t1 : tableau entier [0..n1-1], n2 : entier, t2 : tableau entier [0..n2-1]) : tableau entier [0..n1+n2 - 1]
début
i <- 0
j <- 0
k <- 0
tant que i < n1 et j < n2 faire
si t1[i] < t2[j] alors
res[k] <- t1[i]
i <- i + 1
sinon
res[k] <- t2[j]
j <- j + 1
fsi
k <- k + 1
ftant
pour r de i à n1 - 1 faire
res[k] <- t1[r]
k <- k + 1
fpour
pour r de j à n2-1 faire
res[k] <- t2[r]
k <- k + 1
fpour
retourne res
fin