首页 > 代码库 > uva 10883 - Supermean(组合数学+数值优化)
uva 10883 - Supermean(组合数学+数值优化)
题目链接:uva 10883 - Supermean
题目大意:给出n个数,每相邻两个数求平均数,将得到n-1个数,这n-1个数每相邻的两个数求平均值,将得到n-2个数。一次类推,求最后得到的那个数的值。
解题思路:类似与杨辉三角,第i个数起始被加了C(n?1i?1)次。总共有2n?1个数相加。但是因为n有50000,250000根本存不下,所以借助log函数。
例:
中间的2可以通过蓝色和红色两条路径影响最后的答案。
#include <cstdio>
#include <cstring>
#include <cmath>
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
int n;
double ans = 0, a, c = 0;
scanf("%d", &n);
for (int j = 0; j < n; j++) {
scanf("%lf", &a);
double tmp = log2(fabs(a));
if (j) {
c += log2(double(n-j)/j);
tmp += c;
}
if (a < 0)
ans -= pow(2, tmp - n + 1);
else
ans += pow(2, tmp - n + 1);
}
printf("Case #%d: %.3lf\n", i, ans);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。