Exercice 1: Recherche valeur dans une liste
Algorithme:
fonction chercher : (tableau, clé) —-> booléen
1. Pour un tableau de taille 1, il contient la clé si valeur est la clé
2. On sépare le tableau en deux parties sensiblement de même taille (gauche et droite)
3. Le tableau contient la clé si
chercher(gauche, clé) ou chercher(droite, clé)
est vrai.
Exemple
tableau = [4, 10, 20, 5]
clé = 10
A-t-on clé dans tableau ?
Exemple
clé = 10
[4, 10, 20, 5]
diviser [4, 10] [20, 5]
diviser [4] [10] [20] [5]
combiner Faux ou Vrai Faux ou Faux
combiner Vrai ou Faux
combiner Vrai
Implémenter cette fonction sous python.
Exercice 2: Calcul y puissance x
On souhaite calculer N=752. La méthode basique consiste à multiplier le nombre 7 par lui-même 52 fois… Ce qui n’est pas très rapide !
L’idée consiste donc à diviser le problème en 2 : on va calculer 726× 726, c’est-à-dire( 726)2. Là, il n’y a plus que 26 + 1 opérations (26 multiplications pour calculer 726, et une dernière pour faire le carré du résultat.
On recommence ensuite avec 726 : on le calcule en faisant (713)2.
N se calcule alors en 13+1+1 opérations au lieu de 52 initialement.
On ne s’arrête pas là, bien entendu : on continue tant que l’on peut utiliser ce principe :
N=752
=(726)2
=((713)2)2
=[[(76)2×7]2]2
=[[((73)2)2×7]2]2
=[[((72×7)2)2×7]2]2
Le principe est, vous l’avez peut-être remarqué, récursif.
Implémentation en Python du “diviser pour régner”
Nous allons écrire une fonction “puissance(x,n)” basée sur ce paradigme, où x et n sont deux entiers (positif pour n). Pour cela, nous allons prendre en compte que:
Implémenter cette fonction avec python
Exercice 3: Faire pivoter une image
