La fête foraine

Vous vous amusez à une fête foraine. Vous décidez de jouer au stand "Gagnez le gros lot !". Des lots visuellement identiques, numérotés de 1 à 32, sont exposés. Ils ont tous la même valeur de 1€, sauf un qui a la valeur de 100 €. Vous devez trouver une stratégie pour déterminer à coup sûr le numéro du lot de valeur 100 €.

La règle du jeu est la suivante : vous pouvez sélectionner deux groupes de lots, nommés groupe_1 et groupe_2. Le forain (qui connaît bien-sûr le numéro du gros lot) vous donnera une indication sur les valeurs globales de groupe_1 et groupe_2. Si les deux groupes ont la même valeur globale, il dira "identique", si le groupe_1 a plus de valeur, il dira "groupe_1", sinon il dira "groupe_2".

😥 Vous ne pouvez pas lui demander plus de six indications.

La classe Lots_en_jeu permet de créer une sélection de lots numérotés qui seront mis en jeu par le forain.

Vous devez rédiger la fonction gros_lot qui prend en paramètres :

lots de la classe Lots_en_jeu ;
le numéro debutde début de la zone de recherche (inclus) ;
le numéro fin de fin de la zone de recherche (exclu).

Cette fonction renvoie le numéro du lot de valeur 100 € dans lots.

Les indications données par le forain sont mises en oeuvre par indication(lots, debut_1, fin_1, debut_2, fin_2).

Le groupe_1 contient les lots dont les numéros de début et de fin sont debut_1 (inclus) et fin_1 (exclu). Le groupe_2 contient les lots dont les numéros de début et de fin sont debut_2 (inclus) et fin_2 (exclu).

Le résultat renvoyé sera :

"groupe_1" si le groupe_1 a la plus grande valeur ;
"identique" si les deux groupes ont la même valeur ;
"groupe_2" si le groupe_2 a la plus grande valeur.

Ainsi indication(lots, 1, 15, 15, 30) compare les valeurs totales des lots de numéros allant de 1 (inclus) à 15 (exclu) pour le groupe_1 et de 15 (inclus) à 30 (exclu) pour le groupe_2.

La fonction indication est déjà écrite, vous ne devez pas l’écrire.

On fournit ci-dessous quelques exemples d’utilisation des différentes fonctions :

🐍 Script Python

>>> lots = Lots_en_jeu()  # une sélection de 32 lots
>>> lots
'Une sélection de 32 lots'
>>> # comparaison des valeurs totales des groupes 
>>> # de lots dont les numéros sont dans [1, 20[ et [28, 32[
>>> indication(lots, 1, 20, 28, 32)
'groupe_1'
>>> indication(lots, 5, 15, 17, 27)
'identique'
>>> gros_lot(lots, 1, 33)
2

Votre fonction, pour 32 lots, ne doit pas appeler plus de 6 fois la fonction indication.

Toute tentative juste de résolution sera valorisée.

Exercice

Compléter ci-dessous :

###

# Testsbksl-nlfor i in range(10):bksl-nl lots = Lotspy-undenpy-undjeu()bksl-nl assert grospy-undlot(lots, 1, 33) == lots.npy-undgagnantbksl-nlbksl-nl# Autres Testsbksl-nlfor i in range(10):bksl-nl lots = Lotspy-undenpy-undjeu()bksl-nl assert grospy-undlot(lots, 1, 33) == lots.npy-undgagnantbksl-nl bksl-nl 5/5

#--- HDR ---#bksl-nlfrom random import randrangebksl-nlbksl-nlclass Lotspy-undenpy-undjeu():bksl-nl """bksl-nl Classe mettant en oeuvre un trésor de pièces d'orbksl-nl contenant une fausse piècebksl-nl """bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.taille = 32bksl-nl self.npy-undgagnant = randrange(1, self.taille + 1)bksl-nlbksl-nl self.valeur = randrange(1, 50)bksl-nl self.gagnant = 100py-strself.valeurbksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl """Renvoie la description des lots"""bksl-nl if self.taille > 1:bksl-nl return f"un jeu de {self.taille} lots"bksl-nlbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl """Renvoie la description des lots"""bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nlbksl-nldef indication(lots, debutpy-und1, finpy-und1, debutpy-und2, finpy-und2):bksl-nl """compare les valeurs totales des groupes groupepy-und1 et groupepy-und2.bksl-nlbksl-nl groupepy-und1 contient les lots dont les numéros de début et de fin sontbksl-nl debutpy-und1 (inclus) et finpy-und1 (exclu).bksl-nl groupepy-und2 contient les lots dont les numéros de début et de fin sontbksl-nl debutpy-und2 (inclus) et finpy-und2 (exclu).bksl-nlbksl-nl Cette fonction renvoie :bksl-nl py-str "groupepy-und1" si le groupepy-und1 a la plus grande valeurbksl-nl py-str "identique" si les deux groupes ont la même valeurbksl-nl py-str "groupepy-und2" si le groupepy-und2 a la plus grande valeurbksl-nlbksl-nl indication(lots, 1, 20, 28, 31) compare donc les valeursbksl-nl des lots de numéros :bksl-nl py-str allant de 1 (inclus) à 20 exclu pour le groupepy-und1bksl-nl py-str allant de 28 (inclus) à 31 exclu pour le groupepy-und2bksl-nl """bksl-nlbksl-nl if debutpy-und1 <= lots.npy-undgagnant < finpy-und1:bksl-nl valeurpy-und1 = (bksl-nl lots.valeur py-str (finpy-und1 - debutpy-und1 - 1) + lots.gagnantbksl-nl )bksl-nl else:bksl-nl valeurpy-und1 = lots.valeur py-str (finpy-und1 - debutpy-und1)bksl-nlbksl-nl if debutpy-und2 <= lots.npy-undgagnant < finpy-und2:bksl-nl valeurpy-und2 = (bksl-nl lots.valeur py-str (finpy-und2 - debutpy-und2 - 1) + lots.gagnantbksl-nl )bksl-nl else:bksl-nl valeurpy-und2 = lots.valeur py-str (finpy-und2 - debutpy-und2)bksl-nlbksl-nl if valeurpy-und1 < valeurpy-und2:bksl-nl return "groupepy-und2"bksl-nl elif valeurpy-und1 == valeurpy-und2:bksl-nl return "identique"bksl-nl else:bksl-nl return "groupepy-und1"bksl-nlbksl-nlbksl-nl#--- HDR ---#bksl-nlbksl-nlbksl-nldef grospy-undlot(lots, debut, fin):bksl-nl """bksl-nl Renvoie le numéro du gros lot dans lotsbksl-nl """bksl-nl ...bksl-nl bksl-nlbksl-nl# Testsbksl-nlfor i in range(10):bksl-nl lots = Lotspy-undenpy-undjeu()bksl-nl assert grospy-undlot(lots, 1, 33) == lots.npy-undgagnantbksl-nlbksl-nl bksl-nldef grospy-undlot(lots, debut, fin):bksl-nl """bksl-nl Renvoie le numéro du gros lot dans lotsbksl-nl """bksl-nl if debut + 1 == fin: # une seule pièce dans la zone d'étudebksl-nl return debutbksl-nlbksl-nl milieu = (debut + fin) // 2bksl-nl observation = indication(lots, debut, milieu, milieu, fin)bksl-nl if observation == "groupepy-und1":bksl-nl return grospy-undlot(lots, debut, milieu)bksl-nl else:bksl-nl return grospy-undlot(lots, milieu, fin)bksl-nlbksl-nlbksl-nl

On peut réaliser une version itérative de cette fonction, qui repose sur un algorithme de dichotomie.

🐍 Script Python

def gros_lot(lots, debut, fin):
    """
    Renvoie le numéro du gros lot dans lots
    """

    while debut < fin:
        if debut + 1  == fin:  # une seule pièce dans la zone d'étude
            return debut
        milieu = (debut + fin) // 2
        observation = indication(lots, debut, milieu, milieu, fin)
        if observation == "groupe_1":
            fin = milieu
        else:
            debut = milieu