Решение уравнения, представляющего монотонную функцию

Даны коэффициенты уравнения a₀*xⁿ + a₁*x^n-1 + ... + a_n = 0. Известно, что данный многочлен представляет собой монотонную функцию.
Найти его корни.

    Так как функция монотонна, то либо корень уравнения один, либо их нет. Другими словами, нам надо найти точку пересечения графика функции с осью абсцисс. Будем искать её с помощью бинарного поиска.

    Асимптотика O(NlogL), где N - количество коэффициентов в уравнении, L - количество чисел, среди которых ведётся поиск.

Листинг C++

#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

#define forn(i, n) for ((i) = 0; (i) < (n); ++ (i))
#define forab(i, a, b) for ((i) = (a); (i) <= (b); ++ (i))
#define forv(it, v) for ((it) = (v).begin (); (it) != (v).end (); ++ (it))
#define Forn(i, n) for (int i = 0; i < (n); ++ i)
#define Forab(i, a, b) for (int i = (a); i <= (b); ++ i)

const double eps = 1e-10;
#define eq(a, b) (abs ((a) - (b)) <= eps)

// схема Горнера
int sign_gorner_polynom (list < double > & p, double x, double eps = :: eps)
{
    double s = 0.000;
    list < double > :: iterator it;
    forv (it, p)
        s = s * x + (*it);
    if (eq (s, 0))
        return 0;
    if (s < 0)
        return - 1;
    return 1;
}

// бинарный поиск
int bin_equation (list < double > & p, double left, double right, double & x)
{
    int sL = sign_gorner_polynom (p, left);
    int sR = sign_gorner_polynom (p, right);

    if (eq (sL, 0))
    {
        x = left;
        return 1;
    }
    if (eq (sR, 0))
    {
        x = right;
        return 1;
    }
    if (sL == sR)
        return 0;

    while (right - left > eps)
    {
        double mid = (right + left) * 0.500;
        int sM = sign_gorner_polynom (p, mid);

        if (sM == sL)
            left = mid;
        else
            right = mid;
    }

    x = (left + right) * 0.500;
    return 1;
}

18:34
14.08.2009

По всем вопросам обращаться: rumterg@gmail.com