Discussion :

[coyotte507]

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

[souviron34]

pourquoi faire simple quand on peut faire complique

Code :

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

nombre  = a + (random{0,1} * (b-a))

[coyotte507]

Désolé,
La fonction me donne que 0 ou 1, pas un flottant entre.

C'est vrai que ça aurait été plus simple

[Zavonen]

Générer un flottant entre 0 et 1 en binaire
x=0.n0n1n2.........
Toutes les décimales sont 0 ou 1.
En n étapes on atteint une précision de l'ordre de 1/2n
Par la suite si on veut un entier aléatoire entre a et b
prendre d=b-a
et n=a+dx
Reste à déterminer n en fonction de d.
Il suffit de prendre n suffisamment grand pour que 2^n >d

[ToTo13]

Bonjour,

une fonction qui ne donne que des 0 ou 1 !!!!!!
Quelle horreur !!!!
Mais en algo il y a presque toujours une solution alors en voilà une :
- tu génères N nombre aléatoires avec ta fonction que tu stockes dans l'ordre d'apparition.
- le nombre ainsi formé peut être converti en décimal, puis divisé par 2^N-1.
- tu obtiens ainsi un nombre aléatoire dans [0,1].
- ensuite tu utilises la petite fonction que l'on vient de te proposer
Voilà

[coyotte507]

Ok, mais ca me donne pas une solution totalement totalement aléatoire

Sinon,

• si on prend la plus petite puissance de 2 supérieure à b-a,
• qu'on génère un nombre aléatoire entre 0 et cette puissance de 2 - 1 (en générant chaque bit aléatoirement),
• et que si le nombre est compris entre 0 et b-a on le garde
• sinon on reessaye,

Ca marche pas?

[acx01b]

comme le dit toto13 si les 0 et les 1 sont totalement aléatoires le nombre compris entre 0 et 2^n-1 sera totalement aléatoire à priori

[coyotte507]

comme le dit toto13 si les 0 et les 1 sont totalement aléatoires le nombre compris entre 0 et 2^n-1 sera totalement aléatoire à priori

Ok merci

[Matthieu Brucher]

Ok merci

Il suffit que ton générateur ait une dimension suffisamment grande, comme un Mersenne Twister par exemple (pas un générateur à congruence linéaire comme le rand() du C donc).

[PRomu@ld]

(pas un générateur à congruence linéaire comme le rand() du C donc).

Il n'est aléatoire que si tu penses qu'il l'est . L'autre problème avec le rand() du C est qu'il est plus lent que le Mersenne Twister ...