Livre_silo 30 août 2013 16:32 Page 155
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
155
6 – Notions de complexité et algorithmique sur les tableaux
Exercice 6.6 *
1 Écrire une fonction qui prend un tableau d’entiers t en argument et renvoie le tableau des sommes
cumulées croissantes correspondantes, autrement dit un tableau de même taille dont la k-ième composante vaut
k
∑
i=0
t[i]. Le tableau fourni en argument ne sera pas modifié.
2 Évaluer la complexité de cette fonction.
3 Est-il possible d’en écrire une version plus efficace ?
Exercice 6.7 Écrire une fonction qui renvoie un tableau contenant les n premières valeurs de la suite de
Fibonacci (voir exercice 5.24).
6.3 Recherche dans un tableau
6.3.1 Recherche séquentielle
On cherche à déterminer si un tableau contient une certaine valeur. À la différence de la
section précédente, on ne va pas nécessairement examiner tous les éléments du tableau, car
on souhaite interrompre le parcours dès que l’élément est trouvé. Une solution consiste à
utiliser une boucle while, de la façon suivante :
def appartient(x, a):
i = 0
while i < len(a) and a[i] != x:
i += 1
return i < len(a)
Il est important de noter que le caractère paresseux du and est ici crucial : il évite l’accès
en dehors des bornes du tableau lorsque i atteint len(a). On peut procéder autrement en
utilisant la construction return à l’intérieur de la boucle pour interrompre son exécution.
Du coup, on peut de nouveau utiliser une boucle for comme dans la section précédente :
def appartient(x, a):
for y in a:
if y == x:
return True
return False
On va maintenant écrire une fonction de recherche légèrement différente, qui renvoie le
premier indice où la valeur x apparaît dans le tableau s. On utilise alors enumerate pour parcourir simultanément les indices et les valeurs correspondantes. Comme dans la fonction
précédente, la construction return fait sortir de la fonction dès que la valeur x est trouvée.
Si on sort de la boucle, on renvoie None pour signaler un échec de la recherche.
def indice(x, s):
for i, y in enumerate(s):
if y == x:
return i
return None
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
155
6 – Notions de complexité et algorithmique sur les tableaux
Exercice 6.6 *
1 Écrire une fonction qui prend un tableau d’entiers t en argument et renvoie le tableau des sommes
cumulées croissantes correspondantes, autrement dit un tableau de même taille dont la k-ième composante vaut
k
∑
i=0
t[i]. Le tableau fourni en argument ne sera pas modifié.
2 Évaluer la complexité de cette fonction.
3 Est-il possible d’en écrire une version plus efficace ?
Exercice 6.7 Écrire une fonction qui renvoie un tableau contenant les n premières valeurs de la suite de
Fibonacci (voir exercice 5.24).
6.3 Recherche dans un tableau
6.3.1 Recherche séquentielle
On cherche à déterminer si un tableau contient une certaine valeur. À la différence de la
section précédente, on ne va pas nécessairement examiner tous les éléments du tableau, car
on souhaite interrompre le parcours dès que l’élément est trouvé. Une solution consiste à
utiliser une boucle while, de la façon suivante :
def appartient(x, a):
i = 0
while i < len(a) and a[i] != x:
i += 1
return i < len(a)
Il est important de noter que le caractère paresseux du and est ici crucial : il évite l’accès
en dehors des bornes du tableau lorsque i atteint len(a). On peut procéder autrement en
utilisant la construction return à l’intérieur de la boucle pour interrompre son exécution.
Du coup, on peut de nouveau utiliser une boucle for comme dans la section précédente :
def appartient(x, a):
for y in a:
if y == x:
return True
return False
On va maintenant écrire une fonction de recherche légèrement différente, qui renvoie le
premier indice où la valeur x apparaît dans le tableau s. On utilise alors enumerate pour parcourir simultanément les indices et les valeurs correspondantes. Comme dans la fonction
précédente, la construction return fait sortir de la fonction dès que la valeur x est trouvée.
Si on sort de la boucle, on renvoie None pour signaler un échec de la recherche.
def indice(x, s):
for i, y in enumerate(s):
if y == x:
return i
return None