[Problème]Dichotomie et C++

Résolu/Fermé
Hyperyon Messages postés 5 Date d'inscription samedi 20 septembre 2008 Statut Membre Dernière intervention 10 septembre 2014 - 20 sept. 2008 à 22:12
oldirty Messages postés 21 Date d'inscription mercredi 3 septembre 2008 Statut Membre Dernière intervention 27 septembre 2008 - 21 sept. 2008 à 00:06
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

#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 !

3 réponses

oldirty Messages postés 21 Date d'inscription mercredi 3 septembre 2008 Statut Membre Dernière intervention 27 septembre 2008 4
20 sept. 2008 à 23:35
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
++
-2
Hyperyon Messages postés 5 Date d'inscription samedi 20 septembre 2008 Statut Membre Dernière intervention 10 septembre 2014
20 sept. 2008 à 23:56
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 ;)
-2
oldirty Messages postés 21 Date d'inscription mercredi 3 septembre 2008 Statut Membre Dernière intervention 27 septembre 2008 4
21 sept. 2008 à 00:06
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
++
-3