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

void_while

5.1-2 用random(0,1)来实现random(a,b),并估计运行时间.

想到一种解法,分治法:
     1.分解,将a-b区间分成2部分,通过random(0,1)控制,则进入前半部和后半部的概率是一样的;
     2.递归的处理前后两个部分,若问题足够小,即落到某个具体位置上时,则直接返回;

伪代码:
int random( a, b )
{
   if( a == b )
     return a;
   if( random( 0, 1 ) )
     return random( a, (a+b)/2 );
   else
     return random( (a+b)/2 + 1, b );
}

但仔细分析下发现有问题.

令 n = b-a, 问题简化为 1/n = f( 1/(2^x) ),
                root
                 / \
                0    1
               / \   / \
             /   .....   \
            0 .........  1
时间复杂度为 O(lgn),通过lgn次random(0,1)调用,即生成长度为lg(b-a)的"前后后前..."随机序列来控制最后落定的位置,类似2叉决策树的决策过程,x次random(0,1)调用最多可能产生2^x条路径,即最多可能返回2^x种结果,每条路径的产生概率相等,即1/(2^x).

但如果n不是2的整数次方,不可能将概率平均分配到每条路径,所以不可能在有限次调用内生成精确的平均返回概率.

如, n=8时,可以取x=3,正好8种返回结果的概率一样,都是1/8.但如果n=7,那么b的返回概率可能会是2/8,其余值的返回概率均为1/8.
  
所以得到的结果是不精确的,上网查了很久,也没找到答案

void_while

没人理 自己偷偷顶下

有人一起做题玩么?

zylthinking

不知行不行， 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;
    }

    assert(b > a);
    int n = b - a;
    return a + random_private(n);
}

int random_private(int b){
    if(b % 2){
        int half = b / 2;
        if(random(0, 1) == 0){
            return random(0, half);
        }
        return random(half + 1, b);
    }

    int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
}

void_while

赞,应该就是楼上的思路!
我咋想不到呢

win_hate

原帖由 void_while 于 2008-7-8 23:24 发表
5.1-2 用random(0,1)来实现random(a,b),并估计运行时间.

想到一种解法,分治法:
     1.分解,将a-b区间分成2部分,通过random(0,1)控制,则进入前半部和后半部的概率是一样的;
     2.递归的处理前后两个部分 ...

按书上的记号，random(3,7) 应该随机生成 3,4,5,6,7 中的一个。你好像只生成 4 个数。

win_hate

原帖由 zylthinking 于 2008-7-10 01:05 发表
int random_private(int b){
    if(b % 2){
        int half = b / 2;
        if(random(0, 1) == 0){
            return random(0, half);
        }
        return random(half + 1, b);
    }

    int n = 0;
    for(int i = 0; i < b; ++i){
        n += random(0, 1);
    }
    return n;
}

看不懂，后面累加的含义是什么？

虑而后能得

呵呵 顶一下 楼主还是比较强的

win_hate

这个题目相当于在能随机生成 0, 1 的前提下，要求随机生成 n 个整数。

把要生成的数标记为 0,1,2,..., n-1

取最小的 m，使得 2^m >= n-1

通过随机生成 0,1 的函数生成一个  m 比特整数（随机生成每一位），这样能随机生成 [0, 2^m) 内的整数。

随机生成一个 [0,2^m) 中的整数，如果这个数大小在 [0,n-1] 内，则取这个数为结果。
如果这个数在 [0,n-1] 外，则丢弃它，重新生成一个。

[ 本帖最后由 win_hate 于 2008-7-12 11:46 编辑 ]

tyc611

原帖由 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 ...

1. 你的random(b)应该产生[0, b]，因此，b % 2的判断是错误的（因为这里有b + 1个数）
2. 后面的循环产生的b + 1个数的每个数的概率是不均等的。举个简单的例子：产生0和b的概率为(1/2)^b，而不是期望的1/(b+1)。
   如果你写成了n = n0 + n1 + n2 + .... + nb的形式，其中ni的产生概率为1/2，就很容易知道你方法有问题了

[ 本帖最后由 tyc611 于 2008-7-12 11:52 编辑 ]

tyc611

原帖由 win_hate 于 2008-7-12 11:43 发表
这个题目相当于在能随机生成 0, 1 的前提下，要求随机生成 n 个整数。

把要生成的数标记为 0,1,2,..., n-1

取最小的 m，使得 2^m >= n-1

通过随机生成 0,1 的函数生成一个  m 比特整数（随机生成每一位 ...

我曾经和同学讨论过用random(0, 1)来产生目标数的二进制位，但问题在于，当目标数不是2^n时无法做到等概率