Chinaunix

标题: 如何实现返回0和1的概率为50% [打印本页]
作者: 发仔很忙    时间: 2012-10-20 22:23
标题: 如何实现返回0和1的概率为50%
    前几天去某公司笔试，有道题说的是有个函数foo，返回0的概率是60%，返回1的概率是40%，让你自己写一个函数，使返回0和1的概率是50%，

用前面说的foo函数实现，不能用像c++里面的rand这类的函数，怎么解？
作者: folklore    时间: 2012-10-20 22:30
  1. int half01(){
  2.         static int c0=0;
  3.         int rs=-1;
  4.         switch(foo()){
  5.         case 0:
  6.                 c0++;
  7.                 if(c0==5){
  8.                         c0=0;
  9.                         rs=1;
  10.                 }else{
  11.                         rs=0;
  12.                 }
  13.                 break;
  14.         case 1:
  15.                 rs=1;
  16.                 break;
  17.         default:        //impossible
  18.                 break;
  19.         }
  20.         return rs;
  21. }
复制代码
作者: Ager    时间: 2012-10-20 22:33
我的直觉是：要用到一些高等数学和概率论的知识和方法。
作者: 发仔很忙    时间: 2012-10-20 22:36
回复 2# folklore


c0 == 5这步如何解释，这个half01里的foo函数只是调用一次，c0怎么等于5？
作者: Ager    时间: 2012-10-20 22:38
个人直觉：用离散的方法，解决不了此题。


作者: 发仔很忙    时间: 2012-10-20 22:38
folklore 发表于 2012-10-20 22:30

哦，看懂了，谢啦
作者: folklore    时间: 2012-10-20 22:39
回复 4# 发仔很忙


    who tell you it is called only one time?

btw, there is a bug in the above code, fix it as the following:
  1. int half01(){
  2.         static int c0=0;
  3.         int rs=-1;
  4.         switch(foo()){
  5.         case 0:
  6.                 if(c0++==5){
  7.                         c0=0;
  8.                         rs=1;
  9.                 }else{
  10.                         rs=0;
  11.                 }
  12.                 break;
  13.         case 1:
  14.                 rs=1;
  15.                 break;
  16.         default:        //impossible
  17.                 break;
  18.         }
  19.         return rs;
  20. }
复制代码
作者: folklore    时间: 2012-10-20 22:43
回复 6# 发仔很忙


    
作者: Ager    时间: 2012-10-20 22:43
本帖最后由 Ager 于 2012-10-20 22:44 编辑
发仔很忙 发表于 2012-10-20 22:36
回复 2# folklore

c0 == 5这步如何解释，这个half01里的foo函数只是调用一次，c0怎么等于5？


有static的嘛……


作者: hellioncu    时间: 2012-10-20 22:55
return foo() + foo() + foo() + foo() + foo() == 2 ? 0 : 1;
作者: 群雄逐鹿中原    时间: 2012-10-20 23:03
我的直觉，太简单了，调用foo两次即可，
连续两次，出现 0 1 和 1 0 的概率是一样的，于是就能构造出50%
（两次返回 0 0 或 1 1的结果丢掉，重新调用）

返回0 1 -> 当作 0
返回1 0 -> 当作 1

代码简单的要屎，如下

  2. int half01()
  3. {
  4.     while(1)
  5.     {
  6.         int a = foo();
  7.         int b = foo();
  8.   
  9.         if(a != b) return a;
  10.     }
  11. }
复制代码
作者: Ager    时间: 2012-10-21 03:28
本帖最后由 Ager 于 2012-10-21 03:29 编辑
群雄逐鹿中原 发表于 2012-10-20 23:03
我的直觉，太简单了，调用foo两次即可，
连续两次，出现 0 1 和 1 0 的概率是一样的，于是就能构造出50%
...


很妙，很妙，赞 —— ：）

我是在考虑更一般的情况 …… baz(foo(sP),tP)……



作者: haomarlin    时间: 2012-10-21 11:36
2l和11l的都不错。
2楼的方法一开始不是等概率的，虽然长时间看是等概率的。
11l的方法不收敛。
这个挺难的……

作者: 发仔很忙    时间: 2012-10-21 20:16
牛人，非常厉害回复 11# 群雄逐鹿中原


   
作者: folklore    时间: 2012-10-21 20:34
回复 13# haomarlin


    分析得很好，我开头光想着充分利用样本空间了。。。。
如果foo是真正的随机数，且运行foo的代价很小，11楼是最好的算法了。样本空间利用率也达到近24%。
作者: 发仔很忙    时间: 2012-10-21 20:47
回复 7# folklore

