UVa 10341 – Solve It【经典二分，单调性求解】

工程师炳钛技术 2022年11月9日

0 收藏 624 点赞 4,615 浏览 1368 个字

原题：

Solve the equation:
p*e^–x+ q*sin(x) + r*cos(x) + s*tan(x) + t*x² + u = 0
where 0 <= x <= 1.

Input

Input consists of multiple test cases and terminated by an EOF. Each test case consists of 6 integers in a single line: p, q, r, s, t and u(where 0 <= p,r <= 20 and -20 <= q,s,t <=
0). There will be maximum 2100 lines in the input file.

Output

For each set of input, there should be a line containing the value of x, correct upto 4 decimal places, or the string “No solution”, whichever is applicable.

Sample Input

0 0 0 0 -2 1

1 0 0 0 -1 2

1 -1 1 -1 -1 1

Sample Output

0.7071

No solution

0.7554

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1282分析：非线性方程求根问题， LRJ《算法入门经典》p150有类似的问题。要求的跟是0~1之间，而且这个方程是单调递减的，所以可以用二分来求根。实在不行的话你也可以这样做，用高中求导的方法进行求解，对函数进行求一阶导数，易得出该函数是个单调的函数，所以就可以采用二分求解！二分怎么做呢，我们看，如果是直接去找点，或许问题会变得非常复杂，我们可以换种思路考虑，这个单调函数一定会在某一点使得f(x)=0，所以我们可以去找f(l)*f(mid)的值大于0还是小于0的操作，这是研究单调函数常用的方法，于是这题就变得非常简单了二分判断条件为f(l)*f(mid)>0?l=mid:r=mid;然后你就能AC了？不，此题还有坑点啊！此题坑点在循环输入，还有就是精度问题，注意这两点就AC了！下面给出AC代码：

 #include <bits/stdc++.h>
 using namespace std;
 const double eps=1e-;
 double p,q,r,s,t,u;
 double gcd(double x)
 {
     return p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*pow(x,)+u;
 }
 int main()
 {
     while(scanf("%lf%lf%lf%lf%lf%lf",&p,&q,&r,&s,&t,&u)!=EOF)
     {
         double l=0.0,r=1.0,mid;
         if(gcd(l)*gcd(r)>)
         {
         printf("No solution\n");
         continue;
         }
     while(l+eps<=r)
     {
         mid=(l+r)/;
         if(gcd(l)*gcd(mid)>)
             l=mid;
         else r=mid;
     }
       printf("%.4lf\n",mid);
     }
     return ;
 }