算法-从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 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

604
来自专栏程序员叨叨叨

6.2 逻辑操作符(Logical Operators)

Cg语言中有3种逻辑操作符(也被称为boolean Operators),如表 2 所示,逻辑操作符运算后的返回类型均为bool类型。

703
来自专栏量子位

TensorFlow全新的数据读取方式:Dataset API入门教程

作者:何之源 首发于知乎专栏:AI Insight 量子位 已获授权编辑发布 转载请联系原作者 Dataset API是TensorFlow 1.3版本中引入的...

3429
来自专栏Python数据科学

5种方法教你用Python玩转histogram直方图

直方图是一个可以快速展示数据概率分布的工具,直观易于理解,并深受数据爱好者的喜爱。大家平时可能见到最多就是 matplotlib,seaborn 等高级封装的库...

741
来自专栏专知

如何在TensorFlow上高效地使用Dataset

【导读】近日,机器学习工程师Francesco Zuppichini发表一篇教程,讲解了在TensorFlow中高效地输入数据集的方法,作者首先抛弃了feed-...

9065
来自专栏点滴积累

使用Python实现子区域数据分类统计

目录 前言 geopandas简介 子区域数据分类统计 总结 一、前言        最近碰到一个需求,需要统计某省内的所有市的某数据分布情况信息。现有该省的数...

3727
来自专栏腾讯NEXT学位

你需要知道的算法之基础篇

3737
来自专栏和蔼的张星的图像处理专栏

opencv小项目练习之数独求解

对于给定的数独照片(尽可能干净整齐),进行一系列处理,提取位置和数字信息,这中间可能要用到一系列图像处理的基本算法,数字识别时初步打算用knn来做,knn对手写...

471
来自专栏人工智能头条

TensorFlow全新的数据读取方式:Dataset API入门教程

1713
来自专栏AI科技评论

开发 | TensorFlow全新的数据读取方式:Dataset API入门教程

AI科技评论按:本文作者何之源,该文首发于知乎专栏AI Insight (https://zhuanlan.zhihu.com/ai-insight),AI科技...

3095

扫码关注云+社区