看了这个11L的程序，我发现你这个程序有问题，这个程序永远不会出现连续出现大于6次0的概率，按理说连续出现6次0的概率是有可能的，所以这个程序有点问题

   
作者: folklore    时间: 2012-10-21 20:55
回复 16# 发仔很忙


    对，有这个问题啊。这样的话没办法，要100%充分利用样本空间不可能了（当前条件下）
只能弃去最后两个，这样样本空间利用率80%，却不太好了。不过还没想到好办法。
作者: 群雄逐鹿中原    时间: 2012-10-21 22:12
haomarlin 发表于 2012-10-21 11:36
11l的方法不收敛。


对，这是个问题。

大家有看到10L的办法吗？肯定有道理，我想他不会随便乱写的。
可惜啊，看不懂。。
作者: hbmhalley    时间: 2012-10-21 22:24
回复 18# 群雄逐鹿中原


    为什么不收敛?
作者: folklore    时间: 2012-10-21 22:45
回复 18# 群雄逐鹿中原


    c(5,2)*0.4^2*0.6^3 ，好像不会等于50%的样子。
此外，两个机率相加会改变原机率的分布，可能不太好，但 foo比较特殊只产生0，1倒可以例外。
作者: bruceteen    时间: 2012-10-22 08:57
群雄逐鹿中原 发表于 2012-10-21 22:12
大家有看到10L的办法吗？肯定有道理，我想他不会随便乱写的。

foo() + foo() + foo() + foo() + foo() == 2
必须出现 3个0 和 2个1
这正和foo出现0和1的概率相同
我先拉S去，一会回来想想
作者: Ace_kream    时间: 2012-10-22 13:46
回复 18# 群雄逐鹿中原


   
大家有看到10L的办法吗？肯定有道理，我想他不会随便乱写的。
可惜啊，看不懂。。


稍微解释下10L思想。

foo() 出现0-60%，1-40%.
那么频率 0 ： 1 = 3 ：２

所以５个foo（）相加 等于2 就是出现3次0，2次1。

所以 foo（）* 5 == 2 的概率就是

(C53(0.6) + C52(0.4))/C52 = ( 5*4*3/(3*2*1) + 5*4/(2*1) ) / (5*4/(2*1))= (3 + 2) / 10 = 50%

思想就是简单的高中排列组合。
作者: Ace_kream    时间: 2012-10-22 14:11
回复 11# 群雄逐鹿中原

回复 10# hellioncu

hellioncu 发表于 2012-10-20 22:55
return foo() + foo() + foo() + foo() + foo() == 2 ? 0 : 1;


错了，错了。
向大家赔罪， 轻易的回帖了。

10L的方法应该是错的。

5个foo（）相加 出现 2个1 ，3个0的组合应该是 （C53*0.6*C52*0.4）= 24
而5个foo（）相加的所有组合是2*2*2*2*2 = 32
这样5个foo（）相加等于2的概率是 24 / 32 = 75%

所以 10L的 说法应该是有问题的。

我之前回的帖子是大家可以不看。 算错了， 好长时间没碰高中的知识了。请见谅
作者: fengyun530    时间: 2012-10-22 14:13
hellioncu 发表于 2012-10-20 22:55
return foo() + foo() + foo() + foo() + foo() == 2 ? 0 : 1;

这样好高深。看不懂！
作者: bruceteen    时间: 2012-10-22 14:51
本帖最后由 bruceteen 于 2012-10-22 15:01 编辑
Ace_kream 发表于 2012-10-22 14:11
这样5个foo（）相加等于2的概率是 24 / 32 = 75%

我用程序模拟，算出来是 1080 / 3125 = 34.56%
  1. int sim_equ = 0;
  2. int sim_sum = 0;

  4. void sim( int index, int sum1 )
  5. {
  6.     if( index == 0 )
  7.     {
  8.         if( sum1 == 0 )
  9.             ++sim_equ;
  10.         ++sim_sum;
  11.         return;
  12.     }

  14.     sim( index-1, sum1-0 );
  15.     sim( index-1, sum1-0 );
  16.     sim( index-1, sum1-0 );
  17.     sim( index-1, sum1-1 );
  18.     sim( index-1, sum1-1 );
  19. }

  21. #include <stdio.h>

  23. int main()
  24. {
  25.     sim( 5, 2 ); // 计算 2-foo()-foo()-foo()-foo()-foo() == 0 的数目
  26.     printf( "%d/%d = %f\n", sim_equ, sim_sum, sim_equ*1.0/sim_sum );

  28.     return 0;
  29. }
