CS113: Homework 2

Turn in a PRINTOUT of your program (no sample data necessary) with your full name and netID, in class; AND, e-mail the source code to wes28@cs.cornell.edu.

Please create a separate .c file for each problem. Make the subject line of your email "Assignment 2".

DO NOT just e-mail me your source code. YOU MUST turn in a printout of the code to receive credit for the assignment.

In some of these problems, you will be asked to write specific functions. In your programs, you are free to introduce your own additional functions to aid you. (You are encouraged to do so, in fact, as long as you don't go overboard.)

Problem: Fibonacci and Friends (sequence.c)

The Fibonacci sequence is the sequence of numbers beginning with 1 and 1 as its first two numbers; all other numbers are defined recursively as the sum of the previous two numbers. The first 10 numbers in the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Write a program that generates Fibonacci-like sequences from two integers provided as input. (Later numbers in the sequence are defined recursively as the sum of the previous two numbers, as in the Fibonacci sequence.)

The Fibonacci-like sequence resulting from your initial numbers is infinite; to print some finite subset, your program should also prompt the user for a starting point k1 and an ending point k2 and should print out the k1-th to k2-th numbers in the sequence (inclusive), along with a label telling which number in the sequence is being printed. These numbers should be printed in fields of width 6. For all numbers in the sequence other than the first, it should also print out the ratio of that number to the previous one.

Here are some sample interactions with my program; your program should behave identically.

Enter initial numbers:
1
1
Enter starting point for printing: 1
Enter ending point for printing: 10
     1:      1  
     2:      1  ratio = 1.000000
     3:      2  ratio = 2.000000
     4:      3  ratio = 1.500000
     5:      5  ratio = 1.666667
     6:      8  ratio = 1.600000
     7:     13  ratio = 1.625000
     8:     21  ratio = 1.615385
     9:     34  ratio = 1.619048
    10:     55  ratio = 1.617647


Enter initial numbers:
1
2
Enter starting point for printing: 1
Enter ending point for printing: 2
     1:      1  
     2:      2  ratio = 2.000000


Enter initial numbers:
2
6
Enter starting point for printing: 2
Enter ending point for printing: 6
     2:      6  ratio = 3.000000
     3:      8  ratio = 1.333333
     4:     14  ratio = 1.750000
     5:     22  ratio = 1.571429
     6:     36  ratio = 1.636364


Enter initial numbers:
1
3
Enter starting point for printing: 5
Enter ending point for printing: 15
     5:     11  ratio = 1.571429
     6:     18  ratio = 1.636364
     7:     29  ratio = 1.611111
     8:     47  ratio = 1.620690
     9:     76  ratio = 1.617021
    10:    123  ratio = 1.618421
    11:    199  ratio = 1.617886
    12:    322  ratio = 1.618091
    13:    521  ratio = 1.618012
    14:    843  ratio = 1.618042
    15:   1364  ratio = 1.618031

• Be sure to use printf effectively to make the printing as easy as possible. For example, the tag "%10.5f" will print a floating-point number with 5 decimal places in a column of width 10.

Problem: Prime Numbers (prime.c)

Write a function, next_prime, that accepts one parameter, a variable of type int, and returns an int:

int next_prime( int a ) {}

This function should return the lowest prime number which is greater than or equal to the value passed to it. (Recall that a prime number is a positive integer with exactly two numbers dividing it evenly, one and itself. The first five prime numbers are 2, 3, 5, 7, 11.)

For example, next_prime( 14 ) should return 17, because 17 is the first prime in the list 14, 15, 16, .... Also, next_prime( 19 ) should return 19 and next_prime( 55 ) should return 59.

If you want to make your function more efficient, note that an integer n is prime if and only if it has no divisors less than (or equal to) the square root of n. The function sqrt defined in the standard library math.h may be helpful in this regard. (If you're using gcc, you can use the "-lm" at compile-time to link to math.h, assuming it's "#included" in your source file.) Also, no even numbers greater than 2 are prime. (If you're interested, efficient primality testing for very large numbers is very complicated, but was recently discovered to be computationally tractable.)

USING THIS FUNCTION, write a program which accepts as input two integers, and prints out all prime numbers which are greater than or equal to the first, and less than or equal to the second (in ascending order.) You must use the function next_prime in an essential way to receive credit for this problem!

Here are some sample interactions with my program:

Enter the low: -5
Enter the high: 10
The prime numbers between -5 and 10 are:
2  3  5  7  


Enter the low: 5
Enter the high: 22
The prime numbers between 5 and 22 are:
5  7  11  13  17  19  

Problem: Averaging an Array (average.c)

For this problem you will write two functions that find the mean and the standard deviation of an array of integers. You should flesh out the following function declarations:

• float mean(int *num_array, int n);
  • Accepts an array num_array with at least n elements and returns the mean of the first n elements as a floating-point number.
• float stdev(int *num_array, int n);
  • Returns the standard deviation of the first n elements as a floating-point number.
  • It can be calculated using the formula presented here. (Basically you take the mean of the squares of the differences between the elements of the array and the mean.)
  • You may not modify the array that you pass to the function, or declare any new arrays in the body of the function.

Here are some sample interactions with my program:

Enter some numbers:
4
9
11
12
17
5
8
12
14
-1
The mean is: 10.222222
The standard deviation is: 3.937788


Enter some numbers:
1
2
3
4
5
-1
The mean is: 3.000000
The standard deviation is: 1.414214

• Try writing the program for a maximum array size of much less than 100 in order to check boundary conditions.
• The declaration "int *num_array" says that num_array is an array type, but does not specify the size of the array. (Within the function you can refer to "num_array[k]" to access the (k+1)th element of the array.)

Problem: Bell numbers (bell.c)

Note: For this problem, I am intentionally giving you less guidance than for the others. It is 5Aintended to be somewhat more challenging.

The number of subsets of a set of N distinct objects is N!. The number of ways to arrange N distinct objects into K distinctly labeled subsets is K^N. (As an illustration, think about placing 5 different chess pieces onto 5 plates, each of which is a different color. There are 5^5 = 3125 ways to do this.) How many ways can N objects be partitioned into non-empty (but undistinguished) subsets? (E.g. How many ways can you arrange 5 distinct chess pieces onto 5 plates of the same color, where each plate is considered to be the same as any other?) The answer is the Nth Bell number. (B(0) = 1, B(1) = 1, ... , B(5) = 52). There are formulas for the Kth bell number given by infinite series, but it is also possible to calculate the Kth Bell number from the Bell Triangle, which is described here.

Write a program that takes as input from the user a positive integer K indicating the Bell number to be computed, and then output the Kth bell number.

Hints and restrictions :

• You may assume that K is less than 20.
• You may pre-allocate an N x N array for N less than 100, but you may not make the array global.
• It may be helpful to use recursion to fill in the Bell Triangle.
• You probably want to use the keywords 'long' and 'unsigned'.