Programming Team:  Practice Contest, 12-Feb-05 (Matrices)
Mt Lebanon HS 2004-5
David Kosbie

Link to the Programming Team Home Page.

Q1:  Gaussian Elimination (n linear equations in n unknowns)
Read in an integer n followed by n linear equations in n unknowns and solve for the n unknowns.  Consider the following system of equations:
     2a + 2b - 5c = -18
     4a + 3b - 4c = -4
     5a + 4b - 3c = 8
These would be entered by the following numbers (one per line):
     3 2 2 -5 -18 4 3 -4 -4 5 4 -3 8
Print out the values of the unknowns rounded to nearest 0.01.
For the given data, your program should output:
     2.0
     4.0
     6.0

Q2:  Polynomial Fitting
Read in an integer n followed by n points (x1,y1,x2,y2,...), one value per line, and print out a polynomial of degree (n-1) that fits those points. Round coefficients to the nearest 0.01.

Sample input (entered one number per line): 2 1 1.5 2 2.5
Sample output: 1.0x^1 + 0.5x^0

Sample input: 3 -1.5 5 2 -2 4 5
Sample output: 1.0x^2 + -2.5x^1 + -1.0x^0

Q3:  Sum of Powers  (1^k + 2^k + ... + x^k)
Read in a positive integer k and print out the polynomial which represents the sum of the first x integers raised to the kth power. That is, 1^k + 2^k + ... + x^k.  Round coefficients to the nearest 0.01.

Sample input: 1
Sample output: 0.5x^2 + 0.5x^1 + 0.0x^0

Sample input: 2
Sample output: 0.33x^3 + 0.5x^2 + 0.17x^1 + 0.0x^0

Sample input: 4
Sample output: 0.2x^5 + 0.5x^4 + 0.33x^3 + 0.0x^2 + -0.03x^1 + 0.0x^0

To see that this is true, notice that:
    1⁴ + 2⁴ + 3⁴ + 4⁴ = 1 + 16 + 81 + 256 = 354
and
  0.2*4⁵ + 0.5*4⁴ + 0.33*4³ + 0.02*4² + -0.03*4¹ + 0.0*4⁰
   = 204.8 + 128 + 21.12 + 0.32 + -0.12 + 0
   = 354.12  (the extra 0.12 is due to roundoff error)