COMS 113: Introduction to C

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 oneill+assign2@cs.cornell.edu.

Please create a separate .c file for each problem.

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.)

I've also included some basic information about my own solutions to the problems. Don't worry if you don't match my solution in terms of the number of functions or the number of lines of code — I've included this information just so you know if you're working too hard on a particular problem.

Problem: Fibonacci and Friends

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

Hints:

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.
My solution uses no extra functions other than main(), and the total number of lines of code inside main() (not including whitespace) is 26.

Problem: Prime Numbers

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

My solution uses two functions in addition to main(), and the total number of lines of code inside functions is 22.

Problem: Averaging an Array

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.

USING THESE FUNCTIONS, write a program that accepts a sequence of nonnegative integers separated by carriage returns, terminated by a negative integer. (You may assume that the user only inputs integers.) Your program should accept at most 100 integers and should stop reading integers after 100 have been read. Using your functions, your program should compute the mean and the stdev and print the results.

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

Hints:

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.)
My solution uses two functions in addition to main() (as you might guess), and the total number of lines of code inside functions is 22.