问一道阿里的面试题如何求解

[dazhangpan]

N 年前面试阿里的时候有一道算法题不会做，后来一直念念不忘，在网络搜了一下也没找到答案，至今仍然没想出来...

题目是给一个方法 foo()，能以各 50%的概率随机返回 0 或者 1。问题是基于 foo()方法，实现一个 boo()方法，该方法能以各 10%的概率返回[0-9]中的一个数字。

感觉对受过相关训练的同仁来说应该不难，无奈本人对算法不是太在行 o(╥﹏╥)o

[ytmsdy]

@stackexplode 二分不对的，永远都无法得到 10%这个概率。

[yiqunz]

@gaobing 用 5 位来排列组合比 4 位平均调用频率小，
5 位的平均调用次数是 5/(30/32)≈5.33 ，4 位平均调用次数是 4/(10/16)=6.4 /doge

@zhaorunze @ytmsdy
foo()本身就是二分一种表现 #1 结果导向 #3 过程导向 其实一样的，
看他二分的取值区间和摒弃区间都是一样的
[0-9] 每个数都是 10%，不要应该关注 10%，而是 [0-9] 每个数概率均等，想要概率均等那么区间就要满足 2 的 n 次方
摒弃一部分数字不影响目标数字的概率均等问题，产生了浪费罢了，这是不是和二进制很像 /doge

[zhw2590582]

得到的经验就是，凡是看到 0 和 1 出现的题目，就要联想到二进制解法

[suiterchik]

背后的数学原理是舍弃采样（或者其他的蒙特卡洛方法也行），给你一个硬币，别说均匀分布，高斯分布都能给你采出来

[momocraft]

假想有一个区间从[0,1)开始

每掷一次 foo()为 0 则取左一半，为 1 则取右一半，直到这个区间已经是某个 [0.1*n, 0.1*(n+1)) 的子集时，返回 n

从计算的形状上看也是一种二分。

全用浮点数计算时一定在有限步内结束，在这一点来说比需要重掷的稳定，不过不是严格等概率

[shilyx]

function foo() {
return Math.random() < 0.5;
}

function foo2() {
for (;;) {
let n = 0;
for (let i = 0; i < 4; ++i) {
n *= 2;
if (foo()) {
n += 1;
}
}
if (n <= 9) {
return n;
}
}
}

!function foo2_test(times) {
let res = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ];

for (var i = 0; i < times; i++) {
res[foo2()] += 1;
}

for (let i = 0; i < res.length; ++i) {
console.log(times + "次调用中" + i + "的次数： " + res[i]);
}
} (10000);

[st2523684]

类似加权调度算法

[Mohanson]

硬币连续抛掷 32 次得到一个随机 u32 数字，然后取余 10 即可.

[wsssss]

//随机 return 0 到 3
foo0_3(){
return foo() + foo()*2;
}

//随机 return 0 到 15
foo0_15{
return foo0_3() + foo0_3()*4;
}

main(){
//随机给 a 赋值，范围是 0 到 15，超过 9，再重新给 a 赋值；
int a = foo0_15;
while( 9 < a ){
a = foo0_15;
}
return a;
}

[myd]

@Mohanson 这么说也能换成 u16 或 u8 ？

[wsssss]

//随机 return 0 到 3
foo0_3 () {
return foo() + foo() * 2;
}

//随机 return 0 到 15
foo0_15 () {
return foo0_3() + foo0_3() * 4;
}

main () {
//随机给 a 赋值，范围是 0 到 15，超过 9，再重新给 a 赋值；
int a = foo0_15;
while ( 9 < a ) {
a = foo0_15();
}
return a;
}

[lxy42]

leetcode 有一道类似的题目, 使用 rand7 实现 rand10: https://leetcode.com/problems/implement-rand10-using-rand7/

解决方法是拒绝-接受采样: https://en.wikipedia.org/wiki/Rejection_sampling

[Mohanson]

@myd u8 太小了，0-5 数字出现几率会比其他会多一点

[hitmanx]

@Mohanson u32 和 u8 的问题依然一样啊，只是更趋近于 10%而已，依然不是严格意义上的 10%

[mahone3297]

@gaobing
@myd
这种舍弃 6 种，不返回，重新计算 的做法，从数学上讲，是否符合概率？最后得出的，真是是 10% 么？

[wutiantong]

1 楼（&2 楼）的解法是正确且本质的，这里分享一些额外的思考：

1. 不可能存在一个有限步的解法（证明略）
2. 不一定要每组 4 次，也可以每组 5 次，每组 6 次，，，
3. 如果我们关注调用 foo() 方法的次数，那么每组 4 次的期望值是 6.4 次，而每组 5 次的期望值是 5.33333333 次
4. 每组 5 次的方案是调用 foo()方法次数（期望值）最少的方案

[buxudashi]

思考了一下，给个最优解吧。
有十个位置，每个位置被 0 或 1 占位。于是就有了 0000000000-1111111111 （即 0-9 共 10 个位置）得到一个数字 x
这个数字每右移 1 位，只要大于 0，接着右移，而右移的次数称为 k
这个 k 就是 0-9 中的一个数字。所以 foo( )随机取 10 次，这 10 次组成的 x 所取的 k，就是答案。
2 楼给的答案有个极端最差，就是无穷次运行 foo 都会在后面 6 个数字里，取不到数字的。

[epicnoob]

@buxudashi 明显不对，k=0 的概率是 1/1024

[buxudashi]

@epicnoob k 为 0，再右移，右移后 k+1 ；

这个 K 就是 x 最高位所在的位置。当位置在第 0 位时，经过上一次操作，k 变成 1.
答案是 k-1 呀，就是 0.
因为是右移，它就不是 1/1024，而是 1/10，因为一共才移 10 次

[buxudashi]

10 个位置，这题就变向的变成 了：
最高位为 1 为位置 t 的地方。t 为 0-9 中的某一个数字。求 t