g********E
发帖数: 178 | 1 有一个只能产生0和1的随机函数，写一个能产生0到n-1的随机函数 |
F******F
发帖数: 63 | |
j*****y
发帖数: 1071 | 3 bless
需要每个数的概率相等吗？
【在 g********E 的大作中提到】
: 有一个只能产生0和1的随机函数，写一个能产生0到n-1的随机函数
|
f****s
发帖数: 74 | 4 练一个，欢迎找错。
int rand(int n)
{
int re=0;
while(1){
int t=n;
re=0;
while(t){
re=(re<<1)+rand01();
t>>=1;
}
if(t
return t;
}
} |
f****s
发帖数: 74 | 5 显然需要啊。不需要的话我直接return 一个0就完了。
【在 j*****y 的大作中提到】
: bless
: 需要每个数的概率相等吗？
|
g********E
发帖数: 178 | 6 谢谢MM
是的，老题了，估计我就是传说中的“开胃菜吃成了主菜”,sigh
【在 j*****y 的大作中提到】
: bless
: 需要每个数的概率相等吗？
|
g********E
发帖数: 178 | 7 很简洁明了啊，赞
求问怎么才能练到这个水平？
【在 f****s 的大作中提到】
: 练一个，欢迎找错。
: int rand(int n)
: {
: int re=0;
: while(1){
: int t=n;
: re=0;
: while(t){
: re=(re<<1)+rand01();
: t>>=1;
|
f****s
发帖数: 74 | 8 mm羞煞我也。刚开始练leetcode，才练了两遍，离板上的大牛差的远了。
【在 g********E 的大作中提到】
: 很简洁明了啊，赞
: 求问怎么才能练到这个水平？
|
A**u
发帖数: 2458 | 9 其实不好写
【在 g********E 的大作中提到】
: 有一个只能产生0和1的随机函数，写一个能产生0到n-1的随机函数
|
g********E
发帖数: 178 | 10 真的吗，谢谢安慰。。
fanscs写的那个很好，其实思路挺简单的，结果让我写代码，我先紧张了估计有10分钟
，才终于get to the right track..
【在 A**u 的大作中提到】
: 其实不好写
|
|
|
d******e
发帖数: 164 | 11 int rand(int n)
{
while (true) {
int t = n, r = 0;
while (t) {
r = (r << 1) + rand01();
t >>= 1;
}
if (r < n) return r;
}
}
【在 f****s 的大作中提到】
: 练一个，欢迎找错。
: int rand(int n)
: {
: int re=0;
: while(1){
: int t=n;
: re=0;
: while(t){
: re=(re<<1)+rand01();
: t>>=1;
|
i****1
发帖数: 445 | 12 这样行不行？
int rand(int n)
{
int ret = 0;
while (1)
{
for (int i = 0; i < n; i++)
{
ret += rand01();
}
if (ret < n) return ret;
}
}
【在 g********E 的大作中提到】
: 有一个只能产生0和1的随机函数，写一个能产生0到n-1的随机函数
|
g********E
发帖数: 178 | 13 不行吧，
n=2,
1/4概率得到0，1/2概率得到1
【在 i****1 的大作中提到】
: 这样行不行？
: int rand(int n)
: {
: int ret = 0;
: while (1)
: {
: for (int i = 0; i < n; i++)
: {
: ret += rand01();
: }
|
r**h
发帖数: 1288 | 14 这个显然不行
sum of binomial distribution，显然不会是平均分布
（反过来如果N够大会趋向于高斯分布）
这题的思路其实就是，生成一个log n位的数，其每一位做一次随机数(0, 1)就好了。
如果结果大于n那么reject
【在 i****1 的大作中提到】
: 这样行不行？
: int rand(int n)
: {
: int ret = 0;
: while (1)
: {
: for (int i = 0; i < n; i++)
: {
: ret += rand01();
: }
|
j*****y
发帖数: 1071 | 15 nice.
【在 r**h 的大作中提到】
: 这个显然不行
: sum of binomial distribution，显然不会是平均分布
: （反过来如果N够大会趋向于高斯分布）
: 这题的思路其实就是，生成一个log n位的数，其每一位做一次随机数(0, 1)就好了。
: 如果结果大于n那么reject
|
n*******w
发帖数: 687 | 16 两个bug
t的初始值应该是n-1
返回的应该是re
其实最优解是从高位往低位generate，如果中间结果就已经大于等于n的话，直接
reject，从头开始。
【在 f****s 的大作中提到】
: 练一个，欢迎找错。
: int rand(int n)
: {
: int re=0;
: while(1){
: int t=n;
: re=0;
: while(t){
: re=(re<<1)+rand01();
: t>>=1;
|
b******7
发帖数: 92 | 17 还有一个bug，没有判断不合法输入，n<=0时会死循环
【在 n*******w 的大作中提到】
: 两个bug
: t的初始值应该是n-1
: 返回的应该是re
: 其实最优解是从高位往低位generate，如果中间结果就已经大于等于n的话，直接
: reject，从头开始。
|
z*******3
发帖数: 13709 | 18 循环n次
每一次判断0还是1
然后把n次循环结果加起来
这是0到n
1到n-1其实就是
1加上0到n-2次
所以最后结论应该是
循环n-2次，每一次判断0还是1
然后加起来，最后结果再加1
int r=1;
for(int i=0;i
r = r + rand01();
return r; |
u******g
发帖数: 89 | 19 你这是Binomial分布。。
【在 z*******3 的大作中提到】
: 循环n次
: 每一次判断0还是1
: 然后把n次循环结果加起来
: 这是0到n
: 1到n-1其实就是
: 1加上0到n-2次
: 所以最后结论应该是
: 循环n-2次，每一次判断0还是1
: 然后加起来，最后结果再加1
: int r=1;
|
J*****a
发帖数: 4262 | 20 这是典型错误啊 得到n-1的概率超小的
【在 z*******3 的大作中提到】
: 循环n次
: 每一次判断0还是1
: 然后把n次循环结果加起来
: 这是0到n
: 1到n-1其实就是
: 1加上0到n-2次
: 所以最后结论应该是
: 循环n-2次，每一次判断0还是1
: 然后加起来，最后结果再加1
: int r=1;
|
|
|
b*******l
发帖数: 590 | 21 这个不正是此类问题的考点吗。
【在 j*****y 的大作中提到】
: bless
: 需要每个数的概率相等吗？
|
y***i
发帖数: 8 | 22 int rand(int n) {
int ret = 0;
for(int i = 0; i < n; i++)
ret += rand01();
return ret % n;
} |
l*****a
发帖数: 14598 | 23 不对
for example n=3
ret =0..7
【在 y***i 的大作中提到】
: int rand(int n) {
: int ret = 0;
: for(int i = 0; i < n; i++)
: ret += rand01();
: return ret % n;
: }
|
a********n
发帖数: 1287 | 24 不要循环到n吧。
shift n，直到0.
【在 i****1 的大作中提到】
: 这样行不行？
: int rand(int n)
: {
: int ret = 0;
: while (1)
: {
: for (int i = 0; i < n; i++)
: {
: ret += rand01();
: }
|
