首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法-从1,...,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值

算法-从1,...,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值

作者头像
chaibubble
发布2018-01-02 11:30:29
1.5K0
发布2018-01-02 11:30:29
举报

题目: 从1,2,3,…..98,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值。 解题思路: 这是阿里巴巴的一道笔试题目,这并不是一道编程类的题目(虽然可以用编程来解决),这更像一道数理统计的题目,由于期望性质:

这里写图片描述
这里写图片描述

那么我们可以先考虑取到的若干个数的某一位: 由于异或的特性, 对任意一个二进制位,取奇数个1异或后会得到1,取偶数个1异或后会得到0,与取0的个数无关。由于2015的二进制为:111 1101 1111,99的二进制为: 000 0110 0011。这意味着对于任何一次(0个除外)选取,选取的到若干个数的二进制数中,11位中每一位都有可能取到1,那么如果取到的1是奇数个,该位置异或后的结果就是1。 经过上面的分析,我们就可以设事件为第i位取到k个1,其中k为奇数,第i位一个共有n个1,m个0,那么事件的概率为:

这里写图片描述
这里写图片描述

于是我们可以得出一个很有意思的结论,在异或之后的二进制数中,每一位取到1的概率是0.5,那么取到0也是0.5,对于离散事件,我们就能求期望了,当然还是0.5。 那么对全部的11位整体考虑,就会用到上面期望的性质,它是11个二进制为的期望的加和:

这里写图片描述
这里写图片描述

这个问题还可以延伸一下,如果把原问题的2015换成1024,那么结果是什么呢? 关键的问题在于2015或1024对结果的印象到底在哪里,我们计算的其实是取若干个数中某一位为1的数目是奇数的概率,那么: 1024 :‭100 0000 0000‬ 99:000 0110 0011 这意味着,2^7,2^8,2^9着三位永远只能是0,根本就没有1,所在在计算最后的期望的时候把这三位记为0就好了,所以结果是275.5。

代码实现: 其实我们可以用代码测试一下,当采用足够大的时候,可以用均值估计期望,所以采用次数设置为10000000。

#include "iostream"    

using namespace std;

int sample(int *a)
{
    //避免生成随机数相等
    bool flag[100];
    //单次采样个数
    int  M = rand()%101;
    int  k = 0;
    int result =0;
    while (k<M)
    {
        //采样值
        int m = rand()%100;
        if(k==0)
        {
            result = a[m];
            flag[m]=0;
            k++;
        }
        if(flag[m])
        {
            flag[m]=0;
            result = result^a[m]; 
            k++;
        }       
    }
    return result;
}
int main()
{
    const int N = 100;
    int  arr[N];
    for (int i = 0;i<N-1;i++)
        arr[i]=i+1;
    arr[N-1] = 2015;
    //采样次数
    int totalnum = 10000000;
    double s=0;
    for (int j = 0;j<totalnum;j++)
    {
        s= s+sample(arr);
    }
    s = s/totalnum;
    cout<<s<<endl;
    getchar();
    return 0;
}

讲真,这个代码的效率不算好,因为为了避免生成随机数重复的情况(比如,取了两个99,但是这种情况在实际情况中不会发生),所以设置了bool型flag[100]数组,它就像一个简易的hash表,索引就是100下下标,值为0,1。某次生成随机数n,当flag[n]为flash时这个数就是重复了,那么就重新生成。 所以取若干次这个条件,如果若干次越大,那么重复的可能性就越高,重复计算也就越多,但是目前并没有找到更好的方法。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-08-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档