題目連結
這題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;
}
