Livre_silo 30 août 2013 16:32 Page 154
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
154
Informatique pour tous
Là encore, il existe en Python une construction idiomatique, à savoir
for i, ai in enumerate(a) , qui donne simultanément l’indice et la valeur de chaque
case. Ainsi, on peut écrire :
def evaluer(a, x):
s = 0
for i, ai in enumerate(a):
s += ai * x**i
return s
Une méthode plus efficace pour évaluer un polynôme est d’utiliser la méthode de Horner.
Elle consiste à réécrire la somme précédente de la manière suivante :
A(X) = a 0 + X(a 1 + X(a 2 + · · · + X(a n−2 + Xa n−1 ) . . . ))
Ainsi, on évite le calcul des différentes puissances X
i , en factorisant intelligemment et en
ne faisant plus que des multiplications par X. Pour réaliser ce calcul, il faut parcourir le
tableau de la droite vers la gauche, pour que le traitement de la i-ème case de a consiste
à multiplier par X la somme courante, puis à lui ajouter a[i]. Si la variable s contient la
somme courante, la situation est donc la suivante :
A(X) = a 0 + X(· · · (a i + X(a i+1 + · · ·
s
)))
En Python, une manière de parcourir le tableau a de la droite vers la gauche consiste à
utiliser la construction for ai in reversed(a) . Ainsi, la méthode de Horner s’écrit comme
suit :
def horner(a, x):
s = 0
for ai in reversed(a):
s = ai + x*s
return s
On constate facilement que ce programme effectue exactement len(a) additions et autant
de multiplications, soit encore une complexité linéaire.
ATTENTION Utiliser la récursivité avec précaution
On pourrait être tenté d’écrire une version récursive de la méthode de Horner de la façon
suivante :
def horner_rec(p, x):
if len(p) == 0:
return 0
else:
return p[0] + x * horner_rec(p[1:], x)
Cette version évite notamment l’utilisation de reversed. Elle a cependant le défaut d’être
plus longue à exécuter. En effet, l’expression p[1:] réalise une copie des éléments du tableau, ce qui revient à effectuer len(p)-1 affectations. Au total, pour un tableau de taille
initiale n, ce programme effectuerait donc (n − 1) + (n − 2) + · · · + 1 affectations.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
154
Informatique pour tous
Là encore, il existe en Python une construction idiomatique, à savoir
for i, ai in enumerate(a) , qui donne simultanément l’indice et la valeur de chaque
case. Ainsi, on peut écrire :
def evaluer(a, x):
s = 0
for i, ai in enumerate(a):
s += ai * x**i
return s
Une méthode plus efficace pour évaluer un polynôme est d’utiliser la méthode de Horner.
Elle consiste à réécrire la somme précédente de la manière suivante :
A(X) = a 0 + X(a 1 + X(a 2 + · · · + X(a n−2 + Xa n−1 ) . . . ))
Ainsi, on évite le calcul des différentes puissances X
i , en factorisant intelligemment et en
ne faisant plus que des multiplications par X. Pour réaliser ce calcul, il faut parcourir le
tableau de la droite vers la gauche, pour que le traitement de la i-ème case de a consiste
à multiplier par X la somme courante, puis à lui ajouter a[i]. Si la variable s contient la
somme courante, la situation est donc la suivante :
A(X) = a 0 + X(· · · (a i + X(a i+1 + · · ·
s
)))
En Python, une manière de parcourir le tableau a de la droite vers la gauche consiste à
utiliser la construction for ai in reversed(a) . Ainsi, la méthode de Horner s’écrit comme
suit :
def horner(a, x):
s = 0
for ai in reversed(a):
s = ai + x*s
return s
On constate facilement que ce programme effectue exactement len(a) additions et autant
de multiplications, soit encore une complexité linéaire.
ATTENTION Utiliser la récursivité avec précaution
On pourrait être tenté d’écrire une version récursive de la méthode de Horner de la façon
suivante :
def horner_rec(p, x):
if len(p) == 0:
return 0
else:
return p[0] + x * horner_rec(p[1:], x)
Cette version évite notamment l’utilisation de reversed. Elle a cependant le défaut d’être
plus longue à exécuter. En effet, l’expression p[1:] réalise une copie des éléments du tableau, ce qui revient à effectuer len(p)-1 affectations. Au total, pour un tableau de taille
initiale n, ce programme effectuerait donc (n − 1) + (n − 2) + · · · + 1 affectations.