cpper编程论坛 - 查看单个帖子

Elminster · #12 (**permalink**) 2008-04-06

引用:

作者: liuxinyu

给一个思路，用一个骰子可以随机获得1到6任何数字，现在用2个骰子，根据乘法原理，可以获得，6x6等于36种不同排列，并且均匀分布，采用6进制数，骰子1的点数-1，乘以6后加上骰子2的点数-1，就可以机会均等表示0-35。因此用k个骰子，就可以均匀表示0到6^k-1的范围。

值得注意的是，并不能用反复掷一个骰子然后将点数相加来获取1到6n之间的随机数，因为这样概率分布不均匀。

但是，如果n不是正好的6^k-1，则严格说，概率并不均匀。例如我希望通过2个dice，获取0到6这7个数字，必然从8到35代表的数字，超出范围，如果仅仅将结果模n,则就会面对鸽笼原理问题（或叫抽屉原则问题），必然某些数字的概率高，令一些概率低。

一个办法是丢弃，我考虑另一个调整办法，从rand ( m ) 生成rand ( n )。不失一般性，假设(m,n)=1。也就是互素。
首先，寻找k使得m^k<=n<m^(k+1)
令n和m^(k+1)-1的最小公倍数为lcm，并且令
n*p=lcm
(m^(k+1)-1)*p=lcm
我们把生成的随机数乘以q再处以p就将0到m^(k+1)-1均匀分布到0到n-1，附带的scheme代码如下，在MIT scheme上测试通过。

代码:

(define (find-power m n)
  (define (find-power-from k m n)
    (if (and (< (expt m k) n) (< n (expt m (+ k 1))))
      k   
      (find-power-from (+ k 1) m n)))
  (find-power-from 0 m n))
         
(define (generate k m)
  (if (= k 0) 
    (random m) 
    (+ (* (generate (- k 1) m) m) (random m))))

(define (rand-from n m)
    (let ((k (find-power m n))) 
      (let ((upper-bound (- (expt m (+ k 1)) 1)))
        (let ((p (/ (lcm upper-bound n) n))
              (q (/ (lcm upper-bound n) upper-bound)))
          (floor (/ (* (generate k m) q) p))))))

你除了之后未必能得到整数。