如何实现返回0和1的概率为50%

发仔很忙

    前几天去某公司笔试，有道题说的是有个函数foo，返回0的概率是60%，返回1的概率是40%，让你自己写一个函数，使返回0和1的概率是50%，

用前面说的foo函数实现，不能用像c++里面的rand这类的函数，怎么解？

fallening_cu

其实可以这样：

1. #include <cstdint>
   
2. #include <cstddef>
   
3. 
   
4. #include <vg.hpp>//在这里 https://github.com/fengwang/random_variate_generator
   
5. 
   
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. }
    
12. 
    
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;
    
19. 
    
20.     for ( std::size_t i = 0; i != 64; ++i )
    
21.     {
    
22.         s <<= 1;
    
23.         s += foo();
    
24.     }
    
25. 
    
26.     static std::uint64_t ans = s;
    
27.     ans *= a;
    
28.     ans += b;
    
29. 
    
30.     return ans & mask ? 1 : 0;
    
31. }
    
32. //test
    
33. int main()
    
34. {
    
35.     const std::size_t n = 8888888;
    
36. 
    
37.     int acc = 0;
    
38. 
    
39.     for ( std::size_t i = 0; i != n; ++i )
    
40.         acc += gen_50_50();
    
41. 
    
42.     std::cout << "accumulation of " << n << " 0-1 random number is " << acc << "\n";
    
43. 
    
44.     return 0;
    
45. }
    
46. 
    

复制代码

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

FaintKnowledge

回复 1# 发仔很忙

net_robber

A1:A2= x:y
A1+A2 : A2+A1 =1:1

lieque13

本身此题目就提供了基本概率函数，没必要重新编写其他函数，不然笔试肯定不合格，这个题目更多的是考察如何构造算法：
因为 0:60% 1:40%
所以 00:36% 01:24% 10:24% 11:16%
可以看出 01 和10出现的概率是一样的
所以函数中若出现11和00则重新产生随机数
出现10或01则可以

isaacxu

对于独立事件，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;
   
9. 
   
10. /**
    
11. * @author isaacxu
    
12. *
    
13. */
    
14. public class MyFoo {
    
15. 
    
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.         }
    
48. 
    
49. }

复制代码

koolcoy

1. 
   
2. int func() {
   
3.     return foo() * 2 + 1 - foo() <= 1
   
4. }
   

复制代码

目测俺的方法最简单{:3_189:}

rookieljw

感觉求（6/10）∧x+（4/10）∧y=1/2

leeXsen

我有一个想法，不知道对不对。我是这样想的：假设我们要生成N个随机数，先用foo()生成并保存在a[N]中，那么数组a中0占60%，1占40%(N足够大)，然后把60%中的10%由0变成1，这样0和1就各占一半。

hbmhalley

回复 35# bruceteen


    啊 .. 这里的意思是 2n 次调用(遇01/10则停)以内获得 01 的概率，有限次内确实是不到 0.5 的
    但如果不限次数，则是等于 0.5 的。
    而获得非 01/10 的概率随调用次数是呈指数下降的
    有个形象的比喻，这种指数下降的概率两位数次方以后，是小于宇宙射线改变改变内存存储状态的概率的，因而可以忽略。
    所谓“永远不是” 也只是理论上的可能而已。