Génération de nombres aléatoires différents
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:
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 :)
