CSCE121-Lab 3 Functions Solved

The aim of this lab is to continue getting practice in writing functions. There are questions which emphasize the use of pass-by-reference parameters as a useful way to operate on data. Additionally, this lab will give you plenty of practice with arrays.




Pass-by-reference
Ordering a pair
Write a function order_pair that takes two int parameters x and y and swaps them if x  y.

Ordering a triple
Using your order_pair write a function three_in_a_row that takes three int parameters x, y, and z. Using pass-by-reference, have the function place its inputs in non-decreasing order so that after calling your function you have x ≤ y ≤ z. (Accomplish this without using an array.)

Reversing a list in place
Given an array of integers, write a function which changes the input so that the integers now appear in reverse order. The objective here is to do this in place, which means using only the input array and without making any new array of values.

The following gives an appropriate declaration for the function.

void rev_list(int input[], int num)
{ // Takes input, a list with num entries
// Alters input so that the entries are in reverse order
...
}

The preceding declaration might be a bit of a surprise. First, we tell the compiler that we're expecting an argument that is an array of ints, but we don't need to specify its size beforehand. (Which is just as well, as we don't want to have to write separate functions for arrays of size 10, and another for arrays of size 11, and another for 12, and so on.) Secondly, even though we'll be modifying the parameter input we don't put an ‘&’ before the name because arrays are automatically passed by reference.

?
HINT



Craps
These are the rules of a simple game of craps.
You roll a pair of dice. Suppose that the sum of their faces is V.

If V=7 or 11, the player wins.
If V=2, 3, or 12, the house wins.
If V=4, 5, 6, 8, 9, or 10, then you do the following:Keep rolling until you get a sum of V or 7.
If it was V, the player wins.
But if 7 comes up first, the house wins.
 

Suppose that you're running a casino that has a special dice machine which outputs a fixed sequence of dice rolls. These are represented by an array of ints. Write a function which, given such an array, reports whether (i) the player wins; (ii) the player loses; or (iii) more rolls are still needed.

Write your code to be robust to incorrect inputs. It should check that the array inputs really are within the 1-6 range for a standard die, outputting an error if things aren't correct.

Polynomials
One convenient way to represent a polynomial is as an array of coefficients. For example P1 a polynomial of degree 4 in x defined by P1(x) = 2.3 x4 + 1.2 x2 - 9.3 x + 8.4 can be expressed with five floating-point values stored in an array: {2.3, 0.0, 1.2, -9.3, 8.4}.

It is important notice the ordering of the coefficients and also the need to explicitly include zero values for missing terms to ensure that the position in the array implicitly gives the power of x associated with the coefficient.

Pretty printing polynomials
A good step in understanding some new representation of data is to find ways to display it. Your first task is to write a function which will give an attractive, easily readable presentation of the polynomial. Your function should print the following for P1:

P_1(x) = (2.3)*x^4 + (1.2)*x^2 + (-9.3)*x + (8.4)
Here's some skeleton code to get you started:

#include <iostream
using namespace std;

const int max_degree = 15;

void pretty_print_poly(float coeffs[], int degree)
{ // A function to write a nicely formatted version of the polynomial to cout
...
}

int main()
{
float p1_coeff[max_degree] = {2.3, 0.0, 1.2, -9.3, 8.4};

cout << "P_1(x) = ";
pretty_print_poly(p1_coeff, 4);
cout << endl;

return 0;
}
Evaluating polynomials
Of course we'd like to be able to do more than just print polynomials. Write a function poly_eval to evaluate a polynomial at a given value of x.

float power(float b, int exp)
{ // computes b^exp
// (Insert your code from the previous lab)
}

float poly_eval(float coeffs[], int degree, float x)
{ // evaluates a polynomial at x. The polynomial representation has
// taking in degree+1 coefficients in coeffs, with the highest degrees
// appearing first.
...
}

Horner's method
Horner's method for evaluating polynomials can be more efficient than the direct approach. It exploits the fact that any polynomial can be rewritten in order to save having to raise x to any power. Using the same polynomial as before as an example, we unroll it as follows:
P1(x) = 2.3 x4 + 1.2 x2 - 9.3 x + 8.4
= (2.3 x3 + 0.0 x2 + 1.2 x - 9.3)x + 8.4
= ((2.3 x2 + 0.0 x + 1.2)x - 9.3)x + 8.4
= (((2.3 x + 0.0)x + 1.2)x - 9.3)x + 8.4
The steps involved in getting to the final expression are not important for the code, but they help show how one arrives at the final expression.

Implement Horner's method and use your code from eval_poly_simple to help you verify that it is correct.

float horners_method(float coeffs[], int degree, float x)
{ // evaluates a polynomial at x. The polynomial representation has
// taking in degree+1 coefficients in coeffs, with the highest degrees
// appearing first.
...
}

Polynomial derivatives
Write a function which, given an array and the degree of the polynomial, alters the array and degree argument so that they represent the polynomial resulting from taking the derivative of the input (once, with respect to the sole variable).

Don't return a new array, but modify the one passed as input. It might be helpful, as a first step, to keep the same number of entries in the output as the input (hence, keeping the degree fixed). Once that is working, you should try to use one fewer entry in the array.

?
HINT


Computing the mode and median of a list
Suppose that you are given an array of n integers, each between 1 and 20, inclusive. In the following questions, you're asked to compute a summary statistic—try to do this with a single pass over the input array and, specifically, do this without sorting the list. Also, if the input contains numbers that are not within the prescribed range (i.e., not in 1-20), catch this fact and output an error message.

Mode of a list
The mode of a collection of numbers is the number which occurs most often. Write a function that returns the mode of the array. If there are multiple such numbers, break the ties by returning the smallest number.

int calc_mode(char list[], int n)
{ // computes the mode, list is assumed to have n numbers 1 <= x_i <= 20
...
}

Median of a list
The median of a collection of numbers is the number which separates the lower half of the numbers from the upper half. Write a function that returns the median of the array. If n is odd, the median is a number in the array. If n is even it may or may not be in the array.