二分答案——一進制三次方程求解(洛谷 P1024)

題目選自洛谷P1024

 考慮使用二分的方法求解，引出零點存在性定理：若f(a) * f(b) < 0 (a<b)，則在(a,b)上 至少存在一個解。

一個定義在實數區間上的二分呼之欲出：如果終點的函數值和某點的正負性相同，那麼零點一定在中點的另一側。

注意：函數的單調性 和 “條件”的單調性無關

是以我們從最左邊開始枚舉每一個數，把這一個數當做[a,a+1]的一個區間，來進行求解

如果端點是解，那麼直接輸出即可，

否則 如果滿足零點定理，那麼就把這個區間再細分求解，

輸出L即可。

題目描述

有形如：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

1 -5 -4 20
      

輸出樣例 1

-2.00 2.00 5.00      

 解題代碼：

#include<stdio.h>
#include<iostream>
using namespace std;
double a,b,c,d;
double f(double x){
	return (a*x*x*x + b*x*x + c*x +d);
}
int main(){
	cin>>a>>b>>c>>d;
	for(int i=-100;i<=100;i++){ //一個點一個點的試，看是否可能存在根，若存在 則細分求解
		double L = i, R = i + 1,mid;
		if(fabs(f(L)) < 1e-4)  //左端點是根
			printf("%.2lf ",L);
		else if(fabs(f(R)) < 1e-4)  //右端點是根,這裡跳過的原因是放置得到重複解
			continue;
		else if(f(L) * f(R) < 0){   //有根
			while(R - L >1e-4){
				mid = (L + R) / 2;
				if(f(mid) * f(R) > 0)
					R = mid;
				else L = mid;
			}
			printf("%.2lf ",L);
		}
	}
	return 0;
}