Koios1143的筆記

UVa 10341

發表於 分類於

UVa 10341

題目

http://domen111.github.io/UVa-Easy-Viewer/?10341

今天有一個算式 $p * e^{-x} + q * sin(x) + r * cos(x) + s * tan(x) + t * x^{2} + u = 0$

已知 $0 \leq x \leq 1$，給定 $p, q, r, s, t, u$，求 $x$

$0 \leq p, r \leq 20 \
-20 \leq q, s, t \leq 0$

想法

首先先來觀察一下算式，將算式中的每個部份拆分出來

我們只討論 $x$ 所在的的範圍 $0 \leq x \leq 1$

  • $e^{-x}$ 為遞減函數
  • $sin(x)$ 為遞增函數
  • $cos(x)$ 為遞減函數
  • $tan(x)$ 為遞增函數
  • $x^{2}$ 為遞增函數

接下來把係數也考慮進去

  • $p * e^{-x}$ 為遞減函數
  • $q * sin(x)$ 為遞減函數
  • $r * cos(x)$ 為遞減函數
  • $s * tan(x)$ 為遞減函數
  • $t * x^{2}$ 為遞減函數

由此可知， $p * e^{-x} + q * sin(x) + r * cos(x) + s * tan(x) + t * x^{2} + u$ 是遞減函數，令這個函數為 $f(x)$

知道這個函數是呈現遞減的狀態，我們要求其解就想到利用二分搜

透過二分搜，我們可以枚舉 $x$，並且有三種情況

  • $f(x) = 0$
    x 就是答案
  • $f(x) > 0$
    因為函數是遞減，當答案大於 0 則應該要調整邊界向右移動
  • $f(x) < 0$
    因為函數是遞減，當答案大於 0 則應該要調整邊界向左移動

但是程式會有浮點數的誤差存在，所以很難判斷到底應不應該繼續往下尋找答案

但是因為 $f(x)$ 是連續函數，我們可以用勘根定理找到是否存在解，只要除去不存在解的情況，我們就可以放心地往下繼續找答案

除去無解的情況，接下來找答案就很快了

但是浮點數誤差一定要小心處理

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//By Koios1143
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
double p, q, r, s, t, u, esp=1e-9;

double abs2(double x){
	// 因為沒有針對 double 的 abs 存在，自己寫一個
	return (x<0 ? -x : x);
}

double ans(double x){
	// 直接回傳 x 帶入算式的結果
	return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}

double search(double l, double r){
	double mid, ret=1;
	// 只要答案還在誤差範圍內就放心搜尋
	while(abs2(ret) > esp){
		mid = (l+r)/2.0;
		ret = ans(mid);
		if(ret < 0) r = mid;
		else l = mid;
	}
	return mid;
}

int main(){
	while(cin>>p>>q>>r>>s>>t>>u){
		// 當左右邊界的值帶入後答案相乘大於 0 則不存在解 (勘根定理)
		if(ans(1) * ans(0) > 0) cout<<"No solution\n";
		else{
			double x = search(0, 1+esp);
			cout<<fixed<<setprecision(4)<<x<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(1)$

每筆測資找答案的時間複雜度為 $O(logN)$ $N = 10^{9}$

每筆測資總時間複雜度約為 $O(logN)$