1.La recherche dichotomique fonctionne correctement sur un tableau non trié, tant que la valeur cherchée y figure effectivement.
2.Le nombre d’itérations de recherche_dichotomique sur un tableau de longueur n est majoré par ⌊log2(n)⌋+1.
3.Dans puissance_rapide, lorsque exposant est pair, on met à jour resultat en le multipliant par base.
4.D’après le cours, doubler la taille du tableau n’ajoute qu’une seule itération au majorant du nombre d’itérations de la recherche dichotomique.
5.Remplacer d = m - 1 par d = m dans recherche_dichotomique peut provoquer une boucle infinie.
On considère le tableau trié a=[1,4,6,9,13,18,25,31,40,52,67,75] (longueur n=12, indices 0 à 11).
Dérouler l’exécution de recherche_dichotomique(a, 31), en donnant à chaque itération les valeurs de g, d, m et a[m].
g=0, d=11, m=5, a[m]=18 (18<31, donc g <- 6)
g=6, d=11, m=8, a[m]=40 (40>31, donc d <- 7)
g=6, d=7, m=6, a[m]=25 (25<31, donc g <- 7)
g=7, d=7, m=7, a[m]=31 (31=31, on renvoie 7)
L’appel recherche_dichotomique(a, 31) renvoie donc 7, en 4 itérations.
Dérouler de la même façon l’exécution de recherche_dichotomique(a, 20) (valeur absente du tableau).
g=0, d=11, m=5, a[m]=18 (18<20, donc g <- 6)
g=6, d=11, m=8, a[m]=40 (40>20, donc d <- 7)
g=6, d=7, m=6, a[m]=25 (25>20, donc d <- 5)
On a alors g=6>d=5 : la boucle s’arrête, et l’appel renvoie None, en 3 itérations.
On souhaite calculer 225 par puissance_rapide(2, 25).
Écrire 25 en base 2, puis dérouler l’exécution de puissance_rapide(2, 25), en donnant à chaque itération la parité de exposant, ainsi que les nouvelles valeurs de resultat, base et exposant.
25=110012. Le déroulé :
exposant=25 (impair) : resultat=1*2=2, base=2*2=4, exposant=12
exposant=12 (pair) : resultat=2, base=4*4=16, exposant=6
exposant=6 (pair) : resultat=2, base=16*16=256, exposant=3
exposant=3 (impair) : resultat=2*256=512, base=256*256=65536, exposant=1
exposant=1 (impair) : resultat=512*65536=33554432, base=65536^2, exposant=0
La boucle s’arrête (exposant=0) et l’algorithme renvoie 33554432.
Vérifier que ce résultat est correct, et compter le nombre de multiplications effectuées (les deux mises à jour resultat = resultat * base et base = base * base comptent chacune pour une multiplication). Comparer à un calcul naïf par multiplications successives.
On vérifie que 225=33554432. Le déroulé ci-dessus comporte 5 itérations ; à chacune, base = base * base s’exécute (soit 5 multiplications), et resultat = resultat * base s’exécute uniquement lorsque exposant est impair, ce qui se produit 3 fois sur les 5 itérations (25, 3 et 1 sont impairs). Le nombre total de multiplications est donc 5+3=8, conforme au majorant 2⌊log2(25)⌋+2=2×4+2=10 du cours (le compte réel est ici strictement inférieur au majorant, car deux mises à jour de resultat sont évitées par la parité).
Le calcul naïf 2×2×⋯×2 (25 facteurs) effectuerait 24 multiplications : l’exponentiation rapide en économise ici 16.
5 blocs de plus : les autres énoncés et tous les corrigés, rédigés en entier. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.