sciences numériques et technologie (seconde) · Chapitre 7 · Exercice de TD
Prouver qu'il suffit de sept coups
Projets et mini-jeux · Le nombre mystère · niveau 3 (difficile)
Énoncé
La fonction deviner(secret) du cours cherche un entier de à par dichotomie.
- La faire tourner sur les valeurs possibles et relever le nombre maximal de coups, puis le nombre moyen.
- Démontrer la borne obtenue.
- Que devient cette borne si l'on cherche entre et ?
Corrigé de la question 1
1.
def deviner(secret):
bas, haut = 1, 100
coups = 0
while bas <= haut:
milieu = (bas + haut) // 2
coups = coups + 1
if milieu < secret:
bas = milieu + 1
elif milieu > secret:
haut = milieu - 1
else:
return coups
mesures = [deviner(s) for s in range(1, 101)]
print(max(mesures), sum(mesures) / 100) # 7 5.8Sept coups au pire, et en moyenne.
Question 2 : comment l'IA t'aide
- Démontrer la borne obtenue.
Élève
Pour la question 2, je ne vois pas trop ce qu'il faut démontrer : la question 1 a déjà donné le résultat avec le programme, non ?
IA
Le programme donne une mesure sur les valeurs, mais la question demande une preuve valable pour toutes les valeurs possibles. Regarde ce que fait la boucle à chaque tour : le milieu testé est éliminé. Combien de candidats restent au maximum après un coup ?
Élève
Au départ il y a candidats. Après un coup, le milieu est éliminé, donc il en reste au pire ? Ou alors la moitié, parce qu'on garde une seule des deux parts ?
IA
Les deux parts ne sont pas gardées : la comparaison élimine tout un côté. Mais elles ne sont pas forcément de même taille. Si tu dois garantir une borne dans le pire des cas, laquelle des deux parts faut-il considérer, et que devient le nombre de candidats au fil des coups ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.