z*******3
发帖数: 13709 | 1 就是原题，给一个只能产生0和1的rand()
那么要求做出一个能产生0到n-1的随机函数
看了一堆解法，突然想到一个暴力解法
效率比较低，但是应该从理论上说是没有错的
首先把0到n-1改成1到n
几率是一样的
其次，用给好的rand()生成一串n位的数组
要求，这串数组里面只能有一个1，其它都是0
如果出现其它情况，重做这一步
拿到这一串数组之后，计算那一个1出现的位置
这个1可能出现在第一位也可能出现在最后一位
也就是[1,n]之间的自然数
最后再把得到的数字减1
效率比较低，但是这个伪码实现起来很容易，也便于阅读 |
u******g
发帖数: 89 | 2 N个里面只有1个1的概率是n*2^(-n-1)...N大的时候就永远卡在这了。。。当然理论上
时间无限大的话。。。还是有机会的。。 |
z*******3
发帖数: 13709 | 3 是啊，效率比较低，但是理论上可行
而且这个对于任意p的rand()都可行，只要p大于0
我也看明白了网上那些解法的思路
无非是构建一个pool，然后这个pool里面有n个可能
把这个n个可能进行排序，最后计算得到的是第几种可能
如果大于n的话，就抛掉，重新做
但是这个要求原先的rand()本身是uniform distribution
要是其它的话，就麻烦了
【在 u******g 的大作中提到】
: N个里面只有1个1的概率是n*2^(-n-1)...N大的时候就永远卡在这了。。。当然理论上
: 时间无限大的话。。。还是有机会的。。
|
u******g
发帖数: 89 | 4 ……如果原先不是uniform的话可以用一对搭配成uniform的。。然后再用原来的解法。
。。 |
z*******3
发帖数: 13709 | 5 good
【在 u******g 的大作中提到】
: ……如果原先不是uniform的话可以用一对搭配成uniform的。。然后再用原来的解法。
: 。。
|
z*******3
发帖数: 13709 | 6 貌似这种问题用一些语言可以很简单
比如python，因为python可以直接转换二进制数字
这样最后一步就很简单了
【在 u******g 的大作中提到】
: ……如果原先不是uniform的话可以用一对搭配成uniform的。。然后再用原来的解法。
: 。。
|
i****1
发帖数: 445 | 7 能展开来讲讲吗？
譬如原先的rand01（）不uniform
怎么样用一对保证uniform？
【在 u******g 的大作中提到】
: ……如果原先不是uniform的话可以用一对搭配成uniform的。。然后再用原来的解法。
: 。。
|
b******7
发帖数: 92 | 8
【在 i****1 的大作中提到】
: 能展开来讲讲吗？
: 譬如原先的rand01（）不uniform
: 怎么样用一对保证uniform？
|
z*******3
发帖数: 13709 | 9 假设0的概率是p，1的概率是q=1-p
那么投两次，01和10的概率是一样的，都是pq
遇到00和11就扔掉不用，重复前面的步骤
直到取出一个01或者10的组合为止
这样就可以造出一个uniform的函数
【在 i****1 的大作中提到】
: 能展开来讲讲吗？
: 譬如原先的rand01（）不uniform
: 怎么样用一对保证uniform？
|
z*******3
发帖数: 13709 | 10 另外，我想出来怎么转换二进制string鸟
用java
Integer.parseInt("01010101...", 2); |
i****1
发帖数: 445 | 11 哦，谢了，恍然大悟啊。
01和10就是新的rand01函数了。
【在 z*******3 的大作中提到】
: 假设0的概率是p，1的概率是q=1-p
: 那么投两次，01和10的概率是一样的，都是pq
: 遇到00和11就扔掉不用，重复前面的步骤
: 直到取出一个01或者10的组合为止
: 这样就可以造出一个uniform的函数
|
z*******3
发帖数: 13709 | 12 他说的就是我主贴说的方法的特殊情况
主贴说的是n，他说的是2
【在 i****1 的大作中提到】
: 哦，谢了，恍然大悟啊。
: 01和10就是新的rand01函数了。
|
