草庐IT

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

ghost_him 2023-07-12 原文

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

问题描述

对于一个长度为 n 的 01 串 S = x 1 x 2 x 3 . . . x n S = x_{1} x_{2} x_{3} ... x_{n} S=x1​x2​x3​...xn​，香农信息熵的定义为 H ( S ) = − ∑ 1 n p ( x i ) l o g 2 ( p ( x i ) ) H(S ) = − {\textstyle \sum_{1}^{n}} p(x_{i})log_{2} (p(x_{i})) H(S)=−∑1n​p(xi​)log2​(p(xi​))，其中 p ( 0 ) p(0) p(0), p ( 1 ) (1) (1) 表示在这个 01 01 01 串中 0 0 0 和 1 1 1 出现的占比。比如，对于 S = 100 S = 100 S=100 来说，信息熵 H ( S ) = − 1 3 l o g 2 ( 1 3 ) − 2 3 l o g 2 ( 2 3 ) − 2 3 l o g 2 ( 2 3 ) = 1.3083 H(S ) = − \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 H(S)=−31​log2​(31​)−32​log2​(32​)−32​log2​(32​)=1.3083。对于一个长度为 23333333 23333333 23333333 的 01 01 01 串，如果其信息熵为 11625907.5798 11625907.5798 11625907.5798，且 0 0 0 出现次数比 1 1 1 少，那么这个 01 01 01 串中 0 0 0 出现了多少次？

思路

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

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

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

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;
}

可得运行结果：

1.56342
2.98911
4.08468
4.76816
5
4.76816
4.08468
2.98911
1.56342

我们可以发现：

  1. h ( s ) h(s) h(s) 关于 5 对称
  2. 在对称轴的一侧， h ( s ) h(s) 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

正确

答案

11027421

完整的代码

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

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;
}
蓝桥解题spanclasstoken蓝桥杯c++算法

有关第十四届蓝桥杯大赛软件赛省赛-试题 B---01 串的熵 解题思路+完整代码的更多相关文章

  1. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  2. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  3. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru

  4. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  5. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  6. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  7. 程序员如何提高代码能力？ - 2

    前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源

  8. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

随机推荐