复制代码
作者: flw    时间: 2012-10-22 14:56
尼玛，程序员也太难做了吧？
这种题目考的到底是数学还是编程？
作者: bruceteen    时间: 2012-10-22 15:07
我认为这题是无解的
foo() 每次平行产生 0 0 0 1 1
无论什么公式，N次调用foo()后产生 5^N 个可能
5^a / 5^b == 2 是没有整数解ab的
作者: Ace_kream    时间: 2012-10-22 15:18
本帖最后由 Ace_kream 于 2012-10-22 15:50 编辑

回复 27# bruceteen


    C52*0.4*0.4*0.6*0.6*0.6 =0.3456

惭愧。。。。

通过此次数学考验  我突然感觉我好惭愧。。。

从前的知识白学了。
作者: Ager    时间: 2012-10-22 16:14
本帖最后由 Ager 于 2012-10-22 16:20 编辑

@群雄逐鹿中原
@bruceteen
@Ace_kream

10L的解法，从我的直觉看（又来了……），肯定是错的。

我的直觉是这样的：

如果调用foo() 1次，
那么：
P[foo()=0] = .6
P[foo()=1] = .4
fin.

如果调用foo() 2次，
从输出结果看，一共有2^2=4种可能性，分别是：
P[0 + 0 = 0] = .6 * .6 = .36
P[0 + 1 = 1] = .6 * .4 = .24
P[1 + 0 = 1] = .6 * .6 = .24
P[1 + 1 = 2] = .4 * .4 = .16
根据加法交换律（0+1 == 1+0），最后的结果可以合并为：
P[foo().twice = 0] = .36
P[foo().twice = 1] = .48
P[foo().twice = 2] = .16
fin.

(......)

以上，仅供参考，呵呵 …… ：）

作者: safedead    时间: 2012-10-22 16:26
[ 本帖最后由 safedead 于 2012-10-22 16:30 编辑 ]

