[Problème]Dichotomie et C++
Résolu
Bonsoir,
J'ai un petit souci, je dois réaliser un programme en C++ dans lequel l'utilisateur saisi un nombre compris entre 0 et 999, et c'est l'ordinateur lui même qui doit trouver ce nombre en s'aidant avec la méthode dite dichotomique...
Vous avez pas une piste ? svp je n'ai vraiment pas d'inspiration pour trouver la soluce :(
Voici mon code un peu foireux lol.... xD
Si vous pouvez m'aider ! ce serait sympa :D !
J'ai un petit souci, je dois réaliser un programme en C++ dans lequel l'utilisateur saisi un nombre compris entre 0 et 999, et c'est l'ordinateur lui même qui doit trouver ce nombre en s'aidant avec la méthode dite dichotomique...
Vous avez pas une piste ? svp je n'ai vraiment pas d'inspiration pour trouver la soluce :(
Voici mon code un peu foireux lol.... xD
#include "stdafx.h"
#include <iostream>
using namespace std;
void main ()
{
int nombre;
int pc =100;
int diviseur = 1;
int plus;
int moins;
int i;
i = 0;
cout<<"Dichotomie"<<endl;
cout<<"Entrez un nombre : "<<endl;
cin>>nombre;
if (nombre ==100)
{
cout<<"J'ai trouve !"<<pc<<endl;
}
else if (pc != nombre)
{
diviseur = diviseur * 2;
pc = pc / diviseur;
cout<<pc<<endl;
}
do
{
if (pc<nombre)
{
moins = 0;
pc = pc + (pc/diviseur);
cout<<pc<<endl;
moins++;
}
else if (pc>nombre)
{
plus = 0;
pc = pc - (pc/diviseur);
cout<<pc<<endl;
plus++;
}
else if ((plus == 1)&&(moins==1))
{
diviseur = diviseur / 2;
}
i++;
}
while ((pc != nombre)||(i!=6));
cout<<"J'ai trouve"<<endl;
system("pause");
}
Si vous pouvez m'aider ! ce serait sympa :D !
Configuration: Windows XP Firefox 3.0.1
3 réponses
-
sl si tu dois utilisé la dichotomie c'est mieux d'utilser une version recursif plutot que itératif
je definit une fonction auxillaire recursif
int recherche(int a,int b , int c){
if (a+b)/2== c return c;
else {
if (a+b)/2<c recherche(a+b/2,b,c);
else recherche(a,a+b/2,c);
}
}
et donc ton programme principale
fait un appel a recherche(0,1000,c) ou c est a été fourni par l'utilisateur
je sai pa si ca répond a ta kestion
++ -
Mon code a un défaut c'est qu'il ne trouve que certains nombres :s et si il n'arrive pas à trouver le nombre exact, il part dans une boucle infinie :/
En ce qui concerne ton code je vais essayer de l'utiliser, mais j'aimerais avoir un peu plus de détails sur ta fonction (eh oui je débute :s)
En tout cas merci de ton aide ;) -
la fonction engadre la ou se trouve ton entier
si ton nombre est egale a la moitie de ton intervalle alors trouvé (youpi)
sinon tu divise ton intervalle par 2
si le nombre cherché > milieu de l'intervalle tu la cherche entre le milieu de l'intervalle et la fin
sinon c'est entre le debut et le milieu de ton intervalle
dsl de ne pa avoir commenté mon code
bonne continuation pour la suite
++
