Discussion :

[Dam63]

Voila, comme le titre l'indique j'ai un p'tit souci dans mon programme.

C'est un programme qui doit, par dichotomie et récursivité, retrouver la position d'un nombre dans un tableau et l'afficher, pour cela, pas de pointeur, uniquement une fonction, mais je bloque, il y a surement des paramètres que j'écris mal car ça me donne une erreur de pile lors de l'affichage de l'emplacement du nombre dans le tableau, voici le programme:

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
65
66
67
68
69
70
71
#include <stdio.h>
#include <math.h>
 
int dicho(int a, int b, int n, float tab[])
{
if(tab[a]==n)
return a;
if(tab[b]==n)
return b;
if(tab[b]>n)
{
tab[a]=tab[(a+b)/2];
tab[b]=tab[4];
dicho(a,b,n,tab);
}
if(tab[b]<n)
{
tab[b]=tab[(a+b)/2];
tab[a]=tab[0];
dicho(a,b,n,tab);
}
else
return 0;
}
 
main()
{
int x,i,j,k,l,m,n;
float leau[4];
 
printf("Entrer votre tableau de 4 nombres: ");
for(i=0;i<=3;i++)
{
scanf("%f",&leau[i]);
}
 
for(j=0;j<=3;j++)
    {
    for(k=0;k<=j;k++)
        {
        if(leau[j]<leau[k])
            {
            l=leau[j];
            m=leau[k];
 
            leau[j]=m;
            leau[k]=l;
            }
        }
    }
 
i=0;
 
for(i=0;i<=3;i++)
    {
    printf("Votre tableau croissant est: %f \n",leau[i]);
    }
 
printf("Entrer la valeur dont vous voulez la position: ");
scanf("%d",&n);
 
x=dicho(0,4,n,leau);
 
if(x>1)
{
x=x-1;
}else
x=1;
 
printf("Votre chiffre est a la position %d du tableau",x);
}

Pour la partie rentrage et triage du tableau ça marche, donc ça sert à rien de chercher une faute là-dedans, la faute est dans la fonction dicho.

Et voici l'erreur qui s'affiche:


Merci d'avance aux personnes qui sauront m'aider.

[Sve@r]

Voila, comme le titre l'indique j'ai un p'tit souci dans mon programme.

C'est un programme qui doit, par dichotomie et récursivité, retrouver la position d'un nombre dans un tableau et l'afficher, pour cela, pas de pointeur, uniquement une fonction, mais je bloque, il y a surement des paramètres que j'écris mal car ça me donne une erreur de pile lors de l'affichage de l'emplacement du nombre dans le tableau, voici le programme:

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
65
66
67
68
69
70
71
#include <stdio.h>
#include <math.h>
 
int dicho(int a, int b, int n, float tab[])
{
if(tab[a]==n)
return a;
if(tab[b]==n)
return b;
if(tab[b]>n)
{
tab[a]=tab[(a+b)/2];
tab[b]=tab[4];
dicho(a,b,n,tab);
}
if(tab[b]<n)
{
tab[b]=tab[(a+b)/2];
tab[a]=tab[0];
dicho(a,b,n,tab);
}
else
return 0;
}
 
main()
{
int x,i,j,k,l,m,n;
float leau[4];
 
printf("Entrer votre tableau de 4 nombres: ");
for(i=0;i<=3;i++)
{
scanf("%f",&leau[i]);
}
 
for(j=0;j<=3;j++)
    {
    for(k=0;k<=j;k++)
        {
        if(leau[j]<leau[k])
            {
            l=leau[j];
            m=leau[k];
 
            leau[j]=m;
            leau[k]=l;
            }
        }
    }
 
i=0;
 
for(i=0;i<=3;i++)
    {
    printf("Votre tableau croissant est: %f \n",leau[i]);
    }
 
printf("Entrer la valeur dont vous voulez la position: ");
scanf("%d",&n);
 
x=dicho(0,4,n,leau);
 
if(x>1)
{
x=x-1;
}else
x=1;
 
printf("Votre chiffre est a la position %d du tableau",x);
}

Pour la partie rentrage et triage du tableau ça marche, donc ça sert à rien de chercher une faute là-dedans, la faute est dans la fonction dicho.

Et voici l'erreur qui s'affiche:


Merci d'avance aux personnes qui sauront m'aider.

Ton tableau de 4 éléments va de tab[0] à tab[3]. Dans la fonction "dicho" tu vas à un moment t'adresser à tab[4] donc t'es hors tableau. J'ai pas regardé plus loin voir s'il y avait autre chose. Par ailleurs introduire la limite de ton tableau "en dur" dans la fonction "dicho" est une très mauvaise idée (aucune portabilité)

Code :

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

1
2
3
4
5
6
7
8
if(leau[j]<leau[k])
            {
            l=leau[j];
            m=leau[k];
 
            leau[j]=m;
            leau[k]=l;
            }

Code :

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

1
2
3
4
5
6
if(leau[j]<leau[k])
            {
            l=leau[j];
            leau[j]=leau[k];
            leau[k]=l;
            }

PS: Quand on travaille sur un tableau de "n" éléments (dans ton cas il s'agit de 4), il est plus lisible de boucler de 0 à <n que de 0 à <=(n-1)
=> remplacer "for (i=0; i <=3; i++)" par "for (i=0; i < 4; i++)"

[Fred83]

Après un rapide coup d'oeil, il me semble, qu'en plus de dépassement des bornes tu as les problèmes suivants :

1) Tu recherches une valeur entière N dans un tableau de réels.

