Discussion :

[Pimousse22]

Bonjour � tous,

J'ai comme projet de faire un programme en c qui effectue le c�l�bre jeux du PLUS OU MOINS. Jusque l� tout va bien mais c'est dans la deuxi�me partis du TD. C'est l'ordinateur qui doit trouver le nombre que vous avez dans votre t�te. Il faut juste l'aider en lui disant + ou -
Il y a une condition il faut utiliser la fonction recursive.

Je me suis pas mal renseigner la dessus. Je trouve d'ailleurs cette fonction g�nial mais assez dur pour un novice comme moi � mettre en place. Comme mon p�re me disait, C'est en programment que l'on devient programmeur !

Donc voici en gros les r�gles de l'exercice:
Choisissez un nombre entre 0 et 100.
L'ordinateur doit pouvoir trouver votre nombre, pour cela utiliser la touche "1" pour plus petit et "2" pour plus grand et "3" pour c'est gagn� !
Utiliser la recurrence.

J'ai commenc� donc � �crire un programme depuis 2 jours et je vous avouerais que je bloque au niveau des intervalles.
Prenons par exemple le nombre 22.
Le programme me demande au d�but si il est plus petit ou plus grand que 50.
Je r�pond plus petit.
Il me demande ensuite si il est plus petit ou plus grand que 25.
Je r�pond plus petit.
Il me demande ensuite si il est plus petit ou plus grand que 12.
Je lui r�pond plus grand.
LA il me demande si il est plus petit ou plus grand que 6. Je vous avouerais que je bloque. Mon code est surement faux mais je n'arrive pas � trouv� une solution. Si quelqu'un pouvait m'�clairer.

Pour info: Je d�veloppe sur Xcode 6.0.1

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
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
const int MIN = 0;
const int MAX = 100;
 
 
void intervalle(int MIN, int MAX)
{
    int INT_T; // intervalle à l'instant t
    int x;
 
    INT_T = ((MAX-MIN)/2);
 
    printf("Est il plus grand (1) ou plus petit (2) que : %d ? ou est ce %d ? (3) \n", INT_T, INT_T);
    scanf("%d", &x);
 
    if ( x == 1 ) /* nombre mystère > INT_T */
    {
 
        INT_T = (((MAX-MIN)/2) + MIN);
        MIN = INT_T;
        intervalle(MIN, MAX);
    }
    if ( x == 2) /* nombre mystère < INT_T */
    {
        MAX = INT_T;
        intervalle(MIN, MAX);
    }
    if ( x == 3) /* c'est le nombre mystère */
    {
        printf("C'est gagné, le chiffre mystère est %d \n", INT_T);
        exit (0);
    }
}
 
int main ()
{
    intervalle(0,100);
    return 0;
}

MERCI A TOUS

[skeud]

Je pense que tu n'utilise pas la bonne m�thode concernant ton algorithme, l'as-tu test� sur une feuille de papier avant de le coder?
En pseudo code?

J'aurais bien envie de te donner la solution de suite, mais �a serait trop simple .

[M�dinoc]

Franchement, pour cet exemple la r�cursivit� me para�t aussi "forc�e" que pour le cas d'�cole de la factorielle. Mais admettons.

Ton probl�me, c'est que tu as deux formules diff�rentes pour le calcul de INT_T, et seule l'une d'entre elles est bonne.
De plus, ta convention de nommage est un peu bizarre et tu devrais s�parer l'interrogation dans une autre fonction:

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
/*Comme strcmp: Retourne <0 si valeurATester est inférieur au nombre mystère,
>0 si valeurATester est supérieur au nombre mystère,
0 si égal.*/
int ComparerNombre(int valeurATester)
{
	int x;
	int saisieOK = 0;
	int resultat = 0;
	/*On saisit en boucle jusqu'à ce qu'on ait une valeur valide.*/
	do
	{
		printf("Est-il plus grand (1), plus petit (2) ou égal (3) à %d?\n", valeurATester);
		scanf("%d", &x);
		saisieOK = 1;
		switch(x)
		{
		case 1: 
			resultat = -1; /*Nombre mystère est plus grand -> valeurATester est plus petit*/
			break; 
		case 2:
			resultat = 1; /*Nombre mystère est plus petit -> valeurATester est plus grand*/
			break;
		case 3:
			resultat = 0; /*Nombre mysère est égal*/
			break;
		default:
			saisieOK = 0; /*Valeur inconnue*/
			getchar(); /*Pour éviter de reboucler si l'utilisateur a tapé une lettre*/
			break;
		}
	}
	while(!saisieOK);
	return resultat;
}
 
