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

题目: 从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时这个数就是重复了,那么就重新生成。 所以取若干次这个条件,如果若干次越大,那么重复的可能性就越高,重复计算也就越多,但是目前并没有找到更好的方法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

程序员都应该知道的10大算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

681
来自专栏真皮专栏

Data Structure_图图论带权图

交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

411
来自专栏我是攻城师

十大算法,让你轻松进阶高手

3547
来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

2966
来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

703
来自专栏小小挖掘机

大过年的,一起来用Seq2Seq来作对联吧!

Seq2Seq全称Sequence to Sequence,在机器翻译、文章摘要等领域有着广泛的应用。其本身很简单,是一个如下图所示的Encoder-Decod...

8078
来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

2726
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

752
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

2008
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

772

扫码关注云+社区