01串的熵（蓝桥杯）

01串的熵

问题描述

对于一个长度为n的01串 S=$x_1{x}_2{x}_3$…$x_n$，香农信息熵的定义为 H(S) = $-{\sum }_1^{n}p(x_i)lo{g}_2(p(x_i))$，其中 p(0), p(1) 表示在这个01串中0和1出现的占比。

比如，对于 S=100 来说，信息熵 H(S) = $-\frac{1}{3}lo{g}_2(\frac{1}{3})-\frac{2}{3}lo{g}_2(\frac{2}{3})-\frac{2}{3}lo{g}_2(\frac{2}{3})$ = 1.3083

对于一个长度为23333333的01串，如果其信息熵为11625907.5798，且0出现次数比1少，那么这个01串中0出现了多少次？

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填与这个整数，填与多余的内容将无法得分。

答案：11027421

题意解释

这道题目是关于香农信息熵的计算问题。香农信息熵是信息论中用来量化信息预期值的一个概念，通常用于衡量信息的不确定性。在这个问题中，我们需要根据给定的信息熵值和一些条件来计算一个长度为23333333的01串中0出现的次数。

题目描述了一个长度为n的二进制字符串S，由0和1组成。香农信息熵H(S)的计算公式为：
H(S) = $-{\sum }_1^{n}p(x_i)lo{g}_2(p(x_i))$

其中， p(x_i) 表示在字符串中字符i出现的相对频率。对于二进制字符串，i只能是0或1，所以上式中的求和是对i=0和i=1的情况。

题目给出了一个具体的例子，对于字符串S=100，其信息熵计算如下：
$H(S)=-p(0){\log }_2(p(0))-p(0){\log }_2(p(0))-p(1){\log }_2(p(1))$

由于字符串S=100中，0出现了两次，1出现了一次，所以p(0)=2/3，p(1)=1/3，代入公式得到：
$H(S)=-\frac{2}{3}{\log }_2\left(\frac{2}{3}\right)-\frac{2}{3}{\log }_2\left(\frac{2}{3}\right)-\frac{1}{3}{\log }_2\left(\frac{1}{3}\right)$

现在，我们有一个长度为23333333的01串，其信息熵已知为11625907.5798。题目还告诉我们，这个字符串中0出现的次数比1少。我们的任务是计算出0出现的次数。

为了解决这个问题，我们需要设置两个变量，分别表示0和1出现的次数，然后根据信息熵的定义和给定的条件建立方程，求解这个方程即可得到0出现的次数。需要注意的是，由于0出现的次数比1少，我们可以设0的次数为x，1的次数为23333333-x。

暴力枚举

这段代码是用C++编写的，目的是计算在一个给定长度和信息熵的01串中0出现的次数。下面我会逐行进行注释：

#include<bits/stdc++.h>  // 引入几乎所有的C++标准库
using namespace std;  // 使用标准命名空间int main()  // 程序的主函数
{int n=23333333;  // 01串的长度double m=11625907.5798;  // 给定的信息熵// 从0试探到n，找出0的出现次数for(int ling=0; ling<=n; ling++)  {int yi=n-ling;  // 1出现的次数为总长度减去0出现的次数double p_ling=1.0*ling/n;  // 计算0出现的概率double p_yi=1.0*yi/n;  // 计算1出现的概率// 计算以0出现的概率为基础的熵部分double h_ling= - ling * p_ling *log2(p_ling);// 计算以1出现的概率为基础的熵部分double h_yi= - yi * p_yi * log2(p_yi);double h=h_ling+h_yi;  // 计算总熵// 检查当前总熵h是否接近给定的信息熵m，1e-4为容差值if(fabs(h-m)<1e-4){cout<<ling;  // 如果是，输出0出现的次数break;  // 找到答案后结束循环}}return 0;  // 程序正常结束
}

这个程序会枚举0出现的次数从0到n（串的总长度），对于每一个可能的出现次数，计算出相应的信息熵，然后与给定的信息熵m进行比较。如果计算出的信息熵与给定的信息熵在一定的误差范围内（小于$(1\times 10^{-4})$），程序就会输出当前枚举的0的出现次数，并结束循环。