C++

Exercise 4

TASK DESCRIPTION

The goal is to write a C++ program that:

Reads the coefficients of a polynomial and stores them in a vector
Reads an x value, evaluates the polynomial at x, and outputs the result
Computes the derivative of the polynomial
Evaluates the derivative at the same x value and outputs the result

Tackle one step at a time, and test your program as you go. This document gives suggestions and examples

INPUT SPECIFICATION

An n^th degree polynomial with (n+1) coefficients a_i should be read from standard input (cin) in the following form:

n a₀ a₁ ... a_n

For example, the input for the polynomial y(x) = 1 + 2.4x - 4x² + 7x³ (a polynomial of third degree) would be:

3
1 2.4 -4 7

The x value appears next in the input, so the input for the polynomial above with x = 1.5 would be:

3
1 2.4 -4 7
1.5

Line breaks and extra white space in the input are unimportant, so the above is equivalent to:

3 1 2.4 
-4 7 1.5

The correct output (y(x) and y'(x)) for the above input is:

p(x) = 19.225
p'(x) = 37.65

GETTING STARTED

You'll use standard input and output to read and print values. Standard input refers to input coming from the keyboard or piped into the program when it is executed. In C++, it is accessible as cin. Standard output gets printed to the console (or piped into another program at the command line), and is accessible in C++ as cout.
Here is a template from which you might start programming:

#include <iostream>    // for cin, cout, etc.
#include <vector>      // for storing polynomials
using namespace std;   // to refer to the above without 'std::' prefix

// Use this function to test your work as you go
void print_coefficients(const vector<double>& p)
{
    for (unsigned int i=0; i<p.size(); ++i)
        cout << p[i] << " ";

    cout << endl;
}

// put other function definitions here, before main

int main()
{
    int n;	
    cin >> n;  // read degree

    vector<double> p(n+1);

    for (int i=0; i<n+1; ++i) 
    {
        cin >> p[i];  // read the i^th coefficient
    } 
   
    double x;   // where to evaluate p
    
    cin >> x;  

    // TODO: evaluate p(x), output result

    vector<double> d;

    // TODO: compute derivative d
    // TODO: evaluate d(x), output result
}

STORING THE POLYNOMIAL

You should use the vector class to store the coefficients of the polynomials. vector is part of the C++ standard library, and provides an array-like container that allows dynamic resizing:

vector<double> v;          // The vector will hold values of type double (floating point numbers),
                           // and will start with no elements.
v.push_back(2.5);          // Stick 2.5 onto the back of the vector, thus increasing the size of v by 1
v.push_back(3.4);
cout << v.size() << endl;  // output is 2
cout << v[0] << endl;      // output is 2.5
cout << v[1] << endl;      // output is 3.4
for (unsigned int i=0; i<v.size(); ++i)
{
    cout << v[i] << endl;  // output each element of v on a separate line
}

You can also declare a vector with a starting size, and optionally a default value:

vector<double> v(10);  // v.size() == 10, all elements uninitialized (garbage values)
vector<int> w(5, 0);   // v.size() == 5, all elements initialized to 0

EVALUATING THE POLYNOMIAL

You should define a function which takes a vector holding the coefficients of a polynomial, and an x value, and returns the value of the polynomial at x:

double eval_poly(const vector<double>& p, double x)
{
    // put code here
}

You should use Horner's rule for evaluating a polynomial. For a polynomial p(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ, we have:

p(x) = a₀ + x(a₁ + x(a₂ + ... x(a_n-1 + a_nx)...))

This means you can compute p(x) by starting with y=0, looping backwards through the coefficients, highest coefficient first, multiplying y by x and adding the coefficient a_i. The resulting y is p(x).

COMPUTING THE DERIVATIVE

Recall that for a polynomial

p(x) = a₀ + a₁x + a₂x² + ... + a_ixⁱ + .... + a_nxⁿ

we have

p'(x) = a₁ + 2·a₂x + ... + i·a_i x^i-1 + ... + n·a_nx^n-1

The derivative p'(x) has one fewer terms than p(x), and its coefficients can be easily computed from those of p(x). You should store the derivative polynomial in a vector, and use the same function eval_poly to evaluate it.

COMPILING AND RUNNING THE PROGRAM

You can compile your program source (called, for instance, ex1.cc) at the command line using g++:

# g++ -Wall ex1.cc -o ex1

The -Wall flag tells the compiler to show all warnings, and the -o ex1 bit tells it to output the executable to file ex1. It will show any compile errors, with the corresponding line numbers in your source. When you run your program at the command line, you can type the input text once the program is running:

# ./ex1
2
1 2 3
0.5
p(x) = 2.75
p'(x) = 5

or you can store the input as plain text in a file and pipe it into your program:

# ./ex1 < myinput.in
p(x) = 2.75
p'(x) = 5

In both cases, the input is accessible in the program via standard input (cin). To test your program, give it the following input

5
1 2 3 4 5 -2.5
2.0

On to Exercise 5
Back to the main 1B C++ page

© 2010 University of Cambridge Department of Engineering
Information provided by Roberto Cipolla and Ethan Eade (Last updated: December 2010)
Privacy
Accessibility

Department of Engineering

1B C++ Computing (2016-17)