Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Problème algorithme qui doit deviner un nombre

Posté par
Masoretro
16-10-16 à 15:22

Bonjour,
j'en suis encore dans ma première année et j'ai un petit soucis pour cet algorithme:

"Ecrire un algorithme qui devine le nombre choisi par l'utilisateur entre 1 et 1000 et qui aura à répondre à chacun des essais de l'algorithme l'un des trois caractères suivants: P (si l'essai est petit), T (si le programme a trouvé le résultat) ou G (si l'essai est grand). Méthode à suivre, le nombre se trouve dans l'intervalle [a,b] que l'on initialise à [1,1000]. On prend un nombre m = (a+b)/2 et on l'affiche. Si la réponse de l'utilisateur est G alors le nombre se trouve dans la moitié basse de l'intervalle et on change alors la valeur de b en lui affectant la valeur de m. Par contre si la réponse est P, alors on change a en lui affectant la valeur de m. On reprend à partir du calcul de m jusqu'à ce que la réponse de l"utilisateur devienne T."

ce que j'ai fait (je sais pas ce qui est juste/faux et j'aimerai avoir une aide):

Variables: a,b, N,m ;
{
Ecrire ("Donner un nombre entre 1 et 1000");
Lire (N);
a:=1;
b:=1000;
m:= (a+b)/2
      
     {
       répeter
         Si (m>N) alors
         b:=m;
         m:= (a+b)/2;
         Ecrire ("l'essai est grand");
        
         Sinon
         Si (m<N) alors
         a:=m
         m:= (a+b)/2
         Ecrire ("l'essai est petit");
      
         jusqu'à (m=N)
      }
Ecrire ("Le programme a trouvé le résultat");
}

Posté par
Tintin
re : Problème algorithme qui doit deviner un nombre 16-10-16 à 16:26

Bonjour,
ton algorithme de dichotomie me semble bien même si je n'ai pas reconnu le langage.
Un petit détail, qui peut avoir son importance, pour m je ferais en sorte de ne prendre que des nombres entiers, sinon tu risques de tourner autour de ta valeur sans jamais l'atteindre...

Posté par
carpediem
re : Problème algorithme qui doit deviner un nombre 16-10-16 à 18:44

salut

je plussoie au propos de Tintin ... même si c'est un détail ...

ensuite on peut légèrement simplifier :

Citation :
Variables: a,b, N,m ;
{
Ecrire ("Donner un nombre entre 1 et 1000");
Lire (N);
a:=1;
b:=1000;
m:= (a+b)/2
      
     {
       répeter
         Si (m>N) alors
         b:=m;
         m:= (a+b)/2;
         Ecrire ("l'essai est grand");
        
         Sinon
         Si (m<N) alors
         a:=m
         m:= (a+b)/2
         Ecrire ("l'essai est petit");
       m = (a + b)/2
         jusqu'à (m=N)
      }
Ecrire ("Le programme a trouvé le résultat");
}


on peut même faire mieux avec une boucle while plutôt qu'un repeat .... mais c'est aussi un détail ...

Posté par
Masoretro
re : Problème algorithme qui doit deviner un nombre 17-10-16 à 23:54

Merci Tintin pour ta remarque, j'ai essayer de prendre un réel pour m et je tourne toujours

sinon carpediem j'y ai pensé pour le while et je me suis dit que je devrais mettre ensuite 2 conditions (supérieur et inférieur) donc bon ça revient presque au même je trouve..

Merci sinon et bonne journée/soirée

Posté par
cocolaricotte
re : Problème algorithme qui doit deviner un nombre 18-10-16 à 00:19

Bonjour

Il faut quand même bien mettre """m:= (a+b)/2 "" au bon endroit dans la boucle , sinon m ne change pas de valeur et cela tourne indéfiniment !

Posté par
cocolaricotte
re : Problème algorithme qui doit deviner un nombre 18-10-16 à 00:20

pardon pas vu le m:= (a+b)/2   en fin de boucle !  

Posté par
mathafou Moderateur
re : Problème algorithme qui doit deviner un nombre 18-10-16 à 09:43

bonjour,

Citation :
Merci Tintin pour ta remarque, j'ai essayer de prendre un réel pour m et je tourne toujours

c'est justement le contraire de ce que dit tintin !!!
il ne faut pas prendre des réels mais des entiers.
exemple :

le nombre à trouver = 400 par exemple

j'essaie 500.5 (bein oui (1000+1)/2 !!)
trop grand (donc entre 1 et 500.5)
j'essaie 250.75 = (1+500.5)/2
trop petit (donc entre 250.75 et 500.5)
j'essaie 375.625 = (250.75 + 500.5)/2
trop petit (donc entre 375.625 et 500.5)
etc

la partie fractionnaire ne s'annulera jamais, elle est, modulo 0.5, divisée par deux à chaque fois

et donc on ne tombera jamais sur le nombre (entier) entre 1 et 1000 à deviner


d'autre part la compréhension même du problème posé est fausse.

Citation :
Ecrire ("Donner un nombre entre 1 et 1000");
Lire (N);
faux !!
le programme n'a rien à deviner si on lui donne directement le nombre à deviner !!!
ce nombre est le secret de l'utilisateur.
par contre c'est le programme qui propose des valeurs à l'utilisateur (en affichant m)
et l'utilisateur lui répond P, T ou G

donc on aura le dialogue :

afficher m
lire réponse
si réponse = "P"
// alors le nombre inconnu est entre m et b, modifier a
si réponse = "T"
// a lors le nombre a été trouvé, c'est m et c'est fini
si réponse = "G"
// alors le nombre inconnu est entre a et m, modifier b
sinon raler, la réponse doit être uniquement l'une de ces trois là

tout ça entièrement à l'intérieur de la boucle qui va bien
(un "tant que" ou un "répéter jusqu'à" au chois, mais le contenu sera légèrement différent selon la structure de boucle choisie)

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !