Exercices sur les tableaux
Exercice 1
Ecrire un programme (doit comporter au moins trois fonctions) permettant de saisir
deux vecteurs v1 et v2 d’entiers naturels strictement positifs avec v 1(k)≤100 et
v2(k)≤100, de calculer puis d'afficher le vecteur produit vp=v 1 X v2 ainsi que le
vecteur de comparaison vc avec vc(k)=1 si le résultat du produit est correcte sinon
vc(k)=0 ; selon le principe suivant:
1. Initialiser les vecteurs vp et vc à 0 ;
2. Pour chaque indice k
a. Si (v1(k) < v2(k)) alors permuter les contenus des deux éléments
v1(k) et v2(k) ;
b. Ajouter v2(k)2 à vp(k) ;
c. Affecter à v1(k) la valeur de (v1(k) - v2(k)) ;
d. Répéter les actions a, b et c jusqu'à ce que v1(k) ou v2(k) soit nul ;
e. Comparer le résultat du produit du principe donné.
Exemple
v1 1 23 6 11
v2 3 14 27 10
v1[2] v1[2] vp[2] vc[2]
- - 0 0
23 14 0+196=196
14 9 196+81=27
7
9 5 277+25=30
2
5 4 302+16=31
8
4 1 318+1=319
3 1 319+1=320
2 1 320+1=321
1 1 321+1=322
1 0 322 1
3. Afficher les vecteurs vp et vc.
Exercice 2
Ecrire un programme (doit comporter au moins trois procédures) permettant de :
1. générer un vecteur v d’une façon automatique et aléatoire de n entiers
strictement positifs, inférieurs ou égaux à 1000, avec (5≤n≤30).
2. Vérifier pour l’élément de V d’indice p donné, s’il est égal à la somme
d’un certain nombre d’éléments consécutifs de V qui le précèdent.
3. Afficher ces éléments s’ils existent avec leur indices sous format (élément,
indice) sinon afficher « l’élément d’indice p ne vérifie pas la propriété en
question ».
Exemple :
Pour le tableau V suivant, avec n=10
2 1 5 6 14 7 33 10 44 8
p=4 : l’élément v(4)=6 : 5+1 Afficher (5,3),(1,2)
p=5 : l’élément v(5)=14 : 6+5+1+2 …
p=7 : l’élément v(7)=33 : 7+14+6+5+1 …
p=9 : l’élément v(9)=44 : 35+10 …
4. Comment peut-on généraliser vos procédures pour vérifier la somme d’une
combinaison de certain nombre d’éléments de V qui précèdent l’élément
p ? (Ex : 7=5+2 ; 10=7+1+2)
Exercice 3
Soit un tableau T de n caractères (5 ≤ n ≤ N max) qui ne peuvent être que "A", "B" ou
"C" et tels que deux éléments successifs du tableau ne sont pas égaux. (N max est une
constante de valeur 30).
On se propose d'insérer un caractère donné « c » dans la première position possible
dans le tableau T en respectant la règle ci-dessus mentionné puis d'afficher le tableau
T dans son nouvel état (après insertion).
NB:
Le caractère « c » ne peut être que "A", "B" ou "C" et ne peut être
insérée ni à la première ni à la dernière position du tableau.
On suppose que l'insertion d'un nouveau élément est possible en
effet n < Nmax.
Ecrire un programme (doit comporter procédures) permettant cette insertion.
Exercice 4 : Tri de Shaker (amélioration du tri à bulle)
Ce tri est une légère amélioration du tri à Bulle dans la mesure où il permet
non seulement aux plus grands éléments de migrer vers la fin du tableau mais aussi
aux petits éléments de se rapprocher du début du tableau.
Cette méthode consiste tout d’abord à comparer T[i] et T[i+1] et à échanger
ces éléments si T[i] > T[i+1] et ceci pour tout i de 1 à n-1. A la fin de la 1ère boucle,
T[n] contient le plus grand élément du tableau et ce nème élément ne doit plus être
prise en compte dans la suite du tri. Si on agit de même mais en partant du dernier
élément et en vérifiant si T[i] et T[i+1] pour i allant de n-2 à 1, le plus petit élément
prendra sa place définitive après la première boucle.
Il suffit de recommencer ensuite le même processus avec le morceau de T
allant de la 2ème élément à la n-1ème jusqu’au moment où les indices de fin et de
début se rejoignent ou aucun échange n’a été effectué.
Ecrire une procédure TriShaker(T[1..N]: tableau d'entier, n: entier) qui tri le
tableau T par cette méthode.
Exercice 5 : Tri Shell (amélioration du tri par insertion)
Pour ramener un élément de la fin vers la tête, dans le tri par insertion, il faut
décaler tous les éléments plus grands. On va donc, réaliser un tri par insertion sur des
éléments séparés par h cases pour faire moins de décalage. On obtient un tableau
entrelacé partiellement trié ; on fait décroître h jusqu’à 1 pour finir de trier le tableau.
Ecrire une procédure TriShell(T[1..N]: tableau d'entier, n: entier) qui tri le
tableau T par cette méthode.
Exercice 6 : Tri d’une suite d’entiers
1. Ecrire les procédures permettant de trier par ordre croissant une
suite d’entiers. Nous considérerons les méthodes suivantes :
Tri Shell
Tri de Shaker
Tri fusion
Tri rapide
Le type suite d’entiers est défini comme suit :
Const Taille_Max = 10 ;
Type SuiteEntiers = record
nbElements : integer;
elements : array[1.. Taille_Max] of
integer ;
end ;
2. Classer les 4 procédures de tri suivant le temps d’exécution pour
une suite de 10000 éléments.