2) Pour une recherche dichotomique, il faut que ton tableau soit trié. Si c'est le cas ta fonction le mélange. Dans ta fonction, il ne faut pas toucher aux valeurs du tableau mais aux indices passés en paramètres. regarde ton code, si t[a] ou t[b] ne contiennent pas la valeur cherchée, tu permutes des cases du tableau et rappelle la fonction avec les mêmes valeurs de paramètres pour a et b.

Bon courage

[Dam63]

J'ai fais ce que tu m'as dis Sve@r, et ça va mieux, plus de problème de pile, maintenant je dois avoir un problème de fonction, car quand je lui rentre le nombre dont je veux connaitre la position, il me met toujours 2 comme position, pourtant ça ne devrait pas être le cas.

Sinon oui, mon tableau est bien trié, et le but est de couper le tableau en deux jusqu'à trouver la bonne valeur, c'est ça la dichotomie.

[Sve@r]

J'ai fais ce que tu m'as dis Sve@r, et ça va mieux, plus de problème de pile, maintenant je dois avoir un problème de fonction, car quand je lui rentre le nombre dont je veux connaitre la position, il me met toujours 2 comme position, pourtant ça ne devrait pas être le cas.

Fred83 a raison. Tu devrais pas faire "tab[...]=tab[...]" dans ta fonction dicho car tu vas t'autopolluer les éléments de ton tableau.
Faut juste que tu rappelles récursivement dicho en lui passant les bornes min et max de recherche sans jamais toucher à tab...

[Dam63]

Faut juste que tu rappelles récursivement dicho en lui passant les bornes min et max de recherche sans jamais toucher à tab...

Ouais je vois, mais comme faire ça? Ça fait 2 semaines que je bosses dessus et je bloque toujours, je me demande si j'y arriverais un jour...

[Fred83]

En deux semaines, tu aurais pu prendre deux minutes pour taper "recherche dichotomique" dans le premier moteur de recherche venu.

http://cermics.enpc.fr/polys/info1/main/node59.html

[Sve@r]

Ouais je vois, mais comme faire ça? Ça fait 2 semaines que je bosses dessus et je bloque toujours, je me demande si j'y arriverais un jour...

Déjà, faut que tu commences par te forcer à mettre des noms de variable significatifs (plutôt que "a", "b", etc) => ça te permet de mieux garder ton algo à l'esprit.

Ta fonction dicho reçoit en paramètre les bornes min et max du tableau (déjà "min" et "max" c'est mieux que "a" et "b"). Si l'un des éléments de ces bornes est le bon, alors tu renvoies l'indice en question.
Sinon tu appelles dicho en lui passant juste les nouvelles bornes correspondantes à la partie du tableau contenant l'élément (mais sans toucher au tableau) => style tu appelles "dicho(min, (min+max) / 2)" ou bien "dicho((min+max) /2, max)"

[Emmanuel Delahaye]

Ouais je vois, mais comme faire ça? Ça fait 2 semaines que je bosses dessus et je bloque toujours, je me demande si j'y arriverais un jour...

Il y a 2 fonctions C à connaitre :

- qsort() pour trier un tableau
- bsearch() pour faire une recherche dans un tableau trié (probablement dichotomique, parce que c'est le plus rapide).

[Sve@r]

Il y a 2 fonctions C à connaitre :

- qsort() pour trier un tableau
- bsearch() pour faire une recherche dans un tableau trié (probablement dichotomique, parce que c'est le plus rapide).

Oui mais ça doit être un exo d'étudiant donc faut qu'il fasse tout lui-même.

J'ai oublié un truc important => faut pas seulement appeler récursivement dicho(), faut aussi renvoyer vers l'amont ce qu'on reçoit de l'appel récursif aval sinon ça marche pas
Donc remplacer "dicho(..., ..., n, tab)" par "return dicho(..., ..., n, tab)" => le résultat trouvé par le tout dernier appel récursif remontera ainsi tous les appels récursifs imbriqués...

[Dam63]

Euh ouais, je comprends le raisonnement mais je suis incapable de le retranscrire en langage c donc je vais arrêter avant de péter un câble.

Merci quand même pour ton aide Sve@r.

[Sve@r]

donc je vais arrêter avant de péter un câble.

Merci quand même pour ton aide Sve@r.

Bah, faut juste réfléchir un peu (et parfois les commentaires aident à réfléchir). Parfois même un dessin peut aider...

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
int dicho(int deb, int fin, int n, int tab[])
{
    int milieu;
 
    // Si le nombre correspond aux bornes
    if(tab[deb]==n)
          return deb;
    if(tab[fin]==n)
         return fin;
 
    // Evaluation de l'élément milieu
    milieu=(deb + fin) / 2;
 
    // Evaluation de la position de "n" par rapport au milieu
    if (n < tab[milieu])
          // L'élément se trouve dans la partie gauche
          return dicho(deb, milieu, n, tab);
 
    if (n > tab[milieu])
          // L'élément se trouve dans la partie droite
          return dicho(milieu, fin, n, tab);
 
    // L'élément se trouve pile poil au milieu
    return milieu;
}

Pas testé mais ça devrait marcher...

Euh ouais, je comprends le raisonnement mais je suis incapable de le retranscrire en langage c

J'espère que le déclic se produira car cela ne peut venir que de toi. Là t'as la solution "toute faite" parce que j'estime que exceptionnellement ça peut t'aider à progresser mais quand tu seras face à ton exam, tu seras seul. Et plus tard, si tu fais de l'informatique ton métier premier tu pourras pas tricher...