题解 P1022 【计算器的改良 】
Anakin
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)的差值
下面上代码
```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之间的整数,显然分子是等概率往左右两边运动的而不
是只往一边运动,因此需要处理一下