讨论下算法导论第5章一道概率题

win_hate

原帖由 void_while 于 2008-7-13 09:49 发表
丢弃是不行的,丢弃的情况下返回什么呢?

套一个循环，生成的数若合格，则跳出 ，返回。若不合格，则继续循环。

silverzi

本楼内容完全跑题，实在对不起，全编辑掉。

[ 本帖最后由 silverzi 于 2008-7-13 10:15 编辑 ]

j_will

了不起

luckheadline

不明白为什么要用二分，这样不行么？
random(a,b)=a+(b-a)*random(0,1)

jackin0627

“
   int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
”
---------
这样就严重破坏了概率的平均分布。

“
  我曾经和同学讨论过用random(0, 1)来产生目标数的二进制位，但问题在于，当目标数不是2^n时无法做到等概率
”
可以先生成一个范围比较大的随机数然m，然后再取模来得到你想要的数n，
这样当然也不是绝对的等概率。但当m远远大于n时，误差就很少了。
如：
  你要得到的数的范是0～N，生成的随机数M=N+1时，
  1~N的根率是（1/N）
  0的概率是（2/N）
  当M = 10*N + 1 时
  1~N的概率变成了  10/(10*N) ＝ 1/N
  0的概率变成了       11/(10*N)
  误差是不是小了很多。

breakhearts

我的想法是这实际上就是完成2^p到(b-a+1)上的一个映射，因为如果我只能做得是运行ra
ndom(0,1)，运行p次，所有可能的{0,1}序列都是等概率的，如果2^p可以整除(b-a+1)是很
简单的情形，如果不存在这样的p的话按以下处理，
1.选择最小p，使得2^p>b-a+1
把2^p个{0,1}序列分成b-a+1和剩下的部分，如果出现前面的情况，直接返回对应映射到(
b-a+1)的值，如出现后面的情况重新实验.写成伪代码就类似。
random(a,b)
{
choice smallest p,s.t 2^p>b-a+1;
rs=0
for i=1 to p
     rs+=2*(random(0,1))
if rs<=b-a+1
    return rs+a
else
     random(a,b)
}

breakhearts

上面算法误差是0，但是运行时间可能会无限

tassard

又来做作业啦 倒

yaya_aoyu

原帖由 zylthinking 于 2008-7-10 01:05 发表
不知行不行， random(0, 1)和int random(int a, int b)假设不是同一个函数， 因此int random(int a, int b)中没作相应逻辑

int random(int a, int b){
    if(a == b){
        return a;
    }

    a ...

这种解法是有问题的，例如当n=5,random_private(5)

n = 0;
for( int i=0; i<5; ++i)
n+=RANDOM(0,1);

问题是n的可能结果只有如下6种，分别为0，1，2，3，4，5
而这5个数生成的概率是不一样的，分别为
0  ==> (1/2)^5
1 ==> (1/2)^5*5
2 ==>  (1/2)^5*10
3 ==> (1/2)^5*10
4 ==> (1/2)^5*5
5 ==> (1/2)^5
那么相应的输出概率也是不相等的。

8楼正解。

kenby

描述random(a, b)过程的一种实现，它只调用random(0,1)。作为a和b的函数，你的程序期望运行时间是多少？

这个题目相当于在能随机生成0,1的前提下，要求生成[0, 1, ...,n-1]范围内的一个整数
1 求出最小的 m，使2^m >= n-1
2 通过random(0,1)，产生一个m比特的整数，这样能随机产生[0, 2^m-1]内的整数，若产生的整数位于[0, n-1]内，则取这个数作为结果。如果这个数在[0,n-1]外，则丢弃它，再次运行算法重新生成一个。

        a) 证明上述算法可以产生 [0, n-1]范围内的随机数
在范围[0,1, ..., n-1, n, ..., 2^m-1]范围内，总共有p = 2^m个数，其中合法的数是[0, 1, ..., n-1]共n个，非法的数为
[n, ..., 2^m-1]共q = 2^m-n个，则有 n + q = p
算法最后会产生一个合法的随机数，假设得到数i的概率为Pi，0 <= i <= n-1， 则

所以上述方法可以产生随机数

        b) 求算法运行的期望时间
设Pi表示产生随机数时运行了i次算法的概率，那么前i-1次产生的都是非法的数，第i次产生的是合法的数，所以

那么