This page was exported from Enseignement de l'informatique et du numérique au lycée Boissy d'Anglas [ https://icn-isn-boissy.yj.fr/wp ]

Export date:Wed Feb 26 12:38:00 2025 / +0000 GMT

___________________________________________________


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

---------------------------------------------------



Exercice 1: Recherche valeur dans une liste



Algorithme:



fonction chercher : (tableau, clé) ----> booléen1. 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é sichercher(gauche, clé) ou chercher(droite, clé)est vrai.







Exempletableau = [4, 10, 20, 5]clé = 10A-t-on clé dans tableau ?Exempleclé = 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







quartdetourTélécharger


---------------------------------------------------


Images: https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2020/12/Capture.png

https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2020/12/Avatar_cat.png



---------------------------------------------------




---------------------------------------------------


Post date: 2020-12-14 14:27:09

Post date GMT: 2020-12-14 13:27:09

Post modified date: 2021-01-22 07:51:10

Post modified date GMT: 2021-01-22 06:51:10



____________________________________________________________________________________________


Export of Post and Page as text file has been powered by [ Universal Post Manager ] plugin from www.gconverters.com