Le principe du “diviser pour régner” en Python EXERCICES

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=7⁵². 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  7²⁶× 7²⁶, c'est-à-dire( 7²⁶)². Là, il n'y a plus que 26 + 1 opérations (26 multiplications pour calculer 7²⁶, et une dernière pour faire le carré du résultat.

On recommence ensuite avec 7²⁶ : on le calcule en faisant (7¹³)².

 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=7⁵²

=(7²⁶)²

=((7¹³)²)²

=[[(7⁶)²×7]²]²

=[[((7³)²)²×7]²]²

=[[((7²×7)²)²×7]²]²

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

1. https://icn-isn-boissy.yj.fr/wp/wp-content/uploads /2021/01/quartdetour-1.pdf
2. https://icn-isn-boissy.yj.fr/wp/wp-content/uploads /2021/01/quartdetour-1.pdf