欢迎访问个人网站来查看此文章：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=x1x2x3...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)=−∑1np(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)=−31log2(31)−32log2(32)−32log2(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} ) −31log2(31) 和 2 个 − 2 3 l o g 2 ( 2 3 ) − \frac{2}{3} log_{2}( \frac{2}{3} ) −32log2(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>#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;}可得运行结果：
1.563422.989114.084684.7681654.768164.084682.989111.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 <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;}