Previous Next Up Index Contents

a) Tableaux à une dimension - Vecteurs



Exercice 7.8 Produit scalaire de deux vecteurs

Ecrire un programme qui calcule le produit scalaire de deux vecteurs d'entiers U et V (de même dimension).

Exemple:

   /          \   /          \
   | 3  2  -4 | * | 2  -3  5 | = 3*2+2*(-3)+(-4)*5 = -20
   \          /   \          /


Exercice 7.9 Calcul d'un polynôme de degré N

Calculer pour une valeur X donnée du type float la valeur numérique d'un polynôme de degré n:

P(X) = AnXn + An-1Xn-1 + ... + A1X + A0

Les valeurs des coefficients An, ... , A0 seront entrées au clavier et mémorisées dans un tableau A de type float et de dimension n+1.

a) Utilisez la fonction pow() pour le calcul.

b) Utilisez le schéma de Horner qui évite les opérations d'exponentiation:


Exercice 7.10 Maximum et minimum des valeurs d'un tableau

Ecrire un programme qui détermine la plus grande et la plus petite valeur dans un tableau d'entiers A. Afficher ensuite la valeur et la position du maximum et du minimum. Si le tableau contient plusieurs maxima ou minima, le programme retiendra la position du premier maximum ou minimum rencontré.


Exercice 7.11 Insérer une valeur dans un tableau trié

Un tableau A de dimension N+1 contient N valeurs entières triées par ordre croissant; la (N+1)ième valeur est indéfinie. Insérer une valeur VAL donnée au clavier dans le tableau A de manière à obtenir un tableau de N+1 valeurs triées.


Exercice 7.12 Recherche d'une valeur dans un tableau

Problème: Rechercher dans un tableau d'entiers A une valeur VAL entrée au clavier. Afficher la position de VAL si elle se trouve dans le tableau, sinon afficher un message correspondant. La valeur POS qui est utilisée pour mémoriser la position de la valeur dans le tableau, aura la valeur -1 aussi longtemps que VAL n'a pas été trouvée.

Implémenter deux versions:

a) La recherche séquentielle

Comparer successivement les valeurs du tableau avec la valeur donnée.

b) La recherche dichotomique ('recherche binaire', 'binary search')

Condition: Le tableau A doit être trié

Comparer le nombre recherché à la valeur au milieu du tableau,

- s'il y a égalité ou si le tableau est épuisé, arrêter le traitement avec un message correspondant.

- si la valeur recherchée précède la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à gauche de la position actuelle.

- si la valeur recherchée suit la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à droite de la position actuelle.

Ecrire le programme pour le cas où le tableau A est trié par ordre croissant.

Question: Quel est l'avantage de la recherche dichotomique? Expliquer brièvement.


Exercice 7.13 Fusion de deux tableaux triés

Problème: On dispose de deux tableaux A et B (de dimensions respectives N et M), triés par ordre croissant. Fusionner les éléments de A et B dans un troisième tableau FUS trié par ordre croissant.

Méthode: Utiliser trois indices IA, IB et IFUS. Comparer A[IA] et B[IB]; remplacer FUS[IFUS] par le plus petit des deux éléments; avancer dans le tableau FUS et dans le tableau qui a contribué son élément. Lorsque l'un des deux tableaux A ou B est épuisé, il suffit de recopier les éléments restants de l'autre tableau dans le tableau FUS.


Exercice 7.14 Tri par sélection du maximum

Problème: Classer les éléments d'un tableau A par ordre décroissant.

Méthode: Parcourir le tableau de gauche à droite à l'aide de l'indice I. Pour chaque élément A[I] du tableau, déterminer la position PMAX du (premier) maximum à droite de A[I] et échanger A[I] et A[PMAX].

Exemple:


Exercice 7.15 Tri par propagation (bubble sort)

Problème: Classer les éléments d'un tableau A par ordre croissant.

Méthode: En recommençant chaque fois au début du tableau, on effectue à plusieurs reprises le traitement suivant: On propage, par permutations successives, le plus grand élément du tableau vers la fin du tableau (comme une bulle qui remonte à la surface d'un liquide).

Exemple:

Implémenter l'algorithme en considérant que:

* La partie du tableau (à droite) où il n'y a pas eu de permutations est triée.

* Si aucune permutation n'a eu lieu, le tableau est trié.


Exercice 7.16 Statistique des notes

Ecrire un programme qui lit les points de N élèves d'une classe dans un devoir et les mémorise dans un tableau POINTS de dimension N.

* Rechercher et afficher:

- la note maximale,

- la note minimale,

- la moyenne des notes.

* A partir des POINTS des élèves, établir un tableau NOTES de dimension 7 qui est composé de la façon suivante:

NOTES[6] contient le nombre de notes 60

NOTES[5] contient le nombre de notes de 50 à 59

NOTES[4] contient le nombre de notes de 40 à 49

...

NOTES[0] contient le nombre de notes de 0 à 9

Etablir un graphique de barreaux représentant le tableau NOTES. Utilisez les symboles ####### pour la représentation des barreaux et affichez le domaine des notes en dessous du graphique.

Idée: Déterminer la valeur maximale MAXN dans le tableau NOTES et afficher autant de lignes sur l'écran. (Dans l'exemple ci-dessous, MAXN = 6).

Exemple:

 La note maximale est 58
 La note minimale est 13
 La moyenne des notes est 37.250000


   6  >                                 #######
   5  >                         ####### #######
   4  >                 ####### ####### #######
   3  >                 ####### ####### ####### #######
   2  >         ####### ####### ####### ####### #######
   1  >         ####### ####### ####### ####### #######
       +-------+-------+-------+-------+-------+-------+-------+
       I 0 - 9 I 10-19 I 20-29 I 30-39 I 40-49 I 50-59 I  60   I


Previous Next Up Index Contents


Feedback - Copyright © 1993,1996,1997 F.Faber