*Exercices de révision pour le contrôle de l'Algorithmique*
(tableaux-1dim-)

Exercice :  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 : Calcul d'un polynôme de degré N

Calculer pour une valeur X donnée du type reel la valeur numérique d'un polynôme de degré n:
P(X) = A_nXⁿ + A_n-1X^n-1 + ... + A₁X + A₀
Les valeurs des coefficients A_n, ... , A₀ seront entrées au clavier et mémorisées dans un tableau A de type reel et de dimension n+1. 
______________________________________
Exercice : 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 :  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 : 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 : 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.
_________________
- Le tri par sélection : 
          
  Le premier algorithme auquel on pense pour effectuer ce tri est celui-ci :
            On cherche le plus petit élément du tableau et on le place en 1er, puis on cherche le plus petit dans ce qui reste et on le met en second, etc …

52 10 1 25 62 3 8 55 3 23
1 52 10 25 62 3 8 55 3 23
1 3 52 10 25 62 8 55 3 23
1 3 3 52 10 25 62 8 55 23
1 3 3 8 52 10 25 62 55 23
1 3 3 8 10 52 25 62 55 23
1 3 3 8 10 23 52 25 62 55
1 3 3 8 10 23 25 52 62 55
1 3 3 8 10 23 25 52 62 55

1 3 3 8 10 23 25 52 55 62
            Ecrire l’algorithme qui permet de réaliser ce tri.
 
______________
- Le tri par bulle :

            Un tri bulle est un tri plus astucieux, son principe est de faire remonter petit à petit un élément trop grand vers le haut du tableau en comparant les éléments deux à deux.
            Si l’élément de gauche est supérieur à son voisin de droit on les inverse et on continue avec le suivant. Lorsque l’on est en haut du tableau on repart au début et on s’arrête lorsque tous es éléments sont bien placés.

52 10 1 25 62 3 8 55 3 23
10 52 1 25 62 3 8 55 3 23
10 1 52 25 62 3 8 55 3 23
10 1 52 52 62 3 8 55 3 23
10 1 25 52 62 3 8 55 3 23
10 1 25 52 3 62 8 55 3 23
10 1 25 52 3 8 62 55 3 23
10 1 25 52 3 8 55 62 3 23
10 1 25 52 3 8 55 3 62 23
10 1 25 52 3 8 55 3 23 62
On a parcouru tout le tableau, on recommence, jusqu’à ce que tout soit bien placé.

Ecrire l’algorithme qui réalise ce tri.
 
____________________
- Le tri par permutation : 
            
             Le tri par permutation est le tri du jeu de cartes.
            On parcourt le tableau jusqu’à ce que l’on trouve un élément plus petit que le précédent, donc mal placé. On prend cet élément et on le range à sa place dans le tableau puis on continue la lecture. On s’arrête à la fin du tableau.

52 10 1 25 62 3 8 55 3 23
10 52 1 25 62 3 8 55 3 23
1 10 52 25 62 3 8 55 3 23
1 10 25 52 62 3 8 55 3 23
1 3 10 25 52 62 8 55 3 23
1 3 8 10 25 52 62 55 3 23
1 3 8 10 25 52 62 55 3 23
1 3 8 10 25 52 55 62 3 23
1 3 3 8 10 25 52 55 62 23
1 3 3 8 10 23 25 52 55 62

            Ecrire l’algorithme qui réalise ce tri.
_________________
Le tri par comptage : 

            Le tri par comptage consiste pour chaque élément du tableau à compter combien d’éléments sont plus petits que lui, grâce à ce chiffre on connaît sa position dans le tableau résultat.
52 10 1 25 62 3 8 55 3 23
Nbre position
7  4 0 6 9 1 3 8 1 5
8 5 1 7 10 2 4 9 3 6
 
1 3 3 8 10 23 25 52 55 62
_________________
- Le tri alphabétique : 

            Le programme consiste à saisir des mots (au maximum 10) de 20 caractères maximum et de les insérer dans un tableau dans l’ordre alphabétique. Puis d’afficher ensuite ce tableau.
            Le tableau résultat est du type TABLEAU CAR [10, 20].

_________________________
 Exercice : 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

Pour telecharger cette série de révision clicker sur : 



Pour télécharger la correction de cette clicker sur :