[UVA] 10428 - The Roots

題目連結
這題ac uva rank 1耶真是感動到快暴動了










程式碼:
/* 題目: UVa 10428 - The Roots
 * Language: C++
 * Created on: 2016年7月12日
 *   Author: hanting
 */
#include <iostream>
#include <cstring> // memset
#include <iomanip> // setprecision
#include <cmath> // fabs
#include <algorithm> // sort
#include <vector>
#include <cstdio>
using namespace std;
double a[6];
double f(double x) // 高效率求一元多次多項式的值
{
    double result = a[5];
    for(int i = 4; i >= 0; i--)
    {
        result = result * x + a[i];
    }
    return result;
}
double f1(double x)
{
    double result = a[5]*5;
    for(int i = 4; i > 0; i--)
    {
        result = result * x + a[i]*i;
    }
    return result;
}
double newtonsMethod(double x0)
{
    double x1 = x0;
    int cnt = 0;
    do
    {
        if(++cnt == 100) break;
        x0 = x1;
        if(fabs(f(x0)) < 1e-10) return x0;
        x1 = x0 - f(x0)/f1(x0);
    }
    while(fabs(x1 - x0) > 1e-10);
    return x1;
}
void PolynomialDivision(double b, double c) // f div (bx+c)
{
    for(int i = 5; i > 0; i--)
    {
        a[i-1] -= a[i] / b * c;
        a[i] /= b;
    }
    for(int i = 0; i < 5; i++)
    {
        a[i] = a[i+1];
    }
    a[5] = 0;
}
void findRoot(vector<double> &root, int N)
{
    double oneRoot;
    while(root.size() < N)
    {
        oneRoot = newtonsMethod(0);
        root.push_back(oneRoot);
        PolynomialDivision(1, -oneRoot);
    }
}
int main()
{
    int N;
    int caseN = 1;
    while(/*cin >> N*/scanf("%d", &N) == 1 and N)
    {
        memset(a, 0, sizeof(a));
        for(int i = N; i >= 0; i--)
        {
            //cin >> a[i];
            scanf("%lf", a+i);
        }
        vector<double> root;
        findRoot(root, N);
        sort(root.begin(), root.end());
        printf("Equation %d:", caseN++);
        //cout << "Equation " << caseN++ << ":" ;
        for(int i = 0; i < N; i++)
        {
            printf(" %.4lf", root[i]);
            //cout << " " << fixed << setprecision(4) << root[i];
        }
        printf("\n");
        //cout << endl;
    }
    return 0;
}