Hello tout le monde !

Voilà j'ai un exercice en Python sur le jeu du juste prix :

Exercice 3 (Le juste prix, ? ? ?) Le juste prix consiste à deviner le prix d’un objet (un entier rond, inférieur ou égal à 100 euros) en faisant des propositions de prix, l’autre joueur indiquant si on est au-dessus ou en-dessous du prix réel.

1. En vous inspirant de l’exercice précédant, programmez le jeu du juste prix où c’est l’humain qui doit deviner le prix. Il a droit à 7 propositions. Indication : int(’42’) == 42.

2. Quelle stratégie adoptez-vous pour gagner à coup sûr ?

3. Programmez le jeu où c’est l’ordinateur qui fait des propositions et l’humain qui répond « au-dessus » ou « au-dessous ». L’ordinateur a droit à 7 propositions et devra gagner à coup sûr, ou afficher un message spécial si l’humain a triché dans ses réponses. 

J'ai bien réussi à écrire l'algorithme de la question 1 mais je ne comprend pas la 2eme et la 3eme question quand ils parlent d'une stratégie pour gagner à coup sûr?

Pourriez vous m'éclairer sur cette stratégie si vous réussissez à comprendre le sens de la question?

Merci bien !

Salut,

Comme ton prix est entre 0 et 100euros, si tu utilises la dichotomie, tu peux trouver le prix en 7 étapes a coup sur car c'est le plus petit entier tel que 2^n > nb_choix :

2^6 = 64 < 100 mais 2^7 = 128 > 100

Du coup, la stratégie c'est la dichotomie et tu dois le coder pour que l'ordi devine ton nombre en maximum 7 étapes.

Bon courage

A toi de regarder le lien qu'il t'a donné, qui contient même plusieurs algorithmes pour résoudre ton problème...

OC est un forum d'entraide, pas de demande de code.

https://openclassrooms.com/forum/sujet/regles-de-ce-forum-a-lire-avant-de-poster-1

Je ne demande pas de code, je demande juste un exemple d'application de la méthode.

Mais merci quand même

Bah tu as un range de 0 à 100,

Tu coupes a 50

Si le nb est superieur a 50

    tu gardes la partie 51 - 100

Si le nb est plus petit que 50

   tu gardes la partie 0-49

Et tu ré-itère jusqu'a  avoir un seul choix (sauf si tu trouves avant biensur)

A noter que ce qu'il vient d'expliquer est la version littérale de l'algo qui est présent sur le lien.

recherche_dichotomique_récursive(élément, liste_triée):
   m = longueur de liste_triée / 2 ;
   si liste_triée[m] = élément :
       renvoyer m ;
   si liste_triée[m] > élément :
       renvoyer recherche_dichotomique_récursive(élément, liste_triée[1:m]) ;
   sinon :
       renvoyer recherche_dichotomique_récursive(élément, liste_triée[m:l]) ;

J'ai une nouvelle question,

Voici donc l'algorithme que j'ai défini : 

def juste_prix_ordi():

    #On demande au joueur de choisir un chiffre entre 0 et 100
    prix = -1
    while prix < 0 or prix > 100:
        prix = int(input("Choisissez un prix entre 0 et 100"))
        

    nb_essai = 0 #On compte le nombre d'essais qu'il a fallu à l'ordinateur
                 #Pour trouver la réponse
    #On définit les bornes de départ à savoir x = 0 et y = 100
    born_inf = 0
    born_sup = 100
    #On définit m, le juste prix recherché
    m = 0

    #J'ai gagné dit l'ordinateur !
    ais_je_gagne = False
    #Si jamais l'humain aurai des envies de triche
    tricheur = False


    #On applique la méthode de la dichotomie
    #Etant donné qu'on applique la dichotomie, l'ordi continuera de faire
    #des propositions tant que x != y
    while nb_essai < 6 and ais_je_gagne == False and tricheur == False:
        
        #l'ordi propose donc un premier chiffre en accord avec le principe de la dichotomie
        m = ( born_inf + born_sup ) // 2
        print("Je pense que le juste prix est", m)
        #Le joueur doit répondre ensuite au dessus ou en dessous
        reponse = input("Qu'en pensez vous?")
        #On applique ensuite les formules de la dichotomie selon la réponse du joueur
        if reponse == "au dessus":
            born_inf = m + 1
            nb_essai += 1
        elif reponse == "en dessous":
            born_sup = m - 1
            nb_essai += 1
        #On vérifie directement à la fin de l'itération si l'ordinateur a déjà trouvé le chiffre.
        if born_inf == born_sup:
            m = born_inf # m prend la valeur de n'importe laquelle des bornes inf ou sup car elles sont égales
            ais_je_gagne = True
        elif born_inf > born_sup:
            tricheur = True

    #On est en dehors de la boucle WHILE , nous avons donc soit trouvé le bon résultat
    #ou alors le joueur est un vilain tricheur !
    if ais_je_gagne == True:
        print("J'ai trouvé ! Le juste prix est", m, "et tu ne peux pas me contredire !")
    if tricheur == True:
        print("Vous les êtres humains n'avez aucune considération pour nous les robots! J'arrête de jouer tricheur!")

