Discussion :

[oc_alex86]

Bonjour,

J'ai un séquence de 5 nombres n0 .. n5 tous dans un intervalle [0,r] qui vérifient la propriété
n0 <= n1 <= n2 <= ... <= n5.
Mon but est de trouver une façon de les lister tel que, si on me donne un élément de la liste, je peux connaitre facilement sa position dans la liste.

Malheureusement, je ne vois pas du tout comment faire ça.

[edfed]

s'il n'y à que 5 éléments dans la liste, le problème ne se pose même pas, suffit de parcourir la liste, et comparer chaque élément avec le nombre en entrée, et dès qu'on en trouve un égal, on a la position.

ça peut même fonctionner pour des listes de taille énorme, avec la vitesse des processeurs, ça ne pose aucun problème de parcourir des listes de plusieurs millions d'entrées. au delà, ça peut être plus lent.

[estelle.bod]

La recherche par dichotomie peut être plus rapide et elle est possible puisque votre tableau est trié

[souviron34]

+1 pour la dichotomie (pour des nombres quand même largement supérieurs à 5)..

Sinon, pour des nombres pour lesquels une dichotomie ne se justifie pas forcément, un test simple :

milieu = N/2

Si valeur <= valeur(milieu)

cherche pour i = milieu jusqu'à i >= 0

Sinon

cherche pour i = milieu jusqu'à i < N

[oc_alex86]

Il n'y a donc aucun moyen simple d'accéder à l'élément souhaiter?
Je dois tout de même accéder environ 2^30 fois à un élément dans une table de 10 Mo, ce qui n'est pas rien.

[Nebulix]

2^30 fois ?
Il y a un pb d'algo en amont !

[souviron34]

@P.O. :

Tu ne nous a pas donné correctement le rpoblème :

J'ai un séquence de 5 nombres n0 .. n5 tous

ce n'est pas :

un élément dans une table de 10 Mo,

D'autre part :

2^30 fois ?
Il y a un pb d'algo en amont !

Absolument....





Peut-on savoir ce que tu cherches réellement à faire ????

Expose ton vrai problème, clairement, et tu auras (peut-être) des réponses correctes...


(en remarque : la dichotomie est quasi-imbattable sur d'énormes nombres)

[oc_alex86]

Effectivement. Je me suis mal expliqué au début, désolé .
Je souhaite enregistrer dans une table toutes les possibilités de cinq nombres n0, n1, n2, ..., n4 tel que n0 <= n1 <= ... <= n4 en sachant que les nombres sont limités de 0 à r. On peut donc par exemple les générer avec le code suivant

Code :

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

1
2
3
4
5
6
 
for(n0 = 0; n0 <r; ++ n0)
    for(n1 = n0; n1 <r; ++ n1)
 ...
        for(n4 = n3; n4 <r; ++ n4)
            //stocker  f(n0, n1, n2, ..., n4) pour une fonction f

Une fois cette table créée, je souhaite pouvoir accéder rapidement, étant donné un n0, n1, .., n4 à f(n0, ..., n4) dans la table.

[pseudocode]

Ca ressemble fortement a un "combinadic", sauf que ton ordre n'est pas strict.

[Davidlouiz]

Intéressant...

Je viens de coder un programme en C++ qui calcule "instantanément" la position de ton élément à partir des 5 nombres qui le constitue.

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
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long r;
    cout << "r : ";
    cin >> r;
 
    // Affichage de la table
    unsigned long i = 0;
    cout << "Affichage de la table :" << endl;
    for(unsigned long n0 = 0; n0 < r; ++ n0)
        for(unsigned long n1 = n0; n1 < r; ++ n1)
            for(unsigned long n2 = n1; n2 < r; ++ n2)
                for(unsigned long n3 = n2; n3 < r; ++ n3)
                    for(unsigned long n4 = n3; n4 < r; ++ n4)
                        cout << "table[" << i++ << "] : "
                        << n0 << " " << n1 << " "
                        << n2 << " " << n3 << " "
                        << n4 << endl;
 
    // Creation du tableau de comptage
    unsigned long* tableauDeComptage[5];
    for(i = 0; i < 5; i++)
        tableauDeComptage[i] = (unsigned long*)malloc(r * sizeof(unsigned long));
 
    // Initialisation du tableau de comptage
    for(i = 0; i < r; i++)
        tableauDeComptage[0][i] = 1;
    for(i = 0; i < 5; i++)
        tableauDeComptage[i][0] = 1;
    unsigned long j;
    for(j = 1; j < 5; j++)
        for(i = 1; i < r; i++)
            tableauDeComptage[j][i] = tableauDeComptage[j][i-1] + tableauDeComptage[j-1][i];
 
    // Affichage du tableau de comptage
    cout << "Affichage du tableau de comptage :" << endl;
    for(unsigned long j = 0; j < 5; j++)
    {
        for(i = 0; i < r; i++)
            cout << tableauDeComptage[j][i] << " ";
        cout << endl;
    }
 
    // IHM
    cout << "Entrez les 5 nombres de l'element : ";
    unsigned long n[5];
    for(i = 0; i < 5; i++)
        cin >> n[i];
 
    // Calcul de la position de l'element
    unsigned long comptage = 0;
    unsigned long position = r-1;
    for(j = 4; j+1 > 0; j--)
    {
        for(i = position; i >= r-n[4-j]; i--)
            comptage += tableauDeComptage[j][i];
        position = i;
    }
    cout << "Position de l'element : " << comptage << endl;
 
    return 0;
}

Le programme fonctionne bien. Si les explications t'intéressent, je tenterai d'expliquer ma démarche.

David.