目录
题目：
题目描述：
题目链接：
思路：
思路详解：
式子推导：
编辑
精度问题：
代码：
代码详解：
题目：
题目描述：
题目链接：
蓝桥云课 01串的熵
思路：
思路详解：
这题题目看着很复杂，不要被题目吓到。实际上把式子自己在草稿纸上慢慢推导出来并没有那么难，这题主要难点在于精度问题
式子推导：
精度问题：
这里建议结合代码再来思考
1.为什么不能直接用hs==11625907.5798?
因为浮点数在计算机中以二进制形式存储,许多十进制小数(如0.1)无法精确表示
eg:double a=0.1; double b=0.2; if(a+b==0.3) 结果为false,因为0.3的二进制表示不精确
本题中,log2函数的计算可能引入舍入误差,除法运算(如x/23333333)可能产生不精确的浮点数,最终hs可能与
目标值存在微小差异(如11625907.57980001或11625907.57979999),实际上运行后没有输出结果
2.为什么用浮点数精度误差hs-11625907.5798<0.0001会导致失败?
假设目标值为11625907.5798,但实际计算出的hs可能为11625907.5798000000001或11625907.5797999999999
由于二进制浮点数的精度限制(如double只有53位有效数字),这些微小差异无法避免
实际上用hs-11625907.5798<0.0001运行会一直打印输出结果
3.为什么用绝对误差判断fabs(hs-11625907.5798)<0.0001?
因为绝对误差判断(如fabs(hs-target)<1e-6)允许一定的误差范围:
容忍计算误差:即使hs与目标值有微小差异,只要在允许范围内,任认为相等
符合实际需求:题目给出的目标值可能已四舍五入(如原题中的11625907.5798可能是近似值)
eg:假设目标值为1.0,计算得到hs为0.9999999999999999,则:
hs==1.0->fasle fabs(hs-1.0)<1e-9->true
总结:1.避免直接比较浮点数:使用绝对误差或相对误差判断
2.误差范围选择:根据问题精度要求调整epsilon(如1e-6或1e-9)
3.理解浮点数特性:计算机无法精确表示所有二进制小数,必须处理舍入误差
代码：
代码详解：
#include<bits/stdc++.h> //这题题目看着比较复杂,实际上仔细推导发现并没有那么难,这题主要难点在于精度
using namespace std; //答案是11027421 运行1.9s左右出结果const int n=23333333; //n表示的是串的长度 int main()
{for(int x=0;x<23333333/2;x++) //x表示的是0出现的次数,由题x<y,所以x<23333333/2 {int y=23333333-x; //y表示的是1出现的次数 double p0=(x*1.0)/23333333; //p0表示的是串中0出现的占比,涉及整除,开double类型 double p1=(y*1.0)/23333333; //p1表示的是串中1出现的占比,涉及整除,开double类型 double hs=-p0*log2(p0)*x-p1*log2(p1)*y; //通过草稿纸上的式子推导出来的 if(fabs(hs-11625907.5798)<0.0001) //主要难点就在于这里的精度 {cout<<x<<endl;}}return 0;
}