Il a l'air de fonctionner, mais je me posais une question : Si je décide que le juste prix est 75, comment l'ordi va-t-il le détecter étant donné qu'il commence à borne_inferieur + borne_superieur / 2.

Il va me demander si c'est > à 50, je répond "au dessus", mais là du coup vu qu'il fait (51+100)/2 = 75, il me demande si c'est au dessus ou en dessous de 75.. Du coup il ne peut jamais arriver à 75..

Une idée?

   sinon :
       renvoyer recherche_dichotomique_récursive(élément, liste_triée[m:l]) ;

Wikipédiaaa~

Non mais ça va j'ai compris le principe de la dichotomie, inutile de me renvoyer sur wikipedia en plus sur un algo qui s'applique à des listes.. (Et qui plus est algo récusif, je suis sur de la dichotomie par itération là..)

J'aimerai une explication litérale de pourquoi ça me fait ça et de si mon programme applique bien la dichotomie

En plus là j'applique exactement cet algo :

//déclarations
 début, fin, val, mil, N : Entiers
 t : Tableau [0..N] d'entiers classé
 trouvé : Booléen
 
//initialisation
 début ← 0 
 fin ← N
 trouvé ← faux
 Saisir val

//Boucle de recherche
  Répéter
   mil ← partie entière((début + fin)/2)
   Si t[mil] = val alors
     trouvé ← vrai
   Sinon
     Si val > t[mil] Alors
       début ← mil+1
       
     Sinon
       fin ← mil-1
       
     FinSi
    FinSi
   // La condition début inférieur ou égal à fin permet d'éviter de faire
   // une boucle infinie si 'val' n'existe pas dans le tableau.
   Tant que trouvé = faux ET début ≤ fin
//Affichage du résultat
Si trouvé Alors
     Afficher "La valeur ", val , " est au rang ", mil
  Sinon
     Afficher "La valeur ", val , " n'est pas dans le tableau"
FinSi

Donc je comprend pas ce qui cloche.

-
Edité par GamerStone 13 septembre 2017 à 16:49:56

Je n'ai pas testé précisement le code mais voici les points que tu pourrais améliorer :

• le ais_je_gagne == False ne sert a rien, il te suffit de break 
• evite le surplus de commentaire car ça rend le code difficile a lire
• le nb_essai doit etre incrémenté après chaque choix pas que si c'est + ou -
• Pour facilier le debugage, t'eviter les typo avec "au dessus" et "en dessous" stocke ton choix et compare directement.
• Dans ton cas tu stockes ton choix dans prix il n'y a donc pas de raison de ne pas s'en servir
• le while doit inclure aussi 6 (nb_essai <= 6)

Ca donnerai un code comme ca (peut etre a debugger):

def juste_prix_ordi():
    prix = -1
    while prix < 0 or prix > 100:
        prix = int(input("Choisissez un prix entre 0 et 100"))
         
    nb_essai = 0 
    born_inf, born_sup  = 0, 100

    while nb_essai <= 6:
        m = ( born_inf + born_sup ) // 2
        print("L'ordi propose", m)
        nb_essai += 1
        if prix > m:
            print("Trop bas")
            born_inf = m + 1
        elif prix < m:
            print("Trop haut")
            born_sup = m - 1
        else:
            print("Gagné en {} essais".format(nb_essai ))
            break

Dernier petit point, ca aurait du sens d'envoyer en input de ta fonction le range et la valeur a chercher plutot que de faire l'input dans la focntion, du genre :

def dichotomie(prix, min=0, max=100, step_max=7 ):
    ...
 

Ca te permet de la réutiliser plus tard avec un range par exemple différent, un nb de step aussi

-
Edité par coni63 13 septembre 2017 à 17:41:08

# Bad:
while n < a or n > b:

# Good:
while not a <= n <= b: