【数论系列】指数与对数（数值优化）

编程基础 • 2024-10-19 11:06 • 阅读 33

一. 对数

一. 对数

1. 基本公式

（1）log（n）：以e为底的对数

（2）log10（n）：以10为底的对数

（3）换底公式：logx（n）= log（n）/log（x）

2. 基本性质

（1）负数与0无对数可言

（2）log(1) = 0；loga（a） = 1

（3）log（M*N） = log（M） + log（N）

（4）log（M/N） = log（M） - log（N）

（5）

（6）log（a^b） = b*log(a)

（7）若 $a = b^{m}$ ：则 m = logb（a）

（8）完全展开式

3. 应用场景

（1）用对数来进行数值优化，主要是把大数化为小树运算或者比较

（2）与对数/指数有关的题目

（3）与唯一分解定理联系：n = a^p1*b^p2*c^p3*......，则log(n) = p1log(a) + p2log(b) + p3log(c) + ......

4. 例题分析

（1）UVA 10883 Supermean

Problem Description

给你n个数字，让你求相邻数字的平均数n-1个，再求这n-1个平均数的平均数。。。求出最后一个数字（n<=50000）

二项式系数+数值优化。很容易看出来 $sum = (\sum_{0}^{n-1}N[i]*C(n-1,i))/2^{n-1}$ ，而double的范围为-2^1024 ~ +2^1024 ，但这里达到了2^50000绝对超出double范围了，可以看出最后的结果却很小，也就是说我们必须把中间运算过程变小，这里就考虑对数的优化。

直接取log10（sum） = log10（N[0]*C(n-1,0) + N[1]*C(n-1,1) + .....） - log10(2)*(n-1)中累和部分不能拆分，所以这里我们干脆一项一项的拆分即 sum += pow（10，log10(N[i]) + log10(C(n-1,i)) - log10(2)*(n-1)）；注意这里有负数，而负数没有对数，所以需要在负数时使用sum-= ，在正数时使用sum+=；

还要处理一下 C(n-1,i) ：C(n-1,i) = (n-i)/i*C(n-1,i-1)，log10( C(n-1,i)) = log10(n-i) + log10(C(n-1,i-1)) - log10(i)；

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define eps 0.000001
int main()
{
    int T;
    int t = 0;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        t++;
        double sum = 0;
        double C = 0;
        for(int i = 0;i<n;i++){
            double num;
            scanf("%lf",&num);
            if(i!=0)C = log10(n-i) + C - log10(i);
            if(num==0)sum+=0;
            else if(num < 0){
                sum-=pow(10,log10(-num) + C - log10(2)*(n-1));
            }
            else{
                    //cout<<num<<" "<<C<<" "<<n-1<<" "<<pow(10,log(10.4))<<endl;
                sum+=pow(10,log10(num) + C - log10(2)*(n-1));
            }
        }
        printf("Case #%d: %.3lf\n",t,sum);
    }
    return 0;
}

今天的文章【数论系列】指数与对数（数值优化）分享到此就结束了，感谢您的阅读。

【数论系列】 指数与对数（数值优化）

一. 对数

1. 基本公式

2. 基本性质

3. 应用场景

4. 例题分析

相关推荐

【数论系列】指数与对数（数值优化）