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

相关文章

来自专栏ml

数据挖掘之聚类算法K-Means总结

序   由于项目需要,需要对数据进行处理,故而又要滚回来看看paper,做点小功课,这篇文章只是简单的总结一下基础的Kmeans算法思想以及实现; 正文:   ...

3748
来自专栏崔庆才的专栏

自然语言处理中句子相似度计算的几种方法

在做自然语言处理的过程中,我们经常会遇到需要找出相似语句的场景,或者找出句子的近似表达,这时候我们就需要把类似的句子归到一起,这里面就涉及到句子相似度计算的问题...

3023
来自专栏数据科学与人工智能

【算法】利用文档-词项矩阵实现文本数据结构化

“词袋模型”一词源自“Bag of words”,简称 BOW ,是构建文档-词项矩阵的基本思想。对于给定的文本,可以是一个段落,也可以是一个文档,该模型都忽略...

3827
来自专栏闪电gogogo的专栏

压缩感知重构算法之正则化正交匹配追踪(ROMP)

  在看代码之前,先拜读了ROMP的经典文章:Needell D,VershyninR.Signal recovery from incompleteand i...

3266
来自专栏崔庆才的专栏

TensorFlow Bi-LSTM实现文本分词

本节我们来尝试使用 TensorFlow 搭建一个双向 LSTM (Bi-LSTM) 深度学习模型来处理序列标注(分词)问题,主要目的是学习 Bi-LSTM 的...

6946
来自专栏小鹏的专栏

Tensorflow使用的预训练的resnet_v2_50,resnet_v2_101,resnet_v2_152等模型预测,训练

tensorflow 实现:Inception,ResNet , VGG , MobileNet, Inception-ResNet; 地址: https:/...

8888
来自专栏机器学习与自然语言处理

最大子序列和问题之算法优化

算法一:穷举式地尝试所有的可能 int maxSubsequenceSum(const int a[], int n) { int i, j, k; ...

2017
来自专栏Leetcode名企之路

【Leetcode】64. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

1001
来自专栏WD学习记录

n-gram

N-Gram是大词汇连续语音识别中常用的一种语言模型,对中文而言,我们称之为汉语语言模型(CLM, Chinese Language Model)。汉语语言模型...

943
来自专栏来自地球男人的部落格

Seq2Seq模型

前言: 此文翻译自TensorFlow tutorial: Sequence-to-Sequence Models 本文的尽量在做到意思正确的情况下,做到不...

29410

扫码关注云+社区