题目意思:
如果有两个随机数生成器A,B(生成数都小于输入值)
例如n=3;
A 000 001 010
B 000 001 010
两者再随机异或生成的３＊３＝９个数进行期望计算...
计算结果:
*** 000 001 010
000 000 001 010 
001 001 000 011
010 010 011 000
求期望得到4/3.
由于数量庞大 10^9 直接模拟一定超时
所以直接计算每一位的 0 1 个数可以简化计算量
条件一:在异或中,只要两个位不同0 1或1 0 就能得到1
条件二:计算每一位的0 1出现的个数,例如上面,最低位(假设i为二进制权,i=1)1出现1次,
0出现3-1次所以表中得到最低位是1的个数就是1*2+2*1=4个,所以这一位贡献的期望值
是(1*2+2*1)*i/(3*3)=4/9;如此计算第二位,1出现1次,同样贡献期望值为(1*2+2*1)*i/(3*3)=8/9,
此时(i=2)；第三为i=4....
只要算出产生数中每一位的0 1个数k代入 
2*(k*(n-k))*i/(n*n) ==> 2*p*(1-p)*i  其中 p=(n-k)/n  表示 0在该位出现的概率...
代码如下:
#include <stdio.h>
int main()
{
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int t,i,n,s;
    double r,p;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        r=0;
        for(i=0;i<32;i++){
            s=1<<i;
            p=((n/s>>1)*s+(((n&s)==0)?n%s:s))/(double)n;
            //当前位确定0的个数 (n/s>>1)*s 可以理解为 n/2/s*s ==> n/2后再把 s 位以下的全部清为0 
            //  ((n&s)==0)?n%s:s)可以理解为 如果当前位为1，表示当前为位0的情况有s种，如果当前位为0，则只有n%s种 
            //加起来的和就是 0 的个数了 
            r+= 2*p*(1-p)*s;
        }
        printf("%.2lf\n",r);
    }
    return 1;
}

• Re:强悍 (0) ecjtuzxg 2008-07-29 20:06:02
• Re:膜拜，不过不需要分两种情况 (36) kiro3322 2010-12-24 19:36:44