Correct mais sans variant simple — et l'inverse
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 10 — Prouver et analyser : la boîte à outils formalisée
Énoncé
Montrer qu'un algorithme de recherche aléatoire du maximum peut être partiellement correct sans terminer.
Corrigé
Soit la fonction :
import random
def indice_max_hasard(t: list) -> int:
while True:
i = random.randrange(len(t))
if all(t[i] >= x for x in t):
return i
- Correction partielle : Le seul point de sortie est l'instruction
return iqui est conditionnée par le fait quet[i]soit supérieur ou égal à toutes les valeurs du tableau. Si la boucle s'arrête, la postcondition est donc nécessairement vraie. - Terminaison : Rien ne garantit l'arrêt. Il existe une probabilité non nulle (bien qu'infinitésimale) que le tirage aléatoire ne sélectionne jamais l'indice du maximum (ex: tirages répétés du même indice non optimal). Aucun variant entier strictement décroissant ne peut être défini.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.