#UVa:10341-Solve It

灆洢 2016-04-20 12:03:18

首先,由於要計算的函數先拆解每一項來看:

  • \(e^{-x}\):在\(0 \leq x \leq 1\)區間內為遞減函數
  • \(\sin{x}\):在\(0 \leq x \leq 1\)區間內為遞增函數
  • \(\cos{x}\):在\(0 \leq x \leq 1\)區間內為遞減函數
  • \(\tan{x}\):在\(0 \leq x \leq 1\)區間內為遞增函數
  • \(x^{2}\):在\(0 \leq x \leq 1\)區間內為遞增函數

接著配合係數限制:

  • \(p \times e^{-x}\):在\(0 \leq p \leq 20\)區間內為遞減函數
  • \(q \times \sin{x}\):在\(-20 \leq q \leq 0\)區間內,由於係數為負,故倒向為遞減函數。
  • \(r \times \cos{x}\):在\(0 \leq r \leq 20\)區間內為遞減函數
  • \(s \times \tan{x}\):在\(-20 \leq s \leq 0\)區間內,由於係數為負,故倒向為遞減函數。
  • \(t \times x^{2}\):在\(-20 \leq t \leq 0\)區間內,由於係數為負,故倒向為遞減函數。

由於五項皆為遞減函數,和亦為遞減函數。利用遞減函數的性質與二分搜尋法即可找到解。

P.S. 小心兩浮點數之間不能直接做等於運算,會有誤差,必須算兩數相減小於某個可容忍的誤差值去判斷相等。

C++(0.010)

/*******************************************************/
/* UVa 10341 Solve It                                  */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

bool isEqual(double a, double b){
  return (a - b) < 1e-9 && (a - b) > -1e-9;
}

struct Formula{
  double p;
  double q;
  double r;
  double s;
  double t;
  double u;

  double calculate(double x){
    return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
  }
};

int main(){
  Formula f;
  while( scanf("%lf%lf%lf%lf%lf%lf", &(f.p), &(f.q), &(f.r), &(f.s), &(f.t), &(f.u)) != EOF){
    double lowerBound = 0, upperBound = 1;
    double lowerValue = f.calculate(lowerBound), upperValue = f.calculate(upperBound);
    if( isEqual(lowerValue, 0) ){
      printf("%.4lf\n", lowerBound);
      continue;
    }

    if( isEqual(upperValue, 0) ){
      printf("%.4lf\n", upperBound);
      continue;
    }

    if( lowerValue * upperValue > 0 ){
      printf("No solution\n");
      continue;
    }

    double mid;
    double midValue;
    do{
      mid = (lowerBound + upperBound) / 2;
      midValue = f.calculate(mid);

      if( midValue < 0 ){
        upperBound = mid;
      }
      else {
        lowerBound = mid;
      }
    } while( !isEqual(midValue, 0) );

    printf("%.4lf\n", mid);

  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料