Discussion :

[The Wretched]

Bonjour,

J'aurais besoin d'un tableau de 200k cases contenant chacun un chiffre entre 1 et 200k, dans un ordre aléatoire.

Actuellement, j'ai un algo qui remplit le tableau au fur et à mesure, comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
trouvé=1		//indique si le nombre était déjà présent dans le tableau
 
POUR i=1 à 200000, faire : 
{
<div style="margin-left:40px">nombre_aleatoire est un entier
tant que (trouvé == 1) //tant qu'on n'a pas trouvé un nombre différent
{
<div style="margin-left:40px">nombre_aleatoire =hasard (1, 200000) //la fonction hasard génère un nombre aléatoire entre 1 et 200000 (les paramètres)
trouvé = recherche_identique() //On recherche dans tout le tableau déjà rempli un nombre identique, renvoie 1 si trouvé, 0 si pas trouvé</div>}
fin
//A ce moment là on a le nombre aléatoire différent, qu'on met dans le tableau.
tableau[i] = nombre_aleatoire</div>}
fin

En bref, on génère un nombre aléatoire, puis on regarde dans le tableau si il y est déjà. Si il y est déjà, on recommence (mais la fonction "hasard" peut nous ressortir le même nombre).

Le problème est assez évident, si je me rappelle bien mes cours de maths, le temps de calcul augmente exponentiellement avec la taille du tableau à obtenir. Pire, le programme peut théoriquement prendre un temps "infini" (si la fonction "hasard" nous sort en continu le même chiffre présent dans le tableau).


J'ai besoin de changer l'algo pour qu'il accepte de générer un tableau plus grand.
J'avais pensé générer les nombre de 1 à X, puis les placer aléatoirement dans le tableau, en sautant les "cases" déjà remplies.


En bref, j'aimerais bien savoir si vous connaissiez des algos peu coûteux en temps pour faire ce genre de chose.

Merci d'avance

[pseudocode]

1. créer un tableau de 200k cases avec les nombres de 1 à 200k dans l'ordre
2. mélanger les cases du tableau (algo shuffle)
3. ne pas oublier de marquer la discussion comme "résolue".

[The Wretched]

Ça aurait été parfait avec un petit lien pour le 2), genre ça

Merci !