Corrigé C15. Enoncé
Exercice 1 : Gestion des polynômes
Soit le type Polynome défini comme suit :
TYPE Polynome = STRUCTURE
Nbre : ENTIER
Tab : TABLEAU(40..2) DE
REEL
FIN
Module Point
FONCTION Point( P, V) : REEL
VAR P : Polynome
V : REEL
I : Entier
DEBUT
Point := 0
POUR I=1, P.Nbre :
Point := Point +
(P.Tab(I, 1) * ( V ** P.Tab(I, 2) ))
FINPOUR
FIN
Module Dérivée
ACTION Dérivé( P, V)
VAR P, R : Polynome
I, K, Coef: ENTIER
DEBUT
K := 0
POUR I=1, P.Nbre :
Coef := P.Tab(I, 1) *
P.Tab(I, 2)
SI Coef # 0 :
K := K + 1
R.Tab(K, 1) := Coef
R.Tab(K, 2) := P.Tab(I, 2) - 1
FSI
FINPOUR
R.Nbre := K
FIN
Module Somme
ACTION Somme(P, Q, R)
VAR P, Q, R : Polynome
I, J, K : ENTIER
DEBUT
K:=0; I, J := 1
TANTQUE I <= P.Nbre ET J <= Q.Nbre :
K := K + 1
SI P.Tab(I, 2) > Q.Tab(J,
2) :
R.Tab(K, 1) := P.Tab(I, 1)
R.Tab(K, 2) := P.Tab(I, 2)
I := I + 1
SINON
SI P.Tab(I, 2) < Q.Tab(J, 2) :
R.Tab(K, 1) := Q.Tab(J, 1)
R.Tab(K, 2) := Q.Tab(J, 2)
J := J + 1
SINON
Coef := P.Tab(I, 1) + Q.Tab(J, 1)
SI Coef # 0 :
R.Tab(K, 1):= P.Tab(I, 1) + Q.Tab(J, 1)
R.Tab(K, 2) := P.Tab(I, 2)
SINON K := K + 1
FSI
I := I + 1 ; J := J + 1
FSI
FSI
FINTANTQUE
TANTQUE I <= P.Nbre :
K := K + 1
R.Tab(K, 1) := P.Tab(I,
1)
R.Tab(K, 2) := P.Tab(I,
2)
I := I + 1
FINTANTQUE
TANTQUE J <= Q.Nbre :
K := K + 1
R.Tab(K, 1) := Q.Tab(J,
1)
R.Tab(K, 2) := Q.Tab(J,
2)
J := J + 1
FINTANTQUE
R.Nbre := K
FIN
Module Produit
On utilise l'action Prod(P, M, O) qui effectue le produit du polynôme P par le monôme M
et qui range le résultat dans le polynôme O. On utilise également l'action Affecter(P,
O) qui affecte le polynôme P au polynôme O. Elles sont définies comme suit :
Module Prod :
ACTION Prod(P, M, O)
VAR P, M, O : Polynome
I : ENTIER
DEBUT
O.Nbre := P.Nbre
POUR I=1,P.Nbre :
O.Tab(I, 1) := P.Tab(I,
1) * M.Tab(1, 1)
O.Tab(I, 2) := P.Tab(I, 2) *
M.Tab(1, 2)
FINPOUR
FIN
Module Affecter
ACTION Affecter(P, O)
VAR P, O : Polynome
I : ENTIER
DEBUT
O.Nbre := P.Nbre
POUR I=1,P.Nbre :
O.Tab(I, 1) := P.Tab(I,
1)
O.Tab(I, 2) := P.Tab(I,
2)
FINPOUR
FIN
Pseudo-algorithme du produit
1) R = P * premier terme de Q
POUR I = 2, Q.Nbre :
2) M := I-ième terme de Q
3) R := R + P*M
FINPOUR
Module Produit
ACTION Produit(P, Q, R)
VAR M, P, Q, R, T, U
: Polynome
I
: ENTIER
DEBUT
1) M.Nbre := 1
M.Tab(1, 1) := Q.Tab(1,
1)
M.Tab(1, 2) := Q.Tab(1,
2)
Prod(P, M, R)
POUR I=2, Q.Nbre :
2) M.Tab(1, 1) :=
Q.Tab(I, 1)
M.Tab(1, 2) := Q.Tab(I, 2)
3) Prod(P, M, T)
Somme(R, T, U)
Affecter(U, R)
FINPOUR
FIN
Procédure PASCAL qui imprime un polynôme
PROCEDURE Imprimer ( P : Polynome) ;
VAR
I : INTEGER ;
BEGIN
FOR I :=1 TO P.Nbre DO
WRITE(P.Tab[I, 1], 'x', P.tab[I,2] ) ;
END ;
Exercice 2 : Accès par fonction
Dans les trois Algorithmes qui suivent V et V' sont définis comme suit :
V : TABLEAU(N, 2) DE ENTIER
V' : TABLEAU(M, 2) DE ENTIER
Dans l'Algorithme d'insertion, on suppose que :
- 999 désigne le vide
T désigne le prochain emplacement libre dans V'
Dans l'algorithme de suppression, on peut procéder comme suit :
suppression logique : on ajoute un bit dans V'
suppression physique: on modifie les liens
Dans les deux cas, les emplacements libérés ne sont pas récupérés. Par conséquent
une mise à jour ultérieure est à prévoir.
On optera pour une suppression physique.
On utilisera le module Mettredans défini comme suit :
ACTION Mettredans (E, B)
VAR E : ENTIER
B : BOOLEEN
DEBUT
SI T <= M :
SI B : V(K,2) := T
SINON V'(K,2) := T FSI
V'(T, 1) := E
V'(T, 2) := 0
T := T + 1
SINON ECRIRE('Tableau V' saturé') FSI
FIN
Module de recherche
ALGORITHME Recherche
VAR E, I, J : ENTIER
Trouv : BOOLEEN
DEBUT
LIRE(E) { élément à rechercher }
I := F(E)
SI V(I, 1) = E :
ECRIRE ( 'l'élément
existe déjà )
SINON
J := V(I, 2)
Trouv := FAUX
TANTQUE J # 0 ET NON Trouv :
SI V'(J, 1) = E : Trouv := VRAI
SINON J := V'(J, 2) FSI
FINTANTQUE
SI Trouv : ECRIRE (
'l'élément existe déjà )
SINON ECRIRE (
'l'élément n'existe pas' ) FSI
FSI
FIN
Module d'insertion
ALGORITHME Inserer
VAR E, I, J : ENTIER
Trouv : BOOLEEN
DEBUT
LIRE(E) { élément à insérer }
I := F(E)
SI V(I, 1) = - 999 :
V(I, 1) := E ; V(I, 2)
:= 0
SINON
SI V(I, 1) = E :
ECRIRE ( 'l'élément existe déjà' )
SINON
J := V(I, 2)
SI J = 0 : Mettredans(E, VRAI)
SINON
Trouv := FAUX
TANTQUE J # 0 ET NON Trouv :
SI V'(J, 1) = E : Trouv := VRAI
SINON J := V'(J, 2) FSI
FINTANTQUE
SI Trouv : ECRIRE
( 'l'élément existe déjà' )
SINON Mettredans(E,FAUX) FSI
FSI
FSI
FIN
Module de suppression
ALGORITHME Supprimer
VAR E, I, J, K : ENTIER
Trouv : BOOLEEN
DEBUT
LIRE(E) { élément à supprimer }
I := F(E)
SI V(I, 1) = - 999 :
ECRIRE ( 'l'élément
n'existe pas' )
SINON
SI V(I, 1) = E :
SI V(I, 2) = 0 : V(I, 1) := - 999
SINON
V(I, 1) := V'(V(I, 2), 1)
V(I, 2) := V'(V(I, 2),2)
FSI
SINON
J := V(I, 2)
K := I
B := VRAI
Trouv := FAUX
TANTQUE J # 0 ET NON Trouv :
SI V'(J, 1) # E :
K := J ; B := FAUX
J := V'(J, 2)
SINON
Trouv := VRAI
{modifier les liens}
SI B : V(K, 2) := V'(J, 2)
SINON V'(K, 2):= V'(J, 2) FSI
FSI
FINTANTQUE
SI NON Trouv :
ECRIRE ( 'l'élément n'existe pas' )
FSI
FSI
FSI
FIN
Exercice 3 : Tri de couleurs
ALGORITHME Tri
CONST N = 10
VAR
T : TABLEAU[1..N] DE CAR
Limit,I, Pos : ENTIER
Temp : CAR
DEBUT
LIRE(T)
Pos := 1
POUR I:=1, N
SI T(I) = 'R'
SI Pos <> I
Temp := T(.Pos.)
T(.Pos.) := T(.I.)
T(.I.) := Temp
FSI
Pos := Pos + 1
FSI
FINPOUR
Limit := Pos
Pos := N
POUR I:=N, Limit, -1
SI T(I) = 'V'
SI Pos <> I
Temp := T(.Pos.)
T(.Pos.) := T(.I.)
T(.I.) := Temp
FSI
Pos := Pos - 1
FSI
FINPOUR
POUR I:= 1,N ECRIRE(T(I)) FINPOUR
FIN