Question surface:

Tangible, such as a x^3 + b x^2 + c x + d = 0. The coefficients of each item in the equation (a, B, C and D are real numbers) are given, and it is agreed that the equation has three different real roots (the range of roots is - 100 to 100), and the absolute value of the difference between roots is ≥ 1. It is required to output the three real roots in the same line from small to large (there is a space between the roots) and accurate to 2 digits after the decimal point.

Get this question, because the range of root - 100 to 100 is relatively small

So my first thought is:

#include <bits/stdc++.h>
using namespace std;
double a, b, c, d;
int main() {
	cin >> a >> b >> c >> d;
	for (double i = -100; i <= 100; i += 0.001) { //Enumeration & & Card precision
		if (fabs(i * i * i * a + i * i * b + i * c+d) < 0.0001) { //If the conditions are met
			printf("%.2lf ",i);//output
		}
	}
	return 0;
}

This is a violent algorithm, very simple

The complexity is around O (200000), very fast

However, as the author of the question, the main knowledge point you may want to test is two points

What remains unchanged is the first layer of circulation

However, the increment of i can become 1

That is:

for (double i = -100; i < 100; i++)

Now the value of i is an integer

We can also write a check function for indirect binary judgment

By question:

double check(double x) { return x * x * x * a + x * x * b + x * c + d; }

First, if you have an integer root

We can get the answer directly in i integer enumeration:

if (check(i) == 0) {
    printf("%.2lf ", i);
}

What if the root is a decimal

It's time for the dichotomy to come out

1. We need to determine when there is a decimal root

When we enumerate to any i, if check (i) * check (i + 1) < 0

Then it means that one positive and one negative in check(i) and check(i + 1)

I don't know why. I suggest you go home and learn math

For our check function, it is very easy to conclude that when the value of a b c d is determined, the greater the value of x, the greater the value of the original expression

When the value of the expression is 0, the equation holds

In other words, there must be a decimal root between the two integers i and (i+1)

The premise must be check (I) * check (I + 1) < 0

Then we can determine the left endpoint and the right endpoint

I.e. l = i, r = i + 1

2. Under what circumstances do we need to jump out of the cycle of dichotomy and narrowing the scope

The accuracy range of this problem is about 0.001

In other words, when the distance between L and R is < = 0.001, we can approximately regard them as a point

(only for this question)

code:

while (r - l > 0.001)

3. How can we narrow the scope

First, we need double mid;

This mid is the midpoint between l and r

That is: mid = (l + r) / 2 * image: l mid............ r

(the dots in the figure can be understood as many decimals, each of which may be the answer)

The following is the code of the binary process:

            while (r - l > 0.001) { //Range
                mid = (l + r) / 2; //Take the intermediate value
                if (check(mid) * check(l) < 0) { //If the intermediate value is too large
                    r = mid; //Narrow the right range
                } else {
                    l = mid;//Narrow the left range
                }
            }

Let me compare the running speed of the two codes:

29 ms and 76 MS

Although it is basically of the same level, the gap will be widened as the data range is large

Full code:

#pragma GCC optimize(3)
#include <iostream>
#include <cstdio>
using namespace std;
double a, b, c, d;
double l, r, mid;
double check(double x) { return x * x * x * a + x * x * b + x * c + d; }
int main() {
    cin >> a >> b >> c >> d;
    for (double i = -100; i < 100; i++) {
        if (check(i) == 0) {
            printf("%.2lf ", i);
            continue;
        }
        if (check(i) * check(i + 1) < 0) {
            l = i, r = i + 1;
            while (r - l > 0.001) {
                mid = (l + r) / 2;
                if (check(mid) * check(l) < 0) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            printf("%.2lf ", mid);
        }
    }
    return 0;
}