La fausse pièce
Vous avez trouvé, sur une île déserte, une malle pleine de pièces d'or ! Elle contient 128 pièces.
Vous savez néanmoins qu'une des pièces est fausse.
Ce fabuleux trésor pourrait vous permettre d'acheter un nouveau bateau mais le marchand est très méfiant : s'il découvrait la fausse pièce, les choses tourneraient mal... Il vous faut donc trouver cette fausse pièce.
Heureusement vous savez que la fausse pièce est plus légère que les autres et vous disposez d’une balance à deux plateaux.
Cette balance ne donne pas la masse d’un objet, elle permet simplement de comparer les masses sur ses deux plateaux. Si les deux plateaux sont au même niveau, la masse est identique sur chacun, sinon le plateau le plus haut correspond à la masse la plus légère. Malheureusement, cette balance est piégée. Après 10 utilisations, elle s'auto-détruira.
Comme vous êtes bien organisé, vous commencez par numéroter les pièces (de 1 à 128), et vous collez ce numéro sur chaque pièce.
On dispose de la classe class Tresor qui permet de créer des objets de type Tresor constitués de 128 pièces dont une fausse déterminée aléatoirement lors de sa création.
On demande de rédiger la fonction fausse_piece qui prend en paramètres :
tresorde la classe Tresor ;- le numéro
debutde début de l'intervalle de recherche (inclus) ; - le numéro
finde fin de l'intervalle de recherche (exclu).
Cette fonction renvoie le numéro de la fausse pièce dans le trésor tresor
On garantit que :
- il existe une et une seule fausse pièce ;
- toutes les vraies pièces ont la même masse ;
- la masse de la fausse pièce est strictement inférieure à celle d’une vraie pièce.
Les pesées des pièces sont mises en œuvre par la fonction compare(tresor, debut_gauche, fin_gauche, debut_droite, fin_droite) qui compare les masses des pièces placées sur les plateaux de gauche et de droite.
Le plateau de gauche contient les pièces du trésor dont les numéros de début et de fin sont debut_gauche(inclus) et fin_gauche (exclu).
Le plateau de droite contient les pièces du trésor dont les numéros de début et de fin sont debut_droite (inclus) et fin_droite (exclu).
Cette fonction renvoie le côté de la balance le plus léger :
• la fonction renvoie 'gauche' si le plateau de gauche est plus léger ;
• la fonction renvoie 'équilibre' si les deux plateaux ont la même masse ;
• la fonction renvoie 'droite' si le plateau de droite est plus léger.
Ainsi, compare(tresor, 1, 15, 15, 50) compare les masses des pièces de numéros allant de 1 (inclus) à 15 exclu pour le plateau de gauche et de 15 (inclus) à 50 (exclu) pour le plateau de droite.
La fonction compare est déjà écrite, vous ne devez pas l’écrire. Votre fonction fausse_piece doit faire appel à la fonction compare. Attention, ce nombre d'appel doit être inférieur ou égal à 10.
On fournit ci-dessous quelques exemples d’utilisation des différentes fonctions
>>> tresor = Tresor()
>>> tresor
'Un trésor de 128 pièces'
>>> # comparaison des pièces de numéros dans [1, 20[ et [28, 32[
>>> compare(tresor, 1, 20, 28, 32)
'gauche'
>>> compare(tresor, 10, 40, 50, 80)
'équilibre'
>>> fausse_piece(tresor, 1, 129)
42
Recopier et compléter.
Toute tentative juste de résolution sera valorisée.
Exercice
Compléter ci-dessous :
# Tests(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)