Discussion :

[kuroro20]

Salut a Tous,

Voila, Je dois creer une fonction recursive qui permet de rechercher la valeur minimum et maximum dans un tableau, en utilisant une ""methode dichotomique"". J'ai reussi a en creer une sans trop de probleme, mais j'ai l'impression qu'il y a quelquchose qui cloche(j'ai surtout l'impression qu'il fait beacoup trop d'operations) dans mon code :s .

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
 
#include <stdio.h>
#define N 80000
void minmaxrecursif(int tab[],int indiceMin, int indiceMax, int *valeurMin, int *valeurMax)
{
    int milieu=(indiceMax+indiceMin)/2;
 
    if ( indiceMax-indiceMin==1 )
    {
 
        if (*valeurMin > tab[indiceMax])
            *valeurMin=tab[indiceMax];
        else if ( *valeurMax < tab[indiceMax])
            *valeurMax=tab[indiceMax];
        /*printf("tab[min]=%d\ntab[max]=%d",tab[indiceMin],tab[indiceMax]);*/
    }
 
 
    else
    {
        minmaxrecursif( tab,indiceMin,milieu,valeurMin,valeurMax);
        minmaxrecursif( tab,milieu,indiceMax,valeurMin,valeurMax);
    }
}
 
 
int main(void)
{
    int tab[N]={0};
    int min=tab[0], max=tab[0];
    int i;
    for (i=0;i<N;i++)
    {
        tab[i]=i;
    }
 
    minmaxrecursif(tab,0,N-1,&min,&max);
    /*minmax(tab,N,&min,&max);*/
    printf("min=%d max=%d \n",min,max);
    return 0;
 
}

Si vous avez des idees pour optimiser ca je suis preneur (pas forcement des bouts de code ou des correction j'aimerai bien y arriver de moi meme mais pour l'instant j'ai pas de pistes :s )

Merci d'avances pour vos reponses.

[Mizar75]

Si ton tableau est trié c'est le premier élément et le dernier.

S'il n'est pas trié, la dichotomie est inutile car if faut vérifier toutes les cases du tableau. sorry!

[john stedd]

comme indiqué dans la réponse précédente, tu as le choix entre :
- parcourir tout ton tableau à la recherche du min et du max
- utiliser la fonction qsort() qui permet de trier ton tableau à l'aide de la methode "quick sort", adaptée pour les gros tableaux. elle est un peu compliquée à mettre en oeuvre mais efficace.

[kuroro20]

Je sais bien que la dichotomie marche que quand le tableau est trie et c'est pour ca que j'ai mis des guillemets, .
Ce qui m'a ete demande c'est de "couper le tableau en 2" puis de resoudre le probleme dans chacune des parties.
(je sais bien que ici cette methode, et la recursivite ne sont pas beacoup plus utile qu'un algo naif mais c'est ce qui a ete demande )

[diogene]

mais j'ai l'impression qu'il y a quelquchose qui cloche(j'ai surtout l'impression qu'il fait beacoup trop d'operations) dans mon code :s .

Qu'est-ce qui semble clocher ?
Je pense que ton code répond à la question posée sauf pour

Code :

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

    if ( indiceMax-indiceMin==1 )

que je verrai plutôt comme

Code :

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

    if ( indiceMax==indiceMin)

sinon, c'est incorrect pour un tableau de 1 élément.
autre remarque

Code :

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

1
2
        minmaxrecursif( tab,indiceMin,milieu,valeurMin,valeurMax);
        minmaxrecursif( tab,milieu,indiceMax,valeurMin,valeurMax);

analyse deux fois l'élément d'indice milieu. On devrait avoir

Code :

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

1
2
        minmaxrecursif( tab,indiceMin,milieu,valeurMin,valeurMax);
        minmaxrecursif( tab,milieu+1,indiceMax,valeurMin,valeurMax);

mais on le paye alors en devant tester dans la fonction que indicemin <= indicemax
Sinon, je ne vois pas comment améliorer les performances qui sont directement liées à la nature récursive du code.