-------------------------------------------------------------------------------
Michael Locasto Introduction to Computer Programming in C
Homework 1 Fall 2005
$Id: hw1.txt,v 1.4 2005/09/14 14:08:50 locasto Exp $
-------------------------------------------------------------------------------
Due: October 6th, 2005 Before Class (Courseworks timestamp).
[PROGRAMMING]
0) Random number generation. (20 pts)
Often, computer scientists, statisticians, physicists, social
scientists, and mathematicians need a list of random numbers.
Political pundits also find lists of random numbers useful to
provide 'statistical' evidence of their arguments.
Implement a tool to generate and print a sequence of 10 random numbers.
Each random number should be an integer in the range from 0 to 100,
inclusive (that means both 0 and 100 should have a chance of appearing).
$ ./grand
56 77 91 2 33 40 72 100 6 2
$
Augment your program to take a command line parameter specifying how
many random numbers to generate. That is, if grand is invoked by:
$ ./grand 4
it will output 4 random numbers from 0 to 100, inclusive. Make sure
your program does something sensible if the supplied argument is not
a valid integer. There should not be an arbitrarily imposed upper
limit to this number.
Since it is easy to forget how to use programs, it is often useful to
provide a well-known command line switch (or parameter) that tells the
user how to invoke the program. Augment your program to recognize two
more command line arguments, '-h' and '--help' that prints out the
usage information for the program. For example,
$ grand -h
and
$ grand --help
should output the following usage information:
grand [-h | --help] : output this usage message.
grand [n] : print out n random integers in [0,100]
Finally, augment your program to print out its version. Don't forget to
add this usage case to your help dialog.
$ grand --version
grand-0.0.3
$ grand -v
grand-0.0.3
$
-----------------------------------------------------------------------------
1) Functions and Recursion (30 pts)
Experiment with recursion. The Fibannaci sequence is a famous naturally
recursive series of numbers whose ratio approaches the Golden Ratio.
f(n) = f(n-1) + f(n-2)
Implement a program named 'fib' that uses recursion to calculate and
print the first n Fibannaci numbers, where 'n' is less than or equal
to 30.
Usage:
fib [n]
For example, 'fib 4' should output:
fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
Modify your program so that providing the --target or -t option will
print only the nth Fibannaci number.
$ fib --target 3
fib(3) = 3
$
------------------------------------------------------------------------------
2) Pascal's Triangle. (50 pts)
This assignment will help you learn how to use arrays and the formatting
output function printf().
Pascal's Triangle is a mathematical construct that can be used to
generate the coefficients of n-term algebraic equations. That is,
given the expression (a + b)(a + b), the coeffcients for its terms
can be found by taking the entries from the 3rd row of the triangle.
This makes more sense if you remember that Computer Scientists always
start counting from 0: for a polynomial with 2 factors, we look at the
row numbered 2, which is the 3rd row in the triangle.
The expression (a+b)(a+b) expands to a^2 + 2ab + b^2. The coefficients
for this expression are 1, 2, and 1.
The first part of Pascal's Triangle is:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
You can see that each entry (except those in the first 2 rows) is
calculated by summing the elements in the previous row that are
(a) directly above and (b) directly above and to the left. Since each
1st entry is lacking an 'above left' entry, we assume that the value of
this 'above left' entry is 0. Since each last entry is lacking a
'directly above' entry, we assume that the value of this 'directly
above' entry for these entries is 0.
The triangle is prettier to look at in this format:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Write a program called 'pt' to calculate Pascal's Triangle for the
n-th row. You should supply your program one argument: the number
of rows to generate and print. You should first generate and print
the values for the simple triangle (without the center justification).
Then your program should print the values with each row centered.
You may assume that you are never asked to generate more than 25
rows. Make sure you adjust the field widths in the printf to keep
each row center justified as the numbers increase in width (from 1
digit to 2 to 3, etc.).
As always, make sure your program can print out help/usage information
and a version number.