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 : Sélectionner tout - Visualiser dans une fenêtre à part
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