int TrouverDansIntervalle(int valeurMin, int valeurMax)
{
	int milieu = (valeurMax-valeurMin)/2 + valeurMin;
	int resCmp;
	if(milieu == valeurMin) /*peut arriver si valeurMax == valeurMin+1*/
		milieu = valeurMin+1; /*Pour éviter une recherche infinie*/
 
	printf("[Debug: Recherche dans [%d, %d], milieu est %d.]\n", valeurMin, valeurMax, milieu);
 
	resCmp = ComparerNombre(milieu);
	if(resCmp == 0)
		return milieu;
	else if(resCmp < 0) /*milieu est inférieur au nombre mystère, il faut donc rechercher dans la moitié supérieure*/
		return TrouverDansIntervalle(milieu, valeurMax);
	else /*milieu est supérieur au nombre mystère, il faut donc rechercher dans la moitié inférieure*/
		return TrouverDansIntervalle(valeurMin, milieu);
}
 
int main()
{
	int valeurTrouvee = TrouverDansIntervalle(0, 100);
	printf("C'est gagné, le chiffre mystère est %d \n", valeurTrouvee);
}

Avec �a, on obtient des fonctions plus petites, les entr�es/sorties sont s�par�es des calculs, et normalement le code reste facile � comprendre.

[Pimousse22]

Wahh !!

C'est clair comme de l'eau de roche avec votre code.
Il fallait que je fasse deux fonctions distinctes.
Je vous remercie �norm�ment, cela va vraiment m'aider � comprendre.

[skeud]

Puisqu'on est au stade de donner les r�ponse ...... Voici une meilleur m�thode:

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
int chercherValeur(int min, int max)
{
	// Nombre courant
	int courant = ((max - min) / 2) + min;
	char reponse = '\0';
	int continuer = 1;
 
	// Tant qu'on a pas une réponse compréhensible
	while (continuer)
	{
		printf("Est il plus grand (1) ou plus petit (2) que : %d ? ou est ce %d ? (3) \n", courant, courant);
		// Si erreur de lecture
		if ((reponse = getchar()) > 0)
		{
			printf("Erreur de lecture");
			continuer = 0;
		}
		else
		{
			switch (reponse)
			{
			case '1':
				// Le nombre est plus grand donc on referme notre recherche sur [courant-max]
				return (chercherValeur(courant, max));
			case '2':
				// Le nombre est plus petit donc on referme notre recherche sur [min-courant]
				return (chercherValeur(min, courant));
			case '3':
				// Le nombre est trouvé donc on remonte toute la pile d'appel
				return (courant);
			}
		}
	}
 
	return (-1);
}
 
int main(int argc, char* argv[])
{
	int valeur = chercherValeur(0,100);
	if (valeur >= 0)
		printf("La valeur est = %d\n", valeur);
	system("PAUSE");
	return 0;
}

Plus simple, plus rapide, moins de blabla.

[Pimousse22]

Du coup j'ai r�ussi � faire avec la r�cursivit� mais en repartant d'une feuille blanche et en m'aidant de vos codes:

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
 
int x;
int valeur;
int compteur;
 
int main ()
{
    int min = 0;
    int max = 100;
 
    printf("rentre un nombre\n");
    scanf("%d", &x);
 
    compteur = 1;
    while (cherche(min, max, 1));
    printf("valeur : %d en %d fois \n",valeur, compteur);
 
}
 
 
 
 
 
 
int cherche ( int min, int max)
{
    int newmin;
    int newmax;
 
    if ((((max-min)/2)+min) !=x)
    {
        if ((((max-min)/2)+min) > x){
            newmax = ((max-min)/2)+min;
            compteur++;
            cherche(min, newmax);
        } else {
            newmin = ((max-min)/2)+min;
            compteur++;
            cherche(newmin,max);
        }
    } else {
        valeur = (((max-min)/2)+min);
    }
    return 0;
}

Le code marche bien, en plus de �a j'ai rajout� un petit compteur. Le seul HIC c'est qu'il perd la t�te quand notre chiffre est 100 (la limite de l'intervalle).

[M�dinoc]

Tu devrais essayer d'obtenir une version sans variable globale.