|
|
C15. Vecteurs - Programmation PASCAL Corrigé
Exercice 1 : gestion des polynômesSupposons que nous voulions manipuler des polynômes de la forme :
P(x)= c1xe1 + c2xe2+ .. + cnxen (1)
avec a) e1 > e2 .. > en
b) n<=20
c1, c2, .. cn sont des réels
e1, e2, .. en sont des entiers compris entre 0 et 19.
Un tel polynôme peut être représenté par une structure dont le premier élément indique le nombre de termes non nuls et dont le second élément est un tableau à deux dimensions o� chaque ligne représente le couple (ci, ei).
Ecrire les modules suivants :
Point(P, V) : fonction qui rend la valeur P(V)
Somme(P, Q, R) : somme des polynômes P et Q; résultat dans R.
Produit(P, Q, R) : produit des polynômes P et Q; résultat dans R.
Dérivé(P, V) : dérivé du polynôme P; résultat dans R.
Ecrire une procédure PASCAL qui imprime le polynôme P sous la forme (1).
NB. On définira le type polynôme comme suit :
TYPE Polynome = STRUCTURE
Nbr : ENTIER { Nombre d'éléments non nuls }
Tab : TABLEAU[40, 2] DE REEL { Les monômes }
FIN
Exercice 2 : Accès par fonction
On a défini sur les vecteurs deux types d'accès :
- l'accès séquentiel
- l'accès dichotomique
Si l'on veut faire de l'accès séquentiel, on construit le vecteur de telle sorte que l'ordre des éléments est quelconque. Par contre, si on veut faire de l'accès dichotomique l'ordre des éléments est imposé.
On peut envisager un autre type d'accès que l'on définit comme suit :
Soit à construire un vecteur V à partir d'une liste de N valeurs V
1,V2,.. Vn. On définit une fonction F qui à toute valeur Vi attribue un entier compris entre 1 et N. L'élément Vi est alors rangé à la place F(Vi). Comme on ne peut dans la pratique trouver une fonction F qui attribue une valeur différente à chaque élément de V, il se peut que l'on ait :F(V
i) = F(Vj) = F(Vk)= . . = F(Vt)Dans ce cas
- l'élément V
i sera rangé dans le vecteur à la position F(Vi)- les autres V
j, Vk, .. , Vt seront rangés dans un vecteur V' de telle sorte qu'ils soient liés entre eux comme le montre la figure ci-dessous :
F(V) = (V + 5) Mod N + 1
N = 10
Valeurs : 6, 12, 10, 9, 8, 7, 16, 2, 3, 0, 5, 26, 32.
L'élément 10 est rangé à la place 6 car F(10) = 6
Dans l'exemple on a F(6) = F(16) = F(26) = 2; le premier élément 6 est rangé à la place 2 et est lié au second élément 16 par l'indice 1; 16 et 26 sont rangés dans V' et sont liés entre eux par l'indice 4.; l'élément 7 est rangé dans V à la position 3; il n'est lié à aucun élément.
Exercice 3 : Tri de couleurs
Soit un vecteur de N éléments contenant 3 types de couleurs : vert(V), rouge(R) et blanc(B) . Ecrire un algorithme qui ordonne les couleurs comme suit :
RRR... BBBBB... VVVVV