Discussion :

[Flob90]

Personnelement juste avec le pseudo-code je ne peux pas comprendre l'algo, des notations étranges (q,n,c jamais définis), des lettres inutilisées (k), deux notation pour la même chose (indices en indice et entre crochet, et le second indice est réel, on tronc ou on arrondi ?)

Si tu as compris la problèmatique tu devrais pouvoir éclairer ces différents points (sinon faut lire les 17 pages précédentes, ca peut aider à se mettre dans la tête de la personne qui a écrit l'algo), et ensuite ca devrait aller à coder (manipulation de conteneurs et boucle, ca va assez bien avec les algo de la S(T)L).

Edit: @skeud: Je m'addressais plutôt à ghada97

[skeud]

Aucune idee c'est pas mon algo ^^

[ghada97]

Ben si "skeud" : normalement c'est ça d'après ce que j'ai compris des sections précédentes: q c'est le nombre aléatoire de requête retirée aléatoirement: c'est un entier dans l'intervalle: [i, n+i]

[skeud]

Ok donc:
s <- s\ { i, n ; n+i }

veut dire quoi?

sachant que tan que |L| < q
veut dire:

Code :

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

while (L.size() < q)

[ghada97]

s <- s\ { i, n ; n+i } veut dire que la solution s doit appartenir à l'intervalle
[i, n+i] c'est à dire à chaque itération, la requête dont l’indice de
l’un des sommets i et (n+i) correspond au nombre aléatoire généré est retirée.

[skeud]

Le nombre aléatoire est générer ou?

[ghada97]

Plutôt le nombre aléatoire retiré par la fonction "ChoisirRequeteAleatoire"

[Flob90]

C'est s <- s \ {i,i+n} dans le document, et en lisant la suite ca doit vouloir dire : "retirer la requéte i de la solution". Qui doit donc se traduire par retirer i et n+i de la séquence s. Par contre d'où vient n ?

[Flob90]

Il faut regarder la page 17 en fait, n et q son définie avant, cette algo est un sous-algo d'un autre, q est un nombre aléatoire inférieur à n, n étant le nombre de requête.

Et initialement s doit être une séquence d'entier de 1 à 2n.

Il n'y a plus que c que je ne vois pas ce que c'est et k qui n'est pas présent dans l'algo. Pour l'accés à B [ |L| * r^D ], tronquer où arrondir ne doit rien changer en fait, ca sert à effectué un selection probabliste, le choix entre troncature et arrondie ne doit pas changer la tendance recherchée.