luogu【P1024 一元三次方程求解】题解
题目描述
有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。
提示:记方程f(x)=0,若存在2个数x1和x2,且x1<x2,f(x1)*f(x2)<0,则在(x1,x2)之间一定有一个根。
输入输出格式
输入格式:
一行,4个实数A,B,C,D。
输出格式:
一行,三个实根,并精确到小数点后2位。
输入输出样例
1 -5 -4 20
-2.00 2.00 5.00
看到大家没人打通解,那么我来发一波~~~
蒟蒻的凝视~~~
可以先看一下此题的强化版:解方程 求解一个K次函数,那么我们只需从函数图像的各个顶点二分搜索一下就可以了。 比如说如下函数:
我们只需在-∞到第一个顶点中搜索解,再在第一个顶点到第二个顶点中搜索……直到第n个顶点到∞中搜索解。
所以,我们只需找到此函数顶点的x值就可以了。方法很简单,只需求导,再解一下求导后的方程。
我们可以知道,对于一个
∑i=0->n aix^i = 0
的方程,n次求导后总会变成一次函数。之后再解方程,就可以一步一步把解给求出来。
代码比较奇怪,我打了一个class,希望对大家有用。
#define pb push_back
using namespace std;
class fun{
private:
int n;
vector <double> num;
public:
fun ()
{
n=0;
num.clear();
}
int size()
{
return n;
}
vector <double> getarray()
{
return num;
}
void insert(vector <double> p)
{
num=p;
n=p.size();
}
void mem(int p,double e,...)
{
double *q=&e;
n=p;
for (int i=1;i<=n;i++)
{
num.pb(*q);
q++;
}
}
double operator ()(double x)
{
double ans=0;
double xt =1;
for (int i=0;i<=n-1;i++)
{
ans+=xt*num[i];
xt*=x;
}
return ans;
}
void print()
{
for (int i=0;i<n;i++)
{
if (i==0) cout << num[i];
else
if (num[i] != 0)
{
if (num[i]<0)
cout << num[i] << "x^"<<i;
else cout << "+" << num[i] << "x^"<<i;
}
}
}
fun operator !()
{
fun H;
H.n=n-1;
for (int i=0;i<H.n;i++)
{
H.num.pb((i+1)*num[i+1]);
}
return H;
}
double get_root(double p,double q)
{
fun f;
f.insert(num);
if (f(p)*f(q)>0) return -100000000;
double mid = (p+q)2;
while (p+0.000001<q)
{
if (f(p)*f(mid)<=0) q=mid;
else p=mid;
mid=(p+q)2;
}
return mid;
}
double operator [] (int p)
{
return num[p];
}
};
vector <double> get_all_answer(double s,double e,fun f)
{
vector <double> ret;
vector <double> qw;
qw = f.getarray();
ret.clear();
if (qw.size()<=2)
{
ret.pb(-qw[0]qw[1]);
return ret;
}
vector <double> ans_list = get_all_answer(s,e,(!f));
if (ans_list.size()==0)
{
if (f.get_root(s,e)>-99999999) ret.pb(f.get_root(s,e));
return ret;
}
if (f.get_root(s,ans_list[0])>-99999999) ret.pb(f.get_root(s,ans_list[0]));
for (int i=0;i<ans_list.size()-1;i++)
{
if (f.get_root(ans_list[i],ans_list[i+1])>-99999999)
ret.pb(f.get_root(ans_list[i],ans_list[i+1]));
}
if (f.get_root(ans_list[ans_list.size()-1],e)>-99999999)
ret.pb(f.get_root(ans_list[ans_list.size()-1],e));
vector <double> RET;
if (ret.size()==0) return ret;
RET.pb(ret[0]);
for (int i=1;i<ret.size();i++)
{
if (abs(ret[i]-ret[i-1])>0.00001)
RET.pb(ret[i]);
}
return RET;
}
int main()
{
fun f;
vector <double> g;
int n;
cin >> n;
n++;
for (int i=1;i<=n;i++)
{
double x;
cin >> x;
g.pb(x);
}
f.insert(g);
double s,e;
cin >> s >> e;
vector <double> ans;
ans = get_all_answer(s,e,f);
for (int i=0;i<ans.size();i++)
printf("%.5lf ",ans[i]);
}
最新文章
- .NET面试题系列[14] - LINQ to SQL与IQueryable
- AndRodi Strudio中的按钮时件
- SharpDX之Direct2D教程II——加载位图文件和保存位图文件
- CentOS 7 下引导 Windows7 启动
- ClassLoader 机制
- 排序算法之快速排序(java实现)
- 设计模式一:关于C++写观察者模式的一些收获
- 【模板】AC自动机(加强版)
- c/c++ open函数的阻塞和非阻塞
- anaconda安装opencv(python)
- 2017-12-15python全栈9期第二天第七节之x or y ,x 为 非 0时,则返回x
- Vue-接口跨域请求调试proxyTable
- text/css什麼意思
- Composer 安装和使用
- asp.net core 微信扫码支付(扫码支付,H5支付,公众号支付,app支付)之1
- CentOS下安装Python3
- Mac 安装任何来源的文件
- Python 进制转换、位运算
- php-fpm 重启 nginx单独配置 重启
- 你对position的了解有多少?
热门文章
- Android Studio编译报错Could not reserve enough space for 2097152KB object heap解决方法
- 【ABAP系列】SAP ABAP DOI展示EXCEL或WORD
- Mysql-使用xtrabackup添加Slave
- [Git] 020 stash —— Git 中的”皮姆粒子“
- [19/05/27-星期一] JavaScript_ 条件语句(if语句)和循环语句(while 、for、do-while)
- JAVA获取当前系统时间System.currentTimeMillis()以及获取运行时间
- JS案例经验1
- 区间gcd
- 只使用非递归的mutex
- 通过编写串口助手工具学习MFC过程——(四)添加ComboBox组合框