UVA10341 Solve It 题解
UVA10341 Solve It
题目描述
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1282
输入格式
输出格式
输入输出样例 #1
输入 #1
0 0 0 0 -2 1 1 0 0 0 -1 2 1 -1 1 -1 -1 1输出 #1
0.7071 No solution 0.7554Solution
1. 大致题意
- 求方程p exp ( − x ) + q sin ( x ) + r cos ( x ) + s tan ( x ) + t x 2 + u = 0 p\exp(-x)+q\sin(x)+r\cos(x)+s\tan(x)+tx^2+u=0pexp(−x)+qsin(x)+rcos(x)+stan(x)+tx2+u=0在区间[ 0 , 1 ] [0,1][0,1]上的解，无解输出No Solution \texttt{No Solution}No Solution。
- 输入包含多组不同的( p , q , r , s , t , u ) (p,q,r,s,t,u)(p,q,r,s,t,u)，针对每一组数据求解该方程。
2. 分析
解决此类方程的通用方法有两种，一种是牛顿法，一种是二分法。
设函数
f ( x ) = p exp ( − x ) + q sin ( x ) + r cos ( x ) + s tan ( x ) + t x 2 + u f(x)=p\exp(-x)+q\sin(x)+r\cos(x)+s\tan(x)+tx^2+uf(x)=pexp(−x)+qsin(x)+rcos(x)+stan(x)+tx2+u
则导函数
f ′ ( x ) = − p exp ( − x ) + q cos ( x ) − r sin ( x ) + s cos 2 ( x ) + 2 t x f'(x)=-p\exp(-x)+q\cos(x)-r\sin(x)+\dfrac{s}{\cos^2(x)}+2txf′(x)=−pexp(−x)+qcos(x)−rsin(x)+cos2(x)s+2tx
根据题意，由于p , r p,rp,r为正，q , s , t q,s,tq,s,t为负，x xx的范围为[ 0 , 1 ] [0,1][0,1]，因此容易看出f ′ ( x ) ≤ 0 f'(x)\le0f′(x)≤0在区间[ 0 , 1 ] [0,1][0,1]恒成立，也就是说f ( x ) f(x)f(x)是区间[ 0 , 1 ] [0,1][0,1]的单调函数。
在具有单调性（单调递减）的情况下：
- 判断无解只需要看端点值，如果f ( 0 ) < 0 f(0)<0f(0)<0或f ( 1 ) > 0 f(1)>0f(1)>0即为无解。
- 可以直接使用二分求解，使用 Desmos 绘制得到的函数的图像如下。
考虑到所求的函数在区间( − ∞ , + ∞ ) (-\infty,+\infty)(−∞,+∞)不连续，存在间断点并且方程可能存在区间[ 0 , 1 ] [0,1][0,1]以外的解（参考下图）因此不推荐使用牛顿法求解。
3. 代码
#include<bits/stdc++.h>doublep,q,r,s,t,u,eps=1e-8,le,re;doublef(doublex){returnp*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*pow(x,2.)+u;}voidkernel(void){inti=1;if(scanf("%lf%lf%lf%lf%lf%lf",&p,&q,&r,&s,&t,&u)==EOF)exit(0);if(f(1)>0||f(0)<0)printf("No solution\n");else{le=0.;re=1.;while(re-le>=eps)f((le+re)/2.)>=0.?le=(le+re)/2.:re=(le+re)/2.;printf("%.4lf\n",le);}return;}intmain(){while(1)kernel();}