UVa 498: Polly the Polynomial | MathBlog

UVa 498: Polly the Polynomial | MathBlog
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=439
Your program should accept an even number of lines of text. Each pair of lines will represent one problem. The first line will contain a list of integers {  } which represent a set of coefficients to a polynomial expression. The order of the polynomial is n. The coefficients should be paired with the terms of the polynomial in the following manner:


The second line of text represents a sequence of values for x, {  }.

Output

For each pair of lines, your program should evaluate the polynomial for all the values of x (  through  ) and output the resulting values on a single line.

Sample Input

-2
5 0 1 6
1 -1
7 6 -1

Sample Output

-2 -2 -2 -2
6 5 -2

http://www.mathblog.dk/uva-498-polly-the-polynomial/

// the Polynomial class

public class Polynomial {

    // the coefficients of the polynomial,

    // where the i-th element is the coefficient of x^i

    private int[] coefficients;

    // the degree of the polynomial

    private int degree;

    // the constructor for a polynomial of degree 'deg'

    public Polynomial(int deg) {

        degree = deg;

        coefficients = new int[deg + 1];

    }

    // return the degree of the polynomial

    public int getDegree() {

        return degree;

    }

    // get the coefficient for x^i

    public int get(int i) {

        return coefficients[i];

    }

    // set the coefficient for x^i

    public void set(int i, int value) {

        coefficients[i] = value;

    }

}

// evaluate the polynomial at 'x'

public int evaluate(int x) {

    // keep a running sum

    int result = 0;

    // loop through each coefficient of the polynomial

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

        // add (coefficient at x^i) * x^i to the running sum

        result += get(i) * (int)Math.pow(x, i);

    }

    // return the running sum

    return result;

}

This code is alright, but we can still improve it by using Horner’s method. Let’s take a look at the polynomial we had before:

If we factor one  from each term in the polynomial which has at least one  we get:

Then we can keep on doing that in the inner-most polynomial and get:

In our new evaluate method, we’re going to do exactly the reverse of what we just did.

public int evaluate(int x) {

    // keep a running sum

    int result = 0;

    // loop through each coefficient of the polynomial,

    // starting at the one at the highest degree and going down

    for (int i = getDegree(); i >= 0; i--) {

        // multiply by x and then add the current coefficient

        result = result * x + get(i);

    }

    // return the running sum

    return result;

}

public void run(Scanner in, PrintWriter out) {

    // while there are still input cases left

    while (in.hasNextInt()) {

        // read the coefficients with our handy readLineToIntegers method

        List<Integer> coefficients = readLineToIntegers(in);

        // create a Polynomial of degree coefficients.size() - 1

        Polynomial p = new Polynomial(coefficients.size() - 1);

        // loop through the coefficients

        for (int i = 0; i < coefficients.size(); i++) {

            // and change the appropriate coefficient of the polynomial

            p.set(coefficients.size() - i - 1, coefficients.get(i));

        }

        // read the list of x's

        List<Integer> xs = readLineToIntegers(in);

        // loop through the x's

        for (int i = 0; i < xs.size(); i++) {

            // print a space between to consecutive outputs

            if (i != 0) out.print(" ");

            // print the result of the polynomial evaluated at the current x

            out.print(p.evaluate(xs.get(i)));

        }

        // print an endline after each test case

        out.println();

    }

}

public static void main(String[] args) throws Exception {

    Scanner in = new Scanner(System.in);

    PrintWriter out = new PrintWriter(System.out, true);

    new Main().run(in, out);

}

    char s[1001];

    while(gets(s)){

        int c[100], x[100], ct = -1, xt = -1;

        istringstream input(s);

        while(input >> c[++ct]);

        gets(s);

        istringstream read(s);

        while(read >> x[++xt]);

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

            int sum = 0;

            for(int j = 0; j < ct; j++)

                sum += c[j]*(int)pow(x[i], ct-j-1);

            if(i)

                printf(" ");

            printf("%d", sum);

        }

        puts("");

    }

Read full article from UVa 498: Polly the Polynomial | MathBlog