网站建设申请费用,推广平台使用,产品宣传片公司,wordpress哪个版本快欢迎访问个人网站来查看此文章#xff1a;http://www.ghost-him.com/posts/db23c395/ 问题描述
对于一个长度为 n 的 01 串 Sx1x2x3...xnS x_{1} x_{2} x_{3} ... x_{n}Sx1x2x3...xn#xff0c;香农信息熵的定义为 H(S)−∑1np(xi)log2(p(xi))H(S ) − {\textstyl… 欢迎访问个人网站来查看此文章http://www.ghost-him.com/posts/db23c395/ 问题描述
对于一个长度为 n 的 01 串 Sx1x2x3...xnS x_{1} x_{2} x_{3} ... x_{n}Sx1x2x3...xn香农信息熵的定义为 H(S)−∑1np(xi)log2(p(xi))H(S ) − {\textstyle \sum_{1}^{n}} p(x_{i})log_{2} (p(x_{i}))H(S)−∑1np(xi)log2(p(xi))其中 p(0)p(0)p(0), p (1)(1)(1) 表示在这个 010101 串中 000 和 111 出现的占比。比如对于 S100S 100S100 来说信息熵 H(S)−13log2(13)−23log2(23)−23log2(23)1.3083H(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.3083H(S)−31log2(31)−32log2(32)−32log2(32)1.3083。对于一个长度为 233333332333333323333333 的 010101 串如果其信息熵为 11625907.579811625907.579811625907.5798且 000 出现次数比 111 少那么这个 010101 串中 000 出现了多少次
思路
我们先来看这个 h(s)h(s)h(s) 的定义然后先把 h(s)h(s)h(s) 这个函数写出来。
我们看这个 100100100 的例子一共有 1 个 12 个 0h(s)h(s)h(s) 也是由 1 个 −13log2(13)− \frac{1}{3} log_{2} ( \frac{1}{3} )−31log2(31) 和 2 个 −23log2(23)− \frac{2}{3} log_{2}( \frac{2}{3} )−32log2(32) 构成再根据公式我们可以推测如果有 n 个 0m 个 1那么 h(s)h(s)h(s) 应该是由 n 个 p(0)log2(p(0))p(0)log_{2}(p(0))p(0)log2(p(0)) 构成同时由 m 个 p(1)log2(p(1))p(1)log_{2}(p(1))p(1)log2(p(1)) 构成。p(0)p(0)p(0) 表示 0 出现的占比p(0)nnmp(0) \frac{n}{n m}p(0)nmn p(1)mnmp(1) \frac{m}{n m}p(1)nmm。所以我们可以设一个函数用来求解 h(s)h (s)h(s)。
#include iostream
#include cstring
#include algorithm
#include cmathusing 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我们可以发现
h(s)h(s)h(s) 关于 5 对称在对称轴的一侧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; // 减少 0else 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
#include cmathusing 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;
}
