C11 : Exercices

C11.E1 : Tri à bulle

Le tri à bulle consiste à parcourir un tableau, par exemple de gauche à droite, en comparant les éléments côte à côte et en les permutant s’ils ne sont pas dans le bon ordre.

Il faut ensuite recommencer.

On s’arrête dès que le tableau est trié, c'est à dire si aucune permutation n’a été faite au cours d’une passe.

C11.E2 : Fonction de fusion de deux listes triées

Trois algorithme de fusion de deux listes triées sont envisageables :

• - une version itérative qui supprime les valeurs des listes passées en paramètres au fur et à mesure que ces valeurs sont ajoutées dans la liste finale ;
• - une version itérative qui ne modifie pas les valeurs des listes passées en paramètres et se base sur les positions dans ces listes ;
• - une version récursive.

En fonction de la version que vous avez programmée dans l'activité C11.3, proposer le code des deux autres versions.

C11.E11 : Somme des nombres d'une liste

1) Proposer une fonction qui permet de calculer la somme des nombres d'une liste de nombre en vous appuyant sur un algorithme "diviser pour régner".

2) Le coût de cet algorithme est-il meilleur que celui de l'algorithme itératif ?

C11.E12 : Exponentiation rapide

On souhaite reprogrammer l'opérateur ** sous la forme d'une fonction (sans utiliser cet opérateur).

1) La première approche consiste à utiliser l'algorithme suivant :

def puissance_v1(x, n):
    p = 1
    for _ in range(n):
        p = p * x
    return p

Combien de multiplications cet algorithme effectue-t-il pour \(n = 100\) ?

2) Un méthode plus efficace consiste à considérer que :

• - si n est pair : \(x^n = x^{\frac{n}{2}} × x^{\frac{n}{2}}\)
• - si n est impair : \(x^n = x × x^{n-1}\)
• - si n = 0 : \(x^n = 1\)

3) Écrire le code d'un programme qui permet de visualiser sur un graphique le temps mis par chacun de ces deux algorithmes en fonction de \(n\).