题解 P1022 【计算器的改良 】

其实这题难点我觉得主要在移项去分母之类的操作，而不在于字符串处理 我们可以通过模拟退火这个玄学的解法来避开这些麻烦的操作，只做字符串处理，处理出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）的差值 下面上代码 ```cpp #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之间的整数，显然分子是等概率往左右两边运动的而不 是只往一边运动，因此需要处理一下