Connaitre la position d'un élément d'une séquence vérifiant un ordre

Version imprimable

17/03/2011, 08h03
oc_alex86

Connaitre la position d'un élément d'une séquence vérifiant un ordre

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.
17/03/2011, 16h28
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.
18/03/2011, 08h12
estelle.bod

La recherche par dichotomie peut être plus rapide et elle est possible puisque votre tableau est trié
18/03/2011, 13h00
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 :

Citation:

milieu = N/2

Si valeur <= valeur(milieu)

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

Sinon

cherche pour i = milieu jusqu'à i < N
18/03/2011, 14h07
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.
18/03/2011, 14h34
Nebulix

2^30 fois ?
Il y a un pb d'algo en amont !
18/03/2011, 15h39
souviron34

@P.O. :

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

Citation:

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

ce n'est pas :

Citation:

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

D'autre part :

Citation:

Envoyé par Nebulix

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)
19/03/2011, 03h28
oc_alex86
Effectivement. Je me suis mal expliqué au début, désolé :oops:.
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:

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.
19/03/2011, 14h43
pseudocode

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

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:

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.