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

InMySin

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

回复 10# hellioncu


    思路完全正确，只是等号用的不合适。

hbmhalley

回复 27# bruceteen


    lim sigma_(i=0~n){(0.6^2+0.4^2)^i * (0.4*0.6)} = 0.5

cjaizss

对于确定性的算法，算不出50%,就如同用尺规无法三等份角。
那么就只好用不确定性的手段
比如
在连续两次取随机得到01或者10的时候找01出现的概率

bruceteen

hbmhalley 发表于 2012-10-25 12:22
回复 27# bruceteen

佩服，我数学没你那么好，看不懂
但“极限”的意思就是永远达不到^_^

cjaizss

cjaizss 发表于 2012-10-25 13:01
对于确定性的算法，算不出50%,就如同用尺规无法三等份角。
那么就只好用不确定性的手段
比如

其实本质上和无法三等份角一样的，就是无法用有限的组合搭建出50%
举个更加简单的例子，
在自然数
+,-
/10
三种运算的环境里无法表示1/3

hanzhenlll

1. #include <stdio.h>
   
2. 
   
3. #define LEN 10
   
4. int m_rand[LEN] = {0};
   
5. 
   
6. void clear_arry ()
   
7. {
   
8.         int i;
   
9. 
   
10.         for (i = 0; i < LEN; i++)
    
11.         {
    
12.                 m_rand[i] = 10;
    
13.         }
    
14. 
    
15. }
    
16. void write_num (int num)
    
17. {
    
18.         int i;
    
19. 
    
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. }
    
45. 
    
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)
    
54. 
    
55.                         *rand_40_num = *rand_40_num + 1;
    
56.         }
    
57.        
    
58. }
    
59. 
    
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;
    
66. 
    
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.         }
     
127. 
     
128.         return 0;
     
129. }
     

复制代码

如果我要去面试 肯定是过不了了..... ,每次栈地址都不同，所以拿这个开刀，求值..按比例填入0 , 1值,  从算法的角度基本就是废柴，如果只是实现的话 应该也能算个凑合的方法...

hbmhalley

回复 35# bruceteen


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

leeXsen

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

rookieljw

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