【2024.1.19练习】B:01串的熵

发布时间:2024年01月19日

B: 01串的熵(5分)
问题描述

对于一个长度为23333333的01串,如果其信息熵为11625907.5798,且0 出现次数比1 少,那么这个01 串中0出现了多少次?


我的代码:

注意调用<cmath>以便于对数运算。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int ans;
	int n = 23333333;
	double scale = 11625907.5798;
	double s0;
	double s1;
	int i;
	double anticipate;

	for (ans = 0; ans < (n / 2); ans++) {
		s0 = ans / n;
		s1 = (n - ans) / n;
		anticipate = 0;
		for (i = 0; i < ans; i++) {
			anticipate -= (s0)*log2(s0) ;
		}
		for (i = 0; i < n - ans; i++) {
			anticipate -= (s1)*log2(s1);
		}
		if (anticipate == scale) {
			cout << ans << endl;
		}
	}
	return 0;
}

这个答案是错误的,不仅运行时间很冗长(10^{14}),也无法得到答案。

第二重循环太rz了,连续相加重复ans次不如直接乘ans,大大增加了运行时长。


修改后的代码:

#include <iostream>
#include <cmath>
using namespace std;
const int n = 23333333;
const double scale = 11625907.5798;

int main() {
	int ans;
	double anticipate;
	for (ans = 0; ans < (n / 2); ans++) {
		anticipate = 0;
		anticipate -= ans * ans / n * log2(ans / n);
		anticipate -= (n - ans) * (n - ans) / n * log2((n - ans) / n);
		if (abs(anticipate - scale) < 1e-4) {
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}

这个程序依然有问题,尽管和标准代码几乎一模一样,但是无法输出答案。

在经过测试后,发现每次运算anticipate的结果均为inf。

原因:计算ans / n时,由于 ans 和 n?均为整型,结果为0,而log(0)的结果为无穷大。


标准代码:

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

using namespace std;

const int total = 23333333;
const double H = 11625907.5798;

int main() {
    for (int i = 0; i < total / 2; i++) {
        double ans = 0;
        ans -= 1.0 * i * i / total * log2(1.0 * i / total);
        ans -= 1.0 * (total - i) * (total - i) / total * log2(1.0 * (total - i) / total);
        if (abs(ans - H) < 1e-4) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

可以看到,在运算时加上1.0*之后就能将整型化为浮点型,输出正确答案了。

验证答案是否正确时没有使用==符号,而是将计算结果与正确答案的差距限制在1e-4以内。

文章来源:https://blog.csdn.net/FeAtherHZM/article/details/135696524
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。