Corrigé C16. Enoncé
Exercice 1 : Gestion des polynômes
Soit le Type Polynome défini comme suit :
TYPE T = STRUCTURE
Coef : ENTIER
Exp : ENTIER
FIN
TYPE Typemaillon = STRUCTURE
Val : T
Adr : Pointeur(Typemaillon)
FIN
TYPE Polynôme = Pointeur(Typemaillon)
Module Entrée
Nous supposons que
- les polynômes sont bien écrits ( pas d'erreurs)
- il n'y a aucun blanc entre la variable X et l'exposant
- les coefficients et les exposants sont des constantes entières
C'est à dire la syntaxe suivante
[Blancs][+/-] [Blancs][chch...][Blancs][ [X][chch...]][Blancs] désigne
0, 1 ou plusieurs blancs.
Les crochets désignent des parties facultatives
La partie [Chch...] après X n'est présente que si ce dernier est présent.
LIRE(C)
P := NIL
TANTQUE C # '*'
Coef := ' ;Exp :='
Signe := '+'
{Sauter les blancs}
TANTQUE C=' ' LIRE(C) FINTANTQUE
SI C='+' OU C='-' : Signe := C ; LIRE(C) FSI
{Sauter les blancs}
TANTQUE C=' ' LIRE(C) FINTANTQUE
TANTQUE Chiffre(C)
Coef := Coef + C
FINTANTQUE
{Sauter les blancs}
TANTQUE C=' ' LIRE(C) FINTANTQUE
SI C='X'
LIRE(C)
TANTQUE Chiffre(C)
Coef := Coef + C
FINTANTQUE
FSI
V.coef := Nombre(Coef)
V.exp := Nombre(Exp)
Allouer(Typedumaillon, Q)
Aff_val(Q, V)
Aff_adr(Q, nil)
SI P <> NIL Aff_Adr(P, Q)
SINON L := Q FSI
P := Q
FINTANTQUE
Module Point
FONCTION Point( P, V) : REEL
VAR P : Polynome
V : REEL
I : ENTIER
BEGIN
Res := 0
L := P
TANTQUE L # NIL :
Res := Res +
(Valeur(l).Coef * ( V ** Valeur(l).Exp ))
L := Suivant(L)
FINPOUR
Point := Res
FIN
Module Dérivée
ACTION Dérivé( P, Q)
VAR P, R : Polynome
BEGIN
R := NIL
TANTQUE P # NIL :
V.Coef :=
Valeur(P).Coef * ( Valeur(P).Exp - 1 )
V.Exp := Valeur(P).Exp - 1
SI Coef # 0 :
Allouer(Typemaillon, W)
AffVal(W,V)
SI
R#NIL :
AffAdr(R,W)
SINON
Q := R
FSI
R :=
W
FSI
FINTANTQUE
FIN
Module Somme
ACTION Somme(P, Q, R)
VAR P, Q, R : Polynome
DEBUT
L1 := P; L2 := Q ; R := NIL
TANTQUE L1 # NIL ET L2 # NIL:
Allouer(Typemaillon, w)
AffAdr(W, Nil)
SI Valeur(L1).Exp <
Valeur(L2).Exp :
AffVal(W, Valeur(L1) )
L1:= Suivant(L1)
SINON
SI Valeur(L1).Exp > Valeur(L2).Exp :
AffVal(W, Valeur(L2) )
L2:= Suivant(l2)
SINON
V.Coef := Valeur(L1).Coef + Valeur(L2).Coef
V.Exp := Valeur(L1).Exp
AffVal(W, V)
L1:= Suivant(L1)
L2:= Suivant(L2)
FSI
FSI
SI R#Nil :
AffAdr(R,W)
SINON
L3 := R FSI
R := W
FINTANTQUE
TANTQUE L1 # NIL :
Allouer(Typemaillon, W)
Aff-Val(W, Valeur(L1))
SI R# NIL : AffAdr(R,
W)
SINON L3 := W FSI
L := Suivant(L1)
FINTANTQUE
TANTQUE L2# NIL :
Allouer(Typemaillon, W)
Aff-Val(W, Valeur(L2))
SI R# NIL : AffAdr(R,
W)
SINON L3 := W FSI
L2 := Suivant(L2)
FINTANTQUE
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. Elle est définie comme suit :
Module prod :
ACTION Prod(P, M, O)
VAR P, O : Polynome
M : T
DEBUT
R := NIL
L := P
TANTQUE L # NIL :
V.Coef :=
Valeur(L).Coef * M.Coef
V.Exp := Valeur(L).Exp
+ M.Exp
Allouer(Typemaillon, W)
Aff-Val(w, v))
SI R# NIL : AffAdr(R,
W)
SINON O := W FSI
R := W
L := Suivant(L)
FINTANTQUE
FIN
Pseudo-ALGORITHME du produit :
1) R = P * premier terme de Q
POUR I = 2, Q.Nbre :
2) M := I-ème terme de Q
3) R := R + P*M
FINPOUR
Module Produit :
Produit(P, Q, R)
VAR P, Q, R, T, U :
Polynôme
I : ENTIER
1) DEBUT
L:= Q
M.Coef := Valeur(L).Coef
M.Exp := Valeur(L).Exp
Prod(P, M, R)
L := Suivant(L)
TANTQUE L # NIL :
2) M.Coef := Valeur(L).Coef
M.Exp := Valeur(L).Exp
3) Prod(P, M, T)
Somme(R, T, U)
R := U
L := Suivant(L)
FINTANTQUE
FIN
Exercice 2 : Accès par fonction
ALGORITHME HCODE
TYPE T = STRUCTURE
Val : Typeqq
Vide : Booleen
Lien : Pointeur (
Typmaillon)
FIN
VAR V : TABLEAU(1..M) DE T
DEBUT
POUR I=1, N
LIRE(Val)
H := F(I)
SI V(H).Vide :
V(H).Val := Val
SINON
SI V(H).Val = V :
ECRIRE('La donnée existe')
SINON
{Parcours de la liste}
P := V(h).Lien ; Trouv := FAUX
TANTQUE P # NIL ET NON Trouv :
SI Valeur(p) = V :
Trouv := VRAI
SINON
Q := P
P := Suivant(P)
FSI
FINTANTQUE
SI NON Trouv :
Allouer(R, Typmaillon)
AffVal(R, Val); AffAdr(R, NIL)
AffAdr(Q, R)
SINON
ECRIRE('la donnée existe')
FSI
FSI
FSI
FINPOUR
FIN