générer un entier [a, b] avec un RANDOM {0;1}
Bonjour,
Admettons que j'ai une fonction qui renvoie 0 ou 1, aléatoirement.
Ca fait partie d'un exo d'un livre, et j'aimerais savoir si la solution que j'ai trouvé est satisfaisante.
Comment avoir un entier compris entre deux bornes a et b? La solution que j'ai trouvé a une complexité moyenne de (b-a), ce qui ne me semble pas idéal...:?
Voilà le principe, avant le pseudo-code:
Tant que l'écart entre b et a inclus contient un nombre de nombres pair, je divise la poire en deux avec le RANDOM{0; 1}.
Ensuite, pour chaque entier possible (c'est à dire de a à b), je fait une série d'appels à la fonction RANDOM jusqu'à ce qu'elle m'envoie 0. Soit n ce nombre. Si n est inférieur au n maximum déjà trouvé, j'abandonne le nombre...
A la fin j'ai une liste beaucoup plus petite (en moyenne deux éléments..), et je peux répéter la procédure.
Voilà le pseudo-code:
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
| procedure RANDOM(a, b)
//REDUCTION DE L'INTERVALLE
tant que b-a impair //nombre pair de nombres entre a et b
si rand(0, 1) = 0
a + (b-a+1)/2 -> a //on augmente la borne inférieure
sinon
b - (b-a+1)/2 -> b //on diminue la borne supérieure
fin tant que
si a = b RETURN a
//ON PARCOURE TOUS LES NOMBRES
0 -> max
0 -> nb_stocké
tableau A[1..k] //k est ce qu'on veut, on peut agrandir le tableau de toute facon si il y a trop de nombres
pour i de a à b
0->essais
tant que rand(0, 1) = 1
essais++
si essais > max
1 -> nb_stocké
essais -> max
i -> A[nb_stocké]
sinon si essais = max
nb_stocké++
i -> A[nb_stocké]
fin pour
//A ce stade on n'a qu'un faible nombre de nombres dans A, il est facile d'extraire par la même méthode un nombre unique
... |
Voilà, je n'ai pas mis la fin car elle se répète avec la première partie.
C'est juste que pour générer un nombre entre 0 et 3 millions, je devrais me taper 3 millions de calculs...
Sinon il m'est venu une autre idée.
On ne peux pas utiliser la génération aléatoire de bits directement, car si le nombre n'est pas une puissance de 2 alors la méthode sera forcément faussée.
Mais alors le coût est de lg(n)...
Donc, si on prend notre intervalle b-a et qu'on utilise la méthode en lg(n) pour génerer un nombre entre 0 et la plus petite puissance de 2 plus grande que b-a?
On ajoute ce nombre à a, s'il est hors-portée, on réessaye. Là normalement le nombre moyen d'essais est de moins de 2. On a donc un algo en lg(n)!
_____________________________________________________
Cependant je me demande si il n'y a pas une erreur quelquepart, et je voudrais avoir votre avis (ainsi que si une solution ou méthode existe, quelle est-elle?)
Merci beaucoup,
Coyote508 :D
