Lab 4: Arrays

This lab will develop your skills in using arrays.

This page will be available as

http://www.tricity.wsu.edu/~bobl/cpts121/lab04_arrays/writeup.html

Calling it up in a browser will allow you to cut-and-paste the templates below into your editor and save editing time.

Plug your thumbdrive into your workstation. Give it a few seconds to be recognized by Windows and then create a MinGW terminal emulator. In that emulator, create a new directory for this lab and cd to it:

$ cd /e/cpts121
$ mkdir lab04
$ cd lab04

As always, keep all your work for this lab in this directory.

Pascal's Triangle

The French mathematician Blaise Pascal is credited with a triangular arrangement of binomial coefficients C(n,m). Sometimes read as "n choose m", this is the number combinations of n things taken m at a time. For example, there are C(52,5) = 2,598,960 distinct poker (5-card) hands.

There are n rows in the triangle, starting at n = 0, and each row has n+1 elements. There is only one way to choose n = 0 objects, so the first row is:

Each additional row has one more element from the previous row and is built by adding the two elements above it (or copying the single element at the ends). The second row is:

1 1

This means that given one object, there is one way to choose no objects and one way to choose one object. The next three rows make this clearer:

1 2 1
1 3 3 1
1 4 6 4 1

These are more conventionally printed as an isosceles triangle:

Assignment

Write a program that can print out Pascal's Triangle with the proper indentation. Here's the pseudocode:

#include <stdio.h>

/*
 * This will work with any positive value of MAX_ROWS. This one
 * produces cool-looking results on an 80-character width console, but
 * you might want to set it to a lower value like 5 while debugging.
 * (Or a higher value if you want to print a poster!)
 */
#define MAX_ROWS 16

int main(void)
{
    /*
     * declare int arrays oldRow[] and newRow[] to hold MAX_ROWS+1 elements
     * for n from 0 to MAX_ROWS-1 (thus looping MAX_ROWS times)
     *     compute and output appropriate indentation (see text below)
     *     for m from 0 to n, inclusive
     *         if m is zero (first item on row)
     *             set newRow[m] to 1
     *         else if m is n (last item on row)
     *             set newRow[m] to 1
     *         else (middle items on row)
     *             set newRow[m] to the sum of the m'th and the m-1'st
     *              elements of oldRow[]
     *     for m from 0 to n, inclusive
     *         print the m'th element of newRow[] (without a newline)
     *         set oldRow[m] to newRow[m] (for the next iteration)
     *     print a newline
     */
    return 0;
}

A few notes:

Pascal's triangle cannot be easily computed with a single array. It needs two: an old one (oldRow[]) that holds the previous row and a new one (newRow[]) that gets the new one based on the old one. After printing out the new one, it's copied to the old one, ready for the next iteration.
The format spec of "%4d " to print the elements works pretty well, but feel free to try others.
Get the rest of the program working before you do the indentation, calculating a number of spaces nSpaces (or whatever you want to call it), to indent. nSpaces will be based on n. Then insert a loop where the pseudocode says to do then indentation to print out nSpaces spaces.

Questions:

Why do oldRow[] and newRow[] have MAX_ROWS+1 rather than MAX_ROWS elements?
(After you know what pointers are.) How could you write the program with pointers to make it faster?