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: Sorting numbers (sort.c)

For this problem you will write two functions that sort an array of integers in either ascending (1, 2, 3, ...) or descending (..., 3, 2, 1) order, depending on user input. You should flesh out the following function declarations:

• void insertion_sort(int *num_array, int n, int order);
  • Accepts an array num_array with at least n elements and sorts the first n entries of num_array in ascending order if order is 0 or positive, and sorts the first n entries of num_array in descending order if order is negative.
  • The sorting method used must be insertion sort

• void selection_sort(int *num_array, int n, int order);
  • Accepts an array num_array with at least n elements and sorts the first n entries of num_array in ascending order if order is 0 or positive, and sorts the first n entries of num_array in descending order if order is negative.
  • The sorting method used must be selection sort

Here are some sample interactions with my program:

Which sorting method (I or i = insertion sort, S or s = selection sort)?
I
Which order (A or a = ascending, D or d = descending)?
D
Enter some numbers:
5
9
3
10
55
48
2
1
-1
Descending insertion sort:
55 48 10 9 5 3 2 1



Which sorting method (I or i = insertion sort, S or s = selection sort)?
s
Which order (A or a = ascending, D or d = descending)?
a
Enter some numbers:
5
9
3
10
55
48
2
1
-1
Ascending selection sort:
1 2 3 5 9 10 48 55

• Your sorting functions must sort the array in different orders, depending on whether the desired order is ascending or descending. You may not simply always sort the array in one order and then print it forward or backwards according to the selected ordering.
• It may be helpful to use additional functions like int compare(int a, int b, int order) and void swap(int *num_array, int i, int j)