题解 P1022 【计算器的改良 】

2018-10-28 11:23:15


其实这题难点我觉得主要在移项去分母之类的操作,而不在于字符串处理 我们可以通过模拟退火这个玄学的解法来避开这些麻烦的操作,只做字符串处理,处理出a的系数和常数,把等号两边分别作为两个函数f(a)和g(a),用模拟退火去寻找一个a,使f(a)-g(a)=0即可

下面介绍一下模拟退火这种玄学的解法:

首先要了解下物理上冶金退火过程:

众所周知,温度越高,分子运动越剧烈,我们可以理解为分子下一时刻出 现在离此时刻更远距离的概率与温度成正相关。但在冶金工业中,如果将金属从一个较高温度突然冷却至rt,大多数分子并不能占据能量较低的位置,因而造成了体系的不稳定。因此就有了退火这个缓慢降温过程。在温度慢慢降低的过程中,分子大范围移动的概率降低,一旦找到了一个较低能量的区域,分子占据这个位置并放出能量,而随温度降低,分子得不到足够的能量再次逃出这个区域,因此继续移动只能占据能量更低的位置,如此往复循环便使大部分分子都找到的能量较低的位置。

模拟退火这个办法就是用算(bao)法(li)模拟这个过程。我们引入几个参数来模拟这个过程:温度t,降温系数dt,变量ansx,函数值ans。因为温度越高,函数值大幅度变化的概率越大,所以我们用tempx=ansx+rand()*t 来表示每次ansx的变化,并将tempx带入函数中解得一个新解new_ans,如果new_ans比当前值更接近0,则更新ans(接受此解),如果new_ans不如ans接近0,我们以玄学概率exp(-df/t)接受这个新解(df为new_ans和ans)的差值

下面上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define MAXN 1000+10
using namespace std;
char s[MAXN];
struct f{int numa,num;}L,R;
double Abs(double x){return x>0?x:-x;};
double F(double x){
    double la=L.numa,l=L.num,ra=R.numa,r=R.num;
    return Abs(x*la+l-(x*ra+r));
}
double ans=1e18+7,ansx;
void solve(){//模拟退火过程
    double t=192,dt=0.985;
    double xx=ansx;
    while(t>1e-12){
        double tempx=ansx+((rand()<<1)-RAND_MAX)*t;
        double new_ans=F(tempx);
        double df=new_ans-ans;
        if(df<0){
            xx=tempx;
            ansx=xx;
            ans=new_ans;
        }
        else if(exp(-df/t)*RAND_MAX>rand()){
            xx=tempx;
        }
        t*=dt;
    }
}   
int main(){
    cin>>s;
    int i=0;
    int n=strlen(s)-1;
    while(s[i]!='='){//字符串处理,L代表等式左边(f(x))
        int cnt=0;
        bool flag=0;
        bool a=0;
        if(s[i]=='+') ++i;
        if(s[i]==45){
            flag=1;
            ++i;
        }
        if(s[i]<=57&&s[i]>=48){
            cnt=s[i]-48;
            while(s[++i]<=57&&s[i]>=48){
                cnt=(cnt<<1)+(cnt<<3)+s[i]-48;
            }
        }
        if(s[i]=='a'){
            a=1;
            ++i;
            if(cnt==0) ++L.numa;
            else if(flag&&cnt){
                L.numa-=cnt;
            }
            else{
                L.numa+=cnt;            
            }
        }
        if(!a){
            if(flag){
                L.num-=cnt;
            }
            else{
                L.num+=cnt;
            }
        }
    }
    i=0;
    while(s[++i]!='=');
    ++i;
    while(i<n){//R代表等式右边(g(x))
        int cnt=0;
        bool flag=0;
        bool a=0;
        if(s[i]=='+') ++i;
        if(s[i]==45){
            flag=1;
            ++i;
        }
        if(s[i]<=57&&s[i]>=48){
            cnt=s[i]-48;
            while(s[++i]<=57&&s[i]>=48){
                cnt=(cnt<<1)+(cnt<<3)+s[i]-48;
            }
        }
        if(s[i]=='a'){
            a=1;
            ++i;
            if(cnt==0) ++R.numa;
            else if(flag&&cnt){
                R.numa-=cnt;
            }
            else{
                R.numa+=cnt;            
            }
        }
        if(!a){
            if(flag){
                R.num-=cnt;
            }
            else{
                R.num+=cnt;
            }
        }
    }
    solve();//保证准确率,跑两遍
    solve();
    printf("a=%.3lf",ansx);
    return 0;
}

解释一下为什么是rand()*2-RAND_MAX而不直接用rand():

rand()产生的是0~RAND_MAX之间的一个整数,而rand()*2-RAND_MAX代表

-RAND_MAX~RAND_MAX之间的整数,显然分子是等概率往左右两边运动的而不 是只往一边运动,因此需要处理一下