[quote][size=2][color=#000]flw 发表于 2012-10-22 14:56[/color] [url=forum.php?mod=redirect&goto=findpost&pid=22323673&ptid=3776304][img]static/image/common/back.gif[/img][/url][/size]
尼玛，程序员也太难做了吧？
这种题目考的到底是数学还是编程？[/quote]

前一阵子我倒是碰上了这个问题
某函数（也可理解为某设备），生成了1G bits的随机数
用NIST的随即测试软件测试发现0和1的几率不对等
现在要处理，使得这1G bits的数据通过NIST软件测试
一种很简单的方法，就是分割成32 bytes的块，全做一遍sha256，用结果代替输入
效果还凑合
至于自己编程，我对自己的数学没信心。。

备注：请勿在商业随机数测试用这个方法，作弊是能检测出来的
作者: InMySin    时间: 2012-10-25 11:35
10L的确有问题，28L终于找出原因，我想的时候也考虑这个，10L不行
运行foo（）5次。。。。 ans == 2 就是要出现3个0，2个1，就是 0.6^3 * 0.4^2
然后总共的可能情况有 nchoosek( 5 , 3 );
所以 ans == 2 的概率应该是所有情况概率相加，也就是nchoosek( 5 , 3 ) * 0.6^3 * 0.4^2 跟28L一样了。。。 =0.3456

现在要考虑有没有解的问题了。。。如果抛弃一些样本点，就会出现不收敛的情况，只能只有很少的概率会一直死循环。。。但是有些应用不能依靠概率，察。。
作者: liuiang    时间: 2012-10-25 11:50
回复 10# hellioncu


    思路完全正确，只是等号用的不合适。
作者: hbmhalley    时间: 2012-10-25 12:22
本帖最后由 hbmhalley 于 2012-10-25 12:23 编辑

回复 27# bruceteen


    lim sigma_(i=0~n){(0.6^2+0.4^2)^i * (0.4*0.6)} = 0.5
作者: cjaizss    时间: 2012-10-25 13:01
对于确定性的算法，算不出50%,就如同用尺规无法三等份角。
那么就只好用不确定性的手段
比如
在连续两次取随机得到01或者10的时候找01出现的概率
作者: bruceteen    时间: 2012-10-25 13:02
hbmhalley 发表于 2012-10-25 12:22
回复 27# bruceteen

佩服，我数学没你那么好，看不懂
但“极限”的意思就是永远达不到^_^
作者: cjaizss    时间: 2012-10-25 13:11
cjaizss 发表于 2012-10-25 13:01
对于确定性的算法，算不出50%,就如同用尺规无法三等份角。
那么就只好用不确定性的手段
比如

其实本质上和无法三等份角一样的，就是无法用有限的组合搭建出50%
举个更加简单的例子，
在自然数
+,-
/10
三种运算的环境里无法表示1/3
作者: hanzhenlll    时间: 2012-10-25 13:46
本帖最后由 hanzhenlll 于 2012-10-25 13:54 编辑
  1. #include <stdio.h>

  3. #define LEN 10
  4. int m_rand[LEN] = {0};

  6. void clear_arry ()
  7. {
  8.         int i;

  10.         for (i = 0; i < LEN; i++)
  11.         {
  12.                 m_rand[i] = 10;
  13.         }

  15. }
  16. void write_num (int num)
  17. {
  18.         int i;

  20.        
  21.         if (num == 1)
  22.         {
  23.                 for (i = 0; i < LEN; i++)
  24.                 {
  25.                         if (m_rand[i] != num)
  26.                         {
  27.                                 m_rand[i] = num;
  28.                                 break;
  29.                         }
  30.                 }
  31.         }
  32.         else if (num == 0)
  33.         {
  34.                 for (i = LEN; i > 0; i--)
  35.                 {
  36.                         if (m_rand[i] != num)
  37.                         {
  38.                                 m_rand[i] = num;
  39.                                 break;
  40.                         }
  41.                 }
  42.                
  43.         }
  44. }

  46. void get_num (int *rand_60_num, int *rand_40_num)
  47. {
  48.         int i;
  49.         for (i = 0; i < LEN; i++)
  50.         {
  51.                 if (m_rand[i] == 1)
  52.                         *rand_60_num = *rand_60_num + 1;
  53.                 else if (m_rand[i] == 0)

  55.                         *rand_40_num = *rand_40_num + 1;
  56.         }
  57.        
  58. }

  60. int  foo ()
  61. {
  62.         int n = 0;
  63.        
  64. //        printf ("n-------=-===============>%x\n", &n);
  65.         int rand_60_num = 0, rand_40_num = 0;

  67.         if ((int)&n & 0x10)
  68.         {
  69.                         get_num (&rand_60_num, &rand_40_num);
  70.                         if (rand_60_num < 6)
  71.                         {
  72.                                 write_num (1);
  73.                                 return 1;
  74.                         }
  75.                         else if (rand_40_num < 4)
  76.                         {
  77.                                 write_num (0);
  78.                                 return 0;
  79.                         }
  80.                         else if ((rand_60_num == 6) && (rand_40_num == 4))
  81.                         {
  82.                                 clear_arry();
  83.                                 write_num (1);
  84.                                 return 1;
  85.                         }
  86.                        
  87.         }
  88.         else
  89.         {
  90.                         get_num (&rand_60_num, &rand_40_num);
  91.                         if (rand_40_num++ < 4)
  92.                         {
  93.                                 write_num (0);
  94.                                 return 0;
  95.                         }
  96.                         else if (rand_60_num++ < 6)
  97.                         {
  98.                                 write_num (1);
  99.                                 return 1;
  100.                         }
  101.                         else if ((rand_60_num == 6) && (rand_40_num == 4))
  102.                         {
  103.                                 clear_arry();
  104.                                 write_num (0);
  105.                                 return 0;
  106.                         }
  107.                
  108.         }
  109.        
  110.        
  111.                
  112. }
  113. int main (int argc, char *argv[])
  114. {
  115.         int n = 2, i = 0, j = 1;
  116.        
  117.         clear_arry ();
  118.         for (j = 1; j < 10; j++)
  119.         {
  120.         for (i = 0; i < 10; i++)
  121.         {
  122.                 n = foo ();
  123.                 printf ("n--->[%d]\n", n);
  124.         }
  125.                 sleep (j);
  126.         }

  128.         return 0;
  129. }
复制代码
如果我要去面试 肯定是过不了了..... ,每次栈地址都不同，所以拿这个开刀，求值..按比例填入0 , 1值,  从算法的角度基本就是废柴，如果只是实现的话 应该也能算个凑合的方法...
作者: hbmhalley    时间: 2012-10-25 17:57
回复 35# bruceteen


    啊 .. 这里的意思是 2n 次调用(遇01/10则停)以内获得 01 的概率，有限次内确实是不到 0.5 的
    但如果不限次数，则是等于 0.5 的。
    而获得非 01/10 的概率随调用次数是呈指数下降的
    有个形象的比喻，这种指数下降的概率两位数次方以后，是小于宇宙射线改变改变内存存储状态的概率的，因而可以忽略。
    所谓“永远不是” 也只是理论上的可能而已。
作者: leeXsen    时间: 2012-10-29 13:14
我有一个想法，不知道对不对。我是这样想的：假设我们要生成N个随机数，先用foo()生成并保存在a[N]中，那么数组a中0占60%，1占40%(N足够大)，然后把60%中的10%由0变成1，这样0和1就各占一半。
作者: rookieljw    时间: 2012-10-29 20:29
感觉求（6/10）∧x+（4/10）∧y=1/2
作者: koolcoy    时间: 2012-10-30 00:14

  2. int func() {
  3.     return foo() * 2 + 1 - foo() <= 1
  4. }
复制代码
目测俺的方法最简单{:3_189:}
作者: isaacxu    时间: 2012-10-30 06:07
对于独立事件，P(AB)=P(A)P(B)，所以只需调用两次foo，P(0，1)与P(1，0)的概率都是0.24，由此就可得到一个等概率。这样当（0，1）出现时返回0，当（1，0）出现时，返回1。
  1. /**
  2. * File:MyFoo.java
  3. * -----------------
  4. * P(0,1)=P(0)*P(1)=0.6*0.4=0.24
  5. * P(1,0)=P(1)*P(0)=0.4*0.6=0.24
  6. * P(0,1)=P(1,0)
  7. */
  8. package org.cudemo;

  10. /**
  11. * @author isaacxu
  12. *
  13. */
  14. public class MyFoo {

  16.        
  17.         public static void main(String[] args) {
  18.                 int val = myfoo();
  19.         System.out.println(val);
  20.         }
  21.        
  22.         // foo that returns 0 by 0.6 and 1 by 0.4
  23.         static int foo()
  24.         {
  25.                 int i=0;
  26.             // some code here
  27.                 return i;
  28.         }
  29.        
  30.         // returns  0 and 1 by 0.5 probability
  31.         static int myfoo()
  32.         {
  33.                 int returnVal= 0;
  34.             int firstCall = foo();
  35.             int secondCall = foo();
  36.             //get pair (0,1) or (1,0)
  37.             while(firstCall==secondCall){
  38.                     firstCall = foo();
  39.                     secondCall = foo();
  40.             }
  41.           
  42.             if (firstCall == 0 && secondCall == 1)
  43.                 returnVal= 0;   // get 0.24 probability
  44.             if (firstCall == 1 && secondCall == 0)
  45.                     returnVal = 1;   // get 0.24 probability
  46.             return returnVal;  
  47.         }

  49. }
复制代码
作者: lieque13    时间: 2012-10-30 14:10
本身此题目就提供了基本概率函数，没必要重新编写其他函数，不然笔试肯定不合格，这个题目更多的是考察如何构造算法：
因为 0:60% 1:40%
所以 00:36% 01:24% 10:24% 11:16%
可以看出 01 和10出现的概率是一样的
所以函数中若出现11和00则重新产生随机数
出现10或01则可以
作者: net_robber    时间: 2012-10-30 15:09
A1:A2= x:y
A1+A2 : A2+A1 =1:1
作者: FaintKnowledge    时间: 2012-10-30 15:28
本帖最后由 FaintKnowledge 于 2012-10-30 15:34 编辑

回复 1# 发仔很忙


作者: fallening_cu    时间: 2012-10-30 17:23
本帖最后由 fallening_cu 于 2012-10-30 17:56 编辑

其实可以这样：
  1. #include <cstdint>
  2. #include <cstddef>

  4. #include <vg.hpp>//在这里 https://github.com/fengwang/random_variate_generator

  6. int foo()
  7. {
  8.     static vg::vg<double> gen(0.0, 1.0);
  9.     if ( gen() > 0.4 ) return 1;
  10.     return 0;
  11. }

  13. int gen_50_50()
  14. {
  15.     std::uint64_t const a = 6364136223846793005ULL;
  16.     std::uint64_t const b = 1442695040888963407ULL;
  17.     std::uint64_t const mask = 256;
  18.     std::uint64_t s = 1;

  20.     for ( std::size_t i = 0; i != 64; ++i )
  21.     {
  22.         s <<= 1;
  23.         s += foo();
  24.     }

  26.     static std::uint64_t ans = s;
  27.     ans *= a;
  28.     ans += b;

  30.     return ans & mask ? 1 : 0;
  31. }
  32. //test
  33. int main()
  34. {
  35.     const std::size_t n = 8888888;

  37.     int acc = 0;

  39.     for ( std::size_t i = 0; i != n; ++i )
  40.         acc += gen_50_50();

  42.     std::cout << "accumulation of " << n << " 0-1 random number is " << acc << "\n";

  44.     return 0;
  45. }

复制代码
运行了3次，分别输出 4444442、4444443 和 4444445，应该可以接受作为一个 50-50 的随机数生成器



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2