UVA 10428 - The Roots(牛顿迭代法)

UVA 10428 - The Roots

题意：给定一个一元多次方程组，要求求出全部根

思路：利用牛顿迭代法 xn+1=xn−f(xn)/f′(xn)，不断迭代就能求出较为精确的值，然后因为有的方程可能有多解，每次解得一个X后，就把原式子除以(x
- X)，这个是肯定能整除的。把方程降阶然后继续用牛顿迭代法直到求出全部解

代码：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = 10;

int n;

double a[N];

double cal(double *f, double x, int n) {

    double ans = 0;

    for (int i = 0; i <= n; i++)

	ans += f[i] * pow(x, i);

    return ans;

}

double newton(double *f, int n) {

    double fd[N];

    for (int i = 0; i < n; i++)

	fd[i] = f[i + 1] * (i + 1);

    double x = -25.0;

    for (int i = 0; i < 100; i++)

	x = x - cal(f, x, n) / cal(fd, x, n - 1);

    return x;

}

void tra(double *f, double x, int n) {

    f[n + 1] = 0;

    for (int i = n; i > 0; i--)

	f[i] = f[i + 1] * x + f[i];

    for (int i = 0; i < n; i++)

	f[i] = f[i + 1];

}

void solve() {

    for (int i = 0; i < n; i++) {

	double x = newton(a, n - i);

	printf(" %.4lf", x);

	tra(a, x, n - i);

    }

}

int main() {

    int cas = 0;

    while (~scanf("%d", &n) && n) {

	for (int i = n; i >= 0; i--)

	    scanf("%lf", &a[i]);

	printf("Equation %d:", ++cas);

	solve();

	printf("\n");

    }

    return 0;

}