197 条题解
-
4
PowderHan LV 10 @ 2017-05-08 08:02:08
经典二分
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <iomanip> #include <cstdlib> using namespace std; float ans[5]; float a,b,c,d; int n=0; float f(float x) { return ((a*x+b)*x+c)*x+d; } void solve(float l,float r) { if(f(l)*f(r)>0&&(((r-l)<1)||n>=2))//注意这里n>=2啊，不要像我一样作死了半天写成了n>=1。 return; float mid=(l+r)/2; if(f(mid)<=1e-4 && f(mid)>=-1e-4) { ans[n++]=mid; return; } solve(l,mid),solve(mid,r); } int main() { cin>>a>>b>>c>>d; solve(-100,100); printf("%.2lf %.2lf %.2lf",ans[0],ans[1],ans[2]); return 0; } -
2
没用 搜索 也没有二分 也可以过啊
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; double a,b,c,d; int t=0; double ans[4]; int main() { cin>>a>>b>>c>>d; for(double i=-100;i<=100;i+=0.001) { if(t==3) break; double s=a*i*i*i+b*i*i+c*i+d; if(s<=0.01&&s>=-0.01) { ans[t]=i; i+=0.99; t++; } } for(int i=0;i<3;i++) printf("%.2lf ",ans[i]); return 0; } -
1
二分的精度问题
如果你是用r-l>eps来判断while是否终止的话，如果你判断对应的函数值f(x)是否为0也是用-eps<f(x)<eps来判断就可能出问题。
因为有可能你的区间对应的曲线斜率很大，导致虽然[l,r]长度非常接近eps了但是在y轴方向上的差距却还是大于eps的，因此即使mid和x非常接近了，但是它们在函数值上的差距还是不能满足条件，所以最后while会终止，但是却不会把mid视为一个根。
解决方法就是设置两个不同的eps1,eps2，其中判断区间长度的eps1要远远小于eps2#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=10000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; double a,b,c,d; double f(double x) { return a*x*x*x+b*x*x+c*x+d; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>a>>b>>c>>d; REP(i,-100,100) { double l=i,r=i+1; if (-eps<f(l)&&f(l)<eps) printf("%.2lf ",l); //else if (-eps<f(r)&&f(r)<eps) printf("%.2lf ",r); else { if (f(l)*f(r)<-eps) { double mid; while (r-l>1e-10) { mid=(l+r)/2; if (-eps<f(mid)&&f(mid)<eps) { printf("%.2lf ",mid); break; } else if (f(mid)>eps) { if (f(l)>eps) { l=mid; } else r=mid; } else { // f(mid)<-eps if (f(l)<-eps) { l=mid; } else r=mid; } } } } } return 0; }如果你把r-l>1e-10改成>eps就会WA
-
1
因为根的范围在[-100,100]，只要求小数后两位，所以直接枚举i从-10000到10000，然后x=i/100，去求值判断是否为根就好了。不需要二分
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=10000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; double a,b,c,d; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>a>>b>>c>>d; for (double i=-10000;i<=10000;i+=1) { double x=i/100; double val=a*x*x*x+b*x*x+c*x+d; if (-eps<val&&val<eps) printf("%.2lf ",x); } return 0; } -
1
#include<cstdio> double a,b,c,d; double f(double x) { return a*x*x*x+b*x*x+c*x+d; } void solve(double l, double r) { double mid=(l+r)/2; if(r-l<0.0001) { printf("%.2f ",mid); return; } else if(f(mid)==0) printf("%.2f ",mid); else if(f(r)==0) printf("%.2f ",r); if(f(l)*f(mid)<0) solve(l,mid); if(f(r)*f(mid)<0) solve(mid,r); } int main() { scanf("%lf%lf%lf%lf", &a, &b, &c, &d); for(int x=-100; x<=100; x++) if(f(x)*f(x+1.0)<=0) solve(x,x+1.0); return 0; } -
1
区间挺大的我们一起来二分吧。
三个答案都在[-100,100]范围内，两个根的差的绝对值>=1,保证了每一个大小为1的区间里至多有1个解，也就是说当区间的两个端点的函数值异号时区间内一定有一个解，同号时一定没有解。那么我们可以枚举互相不重叠的每一个长度为1的区间，在区间内进行二分查找。#include<cstdio> double a,b,c,d; double fc(double x) { return a*x*x*x+b*x*x+c*x+d; } int main() { double l,r,m,x1,x2; int s=0,i; scanf("%lf%lf%lf%lf",&a,&b,&c,&d); for (i=-100;i<100;i++) { l=i; r=i+1; x1=fc(l); x2=fc(r); if (!x1) {printf("%.2lf ",l); s++;} //判断左端点，是零点直接输出。 //不能判断右端点，会重复。 if (x1*x2<0) //区间内有根。 { while (r-l>=0.001) //二分控制精度。 { m=(l+r)/2; if (fc(m)*fc(r)<=0) l=m; else r=m; //计算中点处函数值缩小区间。 } printf("%.2lf ",r); //输出右端点。 s++; } if (s==3) break; //找到三个就退出大概会省一点时间…… } return 0; } -
1
Empire-003 LV 9 @ 2017-07-29 22:06:12
//很奇怪的写法... #include <iostream> #include <cstdio> #include <algorithm> using namespace std; double a, b, c, d; double f(double x) { double ans = a*x*x*x + b*x*x + c*x + d; return ans; } int main() { int tot = 2; cin >> a >> b >> c >> d; for(int i = -100; i <= 100; i++) { if(f(i) == 0) { printf("%.2lf",(double)i); if(!(tot--)) putchar('\n'); else putchar(' '); continue; } if(f(i) * f(i+1) < 0) { for(double k = (double)i; k <= (double)i+1.1; k += 0.001) { //cout << "f(k) = " << f(k) << " k = " << k << endl; if(f(k) < 0.001 && f(k) > -0.001) { printf("%.2lf",k); if(!(tot--)) putchar('\n'); else putchar(' '); break; } } } } return 0; } -
1
枚举万岁！！！
姑且是从-100到99根据提示算出一个长度为1的存在答案的区间[i,i+1]；然后我的做法是将前区间i=x依次加0.001加1000次算出距离0最近的f(x); (x属于[i,i+1])
* 这里我一开始是加0.01共100次算 结果WA了一半，*
* 原因：答案是由万分位四舍五入到千分位而非直接由千分位算出，*
* 不知道有没有和我遇到一样问题的希望你们看得懂 *
然后如果f(i)×f(i+1)=0的话要特殊处理的；
Pascal代码：var a,b,c,d,x,ans,min:double; i,j:longint; function f(i:double):double; begin exit(a*i*i*i+b*i*i+c*i+d); end; begin readln(a,b,c,d); for i:= -100 to 99 do begin if (f(i)*f(i+1)<0) then begin x:=i; min:=1000; for j:= 1 to 999 do begin if abs(f(x))<min then begin min:=abs(f(x)); ans:=x; end; x:=x+0.001; end; write(ans:0:2,' '); end else if (f(i)*f(i+1)=0) then begin if (f(i+1)=0) then write(i+1,'.00 '); end; end; end. -
1
cjoier_gjh LV 8 @ 2017-01-21 23:27:25
#include<stdio.h>
#include<stdlib.h>
#include<string.h>double a,b,c,d;
double f(double x){
return a*x*x*x+b*x*x+c*x+d;
}int main(){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
for(int i=-100;i<=100;i++){
double x1=i,x2=i+1;
if(f(x1)==0)printf("%.2lf ",x1);
else if(f(x1)*f(x2)<0){
while(x2-x1>=0.001){
double k=(x1+x2)/2;
if(f(x1)*f(k)<=0)x2=k;
else x1=k;
}
printf("%.2lf ",x1);
}
}
puts("");
return 0;
} -
1
#include<iostream>
#include<cmath>
#include <cstdio>using namespace std;
int main()
{
double a,b,c,d;
cin>>a>>b>>c>>d;
double i,j;
j=-100.00;
i=j;
for(j;j<=100;j+=0.01)
{
if(i*i*i*a+i*i*b+i*c+d<0)
if(j*j*j*a+j*j*b+j*c+d>0)
{
printf("%.2f ",j);
i=j;
}
if(i*i*i*a+i*i*b+i*c+d>0)
if(j*j*j*a+j*j*b+j*c+d<0)
{
printf("%.2f ",j);
i=j;
}
}
return 0;
}-
伊人 @ 2017-10-04 09:15:34
你的做法我很喜欢2333
-
-
0
zhanghanchu LV 7 @ 2022-03-03 20:19:35
暴 力 出 奇 迹：
#include<bits/stdc++.h> using namespace std; int main() { double a,b,c,d; cin>>a>>b>>c>>d; for(double i=-100.000;i<=100.000;i+=0.001) { double j=i+0.001,x=a*i*i*i+b*i*i+c*i+d,y=a*j*j*j+b*j*j+c*j+d; if(x<=0 and y>=0 or x>=0 and y<=0) { double ans=(i+j)/2; printf("%.2f ",ans); } } return 0; } -
0
//感觉我的代码是有问题的但是过了 //那过了就过了吧 ```#include<cstdio> #include<iostream> using namespace std; int main() { double a,b,c,d,i,x,y,l,r,m,z; scanf("%lf%lf%lf%lf",&a,&b,&c,&d); for(i=-100;i<=100;i++) { x=a*i*i*i+b*i*i+c*i+d; i++; y=a*i*i*i+b*i*i+c*i+d; i--; if(x==0) { printf("%.2lf ",i); continue; } if(x*y<0) { l=i; r=i+1; while(l<r-0.0001) { m=(l+r)/2; x=a*l*l*l+b*l*l+c*l+d; y=a*r*r*r+b*r*r+c*r+d; z=a*m*m*m+b*m*m+c*m+d; if(z==0) break; if(x*z>0) l=m+0.00001; else if(y*z>0) r=m-0.00001; } printf("%.2lf ",m); } } return 0; } -
0
注意：精度M 二分left=mid+N
M应该远远大于N
#include <cstdio>
#define M 0.00001double p1,p2,p3,p4;
double f(double x){
return p1*x*x*x+p2*x*x+p3*x+p4;
}double search(double l,double r){
double mid,fl,fr,fm;
while(l<r){
mid=(l+r)/2;
fl=f(l),fr=f(r),fm=f(mid);
if(fm<0.0001&&fm>-0.0001)
return mid;
if(fl*fm<0.00000001)
r=mid-0.0000001;
else
l=mid+0.0000001;
}
}int main(){
scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);
for(int i=-100;i<=99;i++){
double ans=-666;
if(f(i)>-M&&f(i)<M)
ans=i;
else if(f(i+1)>-M&&f(i+1)<M)
ans=i+1,i=i+1;
else if(f(i)*f(i+1)<0)
ans=search(i,i+1);
if(ans!=-666)
printf("%.2lf ",ans);
}
return 0;
} -
0
二分 端点特殊处理
#include <cstdio>
#define ACR 0.000000001double a,b,c,d,l,r,p;
double f(double x){
return a*x*x*x+b*x*x+c*x+d;
}double fabs(double x){
return x>0?x:-x;
}int equal(double a,double b){
return fabs(a-b)<ACR;
}int main(){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
l=-100;
for(l=-100.0;l<=99.0;l+=1.0){
r=l+1;
double M=f(l)*f(r);
if(M>0)
continue;
double pl=l,pr=r,pm;
if(equal(f(l),0)){
printf("%.2lf ",l);
continue;
}
if(equal(f(r),0)){
l++;
printf("%.2lf ",r);
continue;
}
while(1){
pm=(pl+pr)/2;
if(f(pl)*f(pm)<=0)
pr=pm;
else
pl=pm;
if(equal(f(pm),0)){
printf("%.2lf ",pm);
break;
}
}
}
return 0;
} -
0
pascal 枚举！！！
pascal
const
min=-100.0;
max=100.0;
eps=0.001;
var
num:longint;
a,b,c,d,i:double;
function f(x:double):double;
begin
exit(a*x*x*x+b*x*x+c*x+d);
end;
function isroot(x:double):boolean;
begin
exit(abs(f(x))<eps);
end;
begin
readln(a,b,c,d);
num:=0;
i:=min;
repeat
if isroot(i)
then
begin
write(i:0:2,' ');
num:=num+1;
i:=i+1;
end
else
i:=i+eps;
until (num>=3) or (i>max);
writeln;
end.
-
0
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;float ans[5];
float a,b,c,d;
int n=0;float f(float x)
{
return ((a*x+b)*x+c)*x+d;
}void solve(float l,float r)
{
if(f(l)*f(r)>0&&(((r-l)<1)||n>=2))//注意这里n>=2啊，不要像我一样作死了半天写成了n>=1。
return;
float mid=(l+r)/2;if(f(mid)<=1e-4 && f(mid)>=-1e-4)
{ans[n++]=mid;
return;
}
solve(l,mid),solve(mid,r);
}int main()
{
cin>>a>>b>>c>>d;
solve(-100,100);
printf("%.2lf %.2lf %.2lf",ans[0],ans[1],ans[2]);
return 0;
} -
0
1667629529 LV 6 @ 2016-07-22 18:00:41
暴力枚举答案 用 double
-
0
/*******************************************二分法*******************************************************/
c++
#include<iostream>
#include<cstdio>
using namespace std;
double a,b,c,d;
int top=1;
double x[5]={0};
double fun(double s){
return a*s*s*s+b*s*s+c*s+d;
}
void search(double s,double t){
if((t-s)<0.001){
x[top++]=s;
return;
}
if(fun(s)*fun(t)<0){
double mid=(s+t)/2;
if(fun(s)*fun(mid)==0){
x[top++]=mid;
return;
}
else if(fun(s)*fun(mid)<0){
search(s,mid);
}
else if(fun(mid)*fun(t)<0){
search(mid,t);
}
}
}
int main(){
int i;
cin>>a>>b>>c>>d;
for(i=-100;i<=100;i++){
if(top==4) break;
if(fun(i)*fun(i+1)<0){
if(fun(i)*fun(i+0.5)<0){
search(i,i+0.5);
}
else if(fun(i+0.5)*fun(i+1)<0){
search(i+0.5,i+1);
}
}
else if(fun(i)*fun(i+1)==0){
if(fun(i)==0){
x[top++]=i;
}
}
}
for(i=1;i<=3;i++){
printf("%.2f ",x[i]);
}
return 0;
}
-
0
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
double a,b,c,d;
double f(double s)
{
return a*s*s*s+b*s*s+c*s+d;
}
int main()
{
int x,x0,biao=3;
double m,i,j;
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
for(x=-100;x<11;x++)
{
x0=x+1;
i=(double)x;
j=(double)(x+1);
if(f(i)==0)
{
printf("%.2lf ",i);
biao--;
}
else
{
if(f(i)*f(j)<0)
while(1)
{
m=(i+j)/2;
if(f(m)==0)
{
printf("%.2lf ",m);
biao--;
break;
}
if(f(i)*f(m)<0) j=m;
if(f(j)*f(m)<0)
{
i=j;
j=m;
}
if(abs(i-j)<=0.001)
{
printf("%.2lf ",m);
biao--;
break;
}
}
}
if(biao==0) break;
}
return 0;
}
请问为什么过不了 -
0
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> using namespace std; int a,b,c,d; double f(double x); int jie(); int main() { cin>>a>>b>>c>>d; jie(); return 0; } double f(double x) { return(x*x*x*a+x*x*b+x*c+d); } int jie() { int x; double xx; double x1,x2; for(x=-100;x<=100;x++) { x1=x;x2=x+1; if(f(x1)==0)printf("%.2f ", x1); else if(f(x1)*f(x2)<0) { while(x2-x1>=0.001) { xx=(x1+x2)/2; if(f(x1)*f(xx)<=0)x2=xx; else x1=xx; } printf("%.2f ", x1); } } cout<<endl; }为什么是错的，大神求解，拜托，十分感谢！
-
wuwangmao @ 2016-07-22 13:47:26
如果已经找到解在1~2间，取中点1.5刚好是解，为什么还要继续，这样反而不精确
-
PowderHan
LV 10
@ 2017-05-08 08:02:08
