第十四届蓝桥杯大赛软件赛省赛-试题 B---01 串的熵解题思路+完整代码-Toy模板网

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯大赛软件赛省赛-试题 B---01 串的熵解题思路+完整代码。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

欢迎访问个人网站来查看此文章：http://www.ghost-him.com/posts/db23c395/

问题描述

对于一个长度为 n 的 01 串 $S = x_{1} x_{2} x_{3} ... x_{n}$ ，香农信息熵的定义为 ${\textstyle \sum_{1}^{n}} p(x_{i})log_{2} (p(x_{i}))$ ，其中 $p (0)$ , p $(1)$ 表示在这个 $01$ 串中 $0$ 和 $1$ 出现的占比。比如，对于 $S = 100$ 来说，信息熵 $\frac{1}{3} log_{2} ( \frac{1}{3} ) − \frac{2}{3} log_{2}( \frac{2}{3} ) − \frac{2}{3} log_{2} ( \frac{2}{3} ) = 1.3083$ 。对于一个长度为 $23333333$ 的 $01$ 串，如果其信息熵为 $11625907.5798$ ，且 $0$ 出现次数比 $1$ 少，那么这个 $01$ 串中 $0$ 出现了多少次？

思路

我们先来看这个 $h (s)$ 的定义，然后先把 $h (s)$ 这个函数写出来。

我们看这个 $100$ 的例子：一共有 1 个 1，2 个 0， $h (s)$ 也是由 1 个 $\frac{1}{3} log_{2} ( \frac{1}{3} )$ 和 2 个 $\frac{2}{3} log_{2}( \frac{2}{3} )$ 构成，再根据公式，我们可以推测：如果有 n 个 0，m 个 1，那么 $h (s)$ 应该是由 n 个 $p(0)log_{2}(p(0))$ 构成，同时，由 m 个 $p(1)log_{2}(p(1))$ 构成。 $p (0)$ 表示 0 出现的占比， $\frac{n}{n + m}$ ， $\frac{m}{n + m}$ 。所以我们可以设一个函数，用来求解 $h (s)$ 。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

// p0 表示 '0' 出现的次数；p1表示 '1' 出现的次数
double h(int p0, int p1) {
	// 需要将 3/6 化简成 1/2 这样的形式，简化运算的时间
	// 将分子和分母共同除以它们的最大公因数即可。
	int t0 = p0, t1 = p1;
	// 获取最大公因数
	int t = gcd(t0, t1);
	// 化简
	t0 /= t, t1 /= t;
	// 获取总数
	double t2 = t0 + t1;
	// 返回的答案
	double res = 0;
	// 套入公式
	res -= p0 * (t0 / t2) * (log2(t0) - log2(t2));
	res -= p1 * (t1 / t2) * (log2(t1) - log2(t2));
	return res;
}

int main () {
	// 100 由 2个0 和 1个1 组成，代入函数以验证函数的正确性
	cout << h(2, 1) << endl;
	
	return 0;
}

可得运行结果：

1.30827

与题目中的结果一致，说明我们写的代码是正确的。

接下来我们就应该来求这个题目的答案了。

我们先来看看这个函数的性质：我们多求几组数字。我们以长度为 10 的所有 01 串来看：

int main () {
	cout << h(9, 1) << endl;
	cout << h(8, 2) << endl;
	cout << h(7, 3) << endl;
	cout << h(6, 4) << endl;
	cout << h(5, 5) << endl;
	cout << h(4, 6) << endl;
	cout << h(3, 7) << endl;
	cout << h(2, 8) << endl;
	cout << h(1, 9) << endl;
	return 0;
}

可得运行结果：

我们可以发现：

$h (s)$ 关于 5 对称
在对称轴的一侧， $h (s)$ 的值单调

由于题目中说明：且 0 出现次数比 1 少 ，所以，0 的个数一定小于总数的一半，所以 0 的数量越多，熵越大。我们知道了这个性质以后，可以采用二分的方法，将 0 的数量二分出来。

int main () {
	// 0 的数量最小是 1， 最大是 (23333333 + 1) / 2 （总数的一半）
	int l = 1, r = (23333333 + 1) / 2;
	while (l < r) {
		// 获取当前判断的 0 的数量
		int mid = l + r >> 1;
		// 如果熵大于目标值，说明 0 的数量太多了，要减小 0 的数量
		// 如果熵小于目标值，说明 0 的数量太少了，要增加 0 的数量
		if (h(mid, 23333333 - mid) > 11625907.5798) r = mid; // 减少 0
		else l = mid + 1; // 增加 0
	}
	cout << l << endl;
	return 0;
}

可得：

11027421

然后我们再验证一下这个结果：

int main () {
	printf("%.10lf", h(11027421, 23333333 - 11027421));
	return 0;
}

得结果：

11625907.5798144601

正确文章来源地址https://www.toymoban.com/news/detail-409187.html

答案

11027421

完整的代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

double h(int p0, int p1) {
	int t0 = p0, t1 = p1;
	int t = gcd(t0, t1);
	t0 /= t, t1 /= t;
	double t2 = t0 + t1;
	double res = 0;
	
	res -= p0 * (t0 / t2) * (log2(t0) - log2(t2));
	res -= p1 * (t1 / t2) * (log2(t1) - log2(t2));
	return res;
}

int main () {
	int l = 1, r = (23333333 + 1) / 2;
	while (l < r) {
		int mid = l + r >> 1;
		if (h(mid, 23333333 - mid) > 11625907.5798) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}