Discussion :

[Hyperyon]

Bonjour,

Voilà je dois réaliser un petit programme dans lequel l'utilisateur dois saisir un nombre compris entre 0 et 999 et où l'ordinateur doit trouver ce nombre en utilisant la méthode dichotomique...

J'y ai déjà pas mal cherché, mais je ne trouve rien de probant



Merci d'avance de votre aide

[méphistopheles]

Heu c'est tout ?

Il manque pas un truc dans ton énoncé?

on dit pas à l'ordinateur si le nombre est au dessus ou en dessous ? (cas le plus classique)

Par-ce que si l'ordinateur peut faire ce qu'il veut, il n'a qu'à afficher le nombre directement .

Merci de poser des problèmes entiers et de ne pas nous prendre pour marabout.org.

D'autre part, on peut te donner une piste mais on ne te fera pas ton exo à ta place, et je pense ,si l'exo correspond à "au dessus, en dessous", que si tu te creuse la cervelle 10 seconde, tu trouvera la solultion.

[Hyperyon]

Non, l'ordinateur fait tout seul comme un grand, pas la peine de lui demander si c'est + ou - ou =... (désolé j'avais omis ce petit détail... pas la peine s'énerver )

Ca fait 3 jours que je cherche alors, c'est pour ça que je demande de l'aide lol et je n'ai jamais demandé la solution entière, juste de m'aider... ça fait à peine 3 semaines que je programme en C++ :/ donc juste un peu d'aide ce serait sympa ^^

Dans mon essai, j'ai tenté de faire un programme utilisant la dichotomie par itération, le hic c'est que soit il trouve la bonne réponse (ça arrive que très peu) soit le programme part dans une boucle infinie (du pure délire lol)

[JolyLoic]

si ça fait trois jours que tu cherches, tu as probablement écrit du code. Si tu ne le postes pas (de préférence nettoyé des choses annexes qui n'ont rien a voir avec ton problème, plus le code est petit, mais quand même suffisant, plus il a des chances d'être lu), on ne peut pas deviner où il a un problème.

[Sykaa]

J'vois pas trop comment tu peux faire de la dichotomie là dessus? tu choisi au hasard dans quel moitié tu regarde à chaque fois jusqu'à trouver un nombre? Ça revien a tirer un chiffre aletoire dans ta liste non .
Enfin si il faut vraiment faire par dichotomie tu peux peut-être tenir à jour un tableau pour voir quelles resultats tu as déjà visité, et quand tu arrive à un nombre, si tu a déjà tester que ce n'était pas celui choisi par l'utilisateur tu arrête et tu recommence la dichotomie... Mais j'arrive pas trop à saisir l'interet du truc enfaite... J'dirais comme mephisto, il manque pas qqchose dans l'énnoncé?

[buggen25]

bonjour,
Il faut définir l'intervalle ou dont tu es sure que la courbe de ta fonction traverse l'axe des abscisses

[Hyperyon]

Voici mon code mais ça foire un peu

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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"); 
}

Sinon une personne m'avait donné une solution, en utilisant une fonction récursive (ce que je n'ai pas encore vu en cours...)

ça donne ça (je copie tel quel qu'il me l'a donné)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
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);
}
}

Edit : J'ai pas trop bien compris son code, d'une il est mal indenté, et de deux, lorsque je lui demande de m'expliquer un peu, il me parle presque en Sms... c'est à n'y rien comprendre

[Hyperyon]

J'vois pas trop comment tu peux faire de la dichotomie là dessus? tu choisi au hasard dans quel moitié tu regarde à chaque fois jusqu'à trouver un nombre? Ça revien a tirer un chiffre aletoire dans ta liste non .
Enfin si il faut vraiment faire par dichotomie tu peux peut-être tenir à jour un tableau pour voir quelles resultats tu as déjà visité, et quand tu arrive à un nombre, si tu a déjà tester que ce n'était pas celui choisi par l'utilisateur tu arrête et tu recommence la dichotomie... Mais j'arrive pas trop à saisir l'interet du truc enfaite... J'dirais comme mephisto, il manque pas qqchose dans l'énnoncé?

Non je ne choisis pas au hasard, c'est l'ordinateur qui en fonction de ce que j'ai rentré comme valeur va comparer ma valeur à la sienne, et si la valeur de l'ordinateur est supérieur à la mienne, ce dernier va prendre la moitié inférieure et vice versa...

J'aurais déjà terminer l'exo depuis longtemps si on pouvait faire un programme qui testerait toutes les possibilités (un peu à la bruteforcing ) mais la prof veut pas... elle veut absolument le faire par dichotomie

[droggo]

Heo,

J'aurais déjà terminer l'exo depuis longtemps si on pouvait faire un programme qui testerait toutes les possibilités (un peu à la bruteforcing ) mais la prof veut pas... elle veut absolument le faire par dichotomie

L'exercice portant sur la dichotomie , ça me paraît pour le moins logique, non ?

[Frifron]

En fait je crois que l'interet de l'exercice est justement d'implémenter une recherche dychotomique sur un intervalle donnée. Le programme en lui même n'a évidemment aucun interet.

Si tu n'a pas vu les fonction recursives, tu n'est pas obligé de les utiliser, et une boucle while fera très bien l'affaire.

Maintenant ton algo me parait tordu. En fait une recherche dichotomique est très simple. Tu prend le milieu de l'intervalle, si c'est en dessous tu réduit l'intervalle a [debut,milieu] sinon a [milieur,fin] jusqu'a ce que tu tombes sur le nombre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
initialisation de l'intervalle
saisie de la valeur
si valeur est dans l'intervalle 
    faire
        valeur_courante = (debut_intervalle + fin_intervalle) / 2
        si (valeur < valeur_courante)
            fin_intervalle = valeur_courante
        sinon
            debut_intervalle = valeur_courante
    tant que valeur_courante != valuer
    La valeur est valeur_courante

Apres tu peux rajouter un compteur pour savoir en combien de passes tu trouve le nombre. Et puis il faut egalement tester le borne supérieure avant la boucle car a cause de la division des entiers, elle ne sera jamais atteinte

Après l'interet d'une recherche par dichotomie va plus apparaitre pour chercher un index dans un tableau d'entier trié par exemple et a le comparer avec une bete recherche linéaire. L'énoncé est un peu bizarre parceque la tu te retrouve a avoir un programme qui fais : "rentrer un nombre... Le nombre est :"

[EDIT] J'ai remplacé mon code par du pseudo code pour ne pas te donner la réponse directement. On est la pour t'aider pas pour te faire tes exo

[loufoque]

Un exercice plus intéressant c'est de faire ça avec lower_bound & co...

[Hyperyon]

Merci de votre aide les gens

Vais mettre en forme ton algo Frifron,

Je vous tiens au courant si ça fonctionne (ou pas lol)

L'exercice portant sur la dichotomie , ça me paraît pour le moins logique, non ?

Dans l'énoncé de l'exercice en question ce n'était pas demandé de faire par dichotomie, ou en tout cas pas dit de manière claire, quoique dans le Tp il y avait écrit "jeu dichotomique"... au début je n'y avais pas fait gaffe car ne savant ce qu'était la dichotomie, heureusement que j'étais curieux d'aller sur Google

La ou l'OO sera interessant, c'est si on va un peu plus loin est qu'on met en place un algorithme de recherche dichotomique sur un conteneur d'objets triés (et puis comparer les résultats avec le classique find)

Tu parlerais pas d'un tableau trié ? si c'est le cas, nous n'avons pas encore vu ça en cours, les profs ont une tendance qui fait qu'ils font les Travaux Pratiques avant les cours, pas commode si on a pas d'inspiration

[Médinoc]

Pour une recherche dichotomique, il s'agit en effet généralement d'un tableau trié.
Sinon, il y a l'Arbre Binaire de Recherche, qui est plus complexe qu'un tableau et plus gourmand en mémoire, mais plus rapide à modifier (pour N suffisamment grand)...

[Invité]

Bonjour,

Pour la recherche dichotomique, c'est plus simple avec la récursivité.

On ramène un problème de taille T à deux problèmes de taille T/2 chacun par dichotomie et ainsi de suite.
En poursuivant, on tombe finalement sur la valeur recherchée ssi elle est présente dans le tableau de recherche.

C'est une recherche dans un tableau trié.

Voici du pseudo-code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
     // constantes
     const N = 9;
 
     // var globales
     int bmin = 0;
     int bmax = N;
     int v = -1; // valeur recherchée
     int milieu;
     int [0..N] tab = [1, 6, 17, 44, 78 , 99, 104, 567, 901, 998];
 
     fonction cherche (int i, int j, int v, int [] t)
     // recherche d'une valeur v dans un tableau tab entre les indices i et j
     // output : renvoie l'indice de la valeur recherchée ou -1 si absent du tableau
 
     debut
          milieu = (i+j) div 2;
          si (milieu==v) 
               alors
                    return milieu;
               sinon
                    si (v>milieu) 
                         alors
                              // c'est la borne inférieure du tableau qui progresse
                              i = milieu + 1;
                              cherche (i, j, v, t);
                         sinon
                              // c'est la borne supérieure du tableau qui diminue
                              j = milieu;
                              cherche (i, j, v, t);
                    finsi
          finsi
 
          return -1;
 
     fin
 
     APPEL : 
     PROGRAM
          ecrire("Valeur recherchée ?");
          lire(v);
          cherche (bmin, bmax, v, tab);
     FINPROG

@Hyperyon:
Il ne te reste plus qu'à traduire en C++ (moyennant quelques erreurs mineures).

[droggo]

Koa,
Suite à une de mes remarques,

Dans l'énoncé de l'exercice en question ce n'était pas demandé de faire par dichotomie, ou en tout cas pas dit de manière claire, quoique dans le Tp il y avait écrit "jeu dichotomique"... au début je n'y avais pas fait gaffe car ne savant ce qu'était la dichotomie, heureusement que j'étais curieux d'aller sur Google

Et pourtant, le post d'origine:

Bonjour,

Voilà je dois réaliser un petit programme dans lequel l'utilisateur dois saisir un nombre compris entre 0 et 999 et où l'ordinateur doit trouver ce nombre en utilisant la méthode dichotomique...

J'y ai déjà pas mal cherché, mais je ne trouve rien de probant

???

[Obsidian]

car ne savant

Sachant.

ce qu'était la dichotomie, heureusement que j'étais curieux d'aller sur Google

« Dichotomie », ça veut dire « coupure en deux ». Rien d'autre. Il faut être clair dans ses termes.

Quand on fait de la conversion d'un décimal vers du binaire, on procède également par « dichotomies successives » : on divise le nombre en deux en regardant à chaque fois si le résultat est entier ou non, et on met le bit à 1 ou à 0 en conséquence. C'est aussi une question de coupure en deux et, pourtant, cela n'a rien à voir avec l'exercice en question.

La recherche par dichotomie dans un tableau trié est effectivement la plus naturelle. Ça n'en a pas peut-être pas l'air quand tu écris un programme, mais si je te dis de vive voix « je pense à un nombre entre 0 et 100. Devine-le. » et que je te dis simplement s'il est inférieur ou supérieur à ce que tu me proposes, tu vas immédiatement taper sur le 50, puis sur le 25 ou le 75, etc. En fait, on s'aperçoit que c'est parce que les seules options que l'on peut avoir en comparant deux nombres différents, c'est supérieur ou inférieur, soit deux cas. Quand on a plus d'infos, on peut faire des tables de hachage.

Ceci t'emmènera aussi à terme vers la complexité des algorithmes. En l'occurence, il n'est pas difficile de déterminer que tu auras forcément trouvé avant le huitième coup. En effet, à ce stade, tu auras divisé ta table en 128èmes, et comme il n'y a que cent éléments dedans, chaque morceau contient forcément moins de deux éléments.

D'ailleurs, si tu tapes « complexité » dans Google, il te suggérera « Complexité de recherche dichotomique » ! :-)

[Hyperyon]

Koa,

Suite à une de mes remarques,

Envoyé par Hyperyon Voir le message
Dans l'énoncé de l'exercice en question ce n'était pas demandé de faire par dichotomie, ou en tout cas pas dit de manière claire, quoique dans le Tp il y avait écrit "jeu dichotomique"... au début je n'y avais pas fait gaffe car ne savant ce qu'était la dichotomie, heureusement que j'étais curieux d'aller sur Google

Et pourtant, le post d'origine:

Envoyé par Hyperyon Voir le message
Bonjour,

Voilà je dois réaliser un petit programme dans lequel l'utilisateur dois saisir un nombre compris entre 0 et 999 et où l'ordinateur doit trouver ce nombre en utilisant la méthode dichotomique...

J'y ai déjà pas mal cherché, mais je ne trouve rien de probant
???

???

Sinon les tableaux triés sont peut-être mieux, sauf que je ne les maîtrise pas encore
On commence tout juste à les aborder en classe, et là on essaye de trouver une méthode pour trier de manière efficace les tableaux, surchauffe de cerveau garantie