Introduction to Programming (22C:16, 22C:106)

Practice Problems

Here are some practice problems. The solutions will be posted by Tuesday. The first two problems do not require recursion, but the remaining four do.

Problem 1:

Let be an arbitrary sequence of integers. Any sequence where is called a block of X. The sum of a block is simply . The problem is to find a block with minimum sum. For example consider the sequence

This sequence has several blocks, some of which are:

Clearly, among the blocks listed above -3, -3, 5, -6, -1 has minimum sum. In fact, it is easy to see that -3, -3, 5, -6, -1 has minimum sum among all blocks of X.

Write a function that takes a sequence of integers stored in an integer Vector and returns via reference parameters the left-endpoint and the right-endpoint of a block with minimum sum. For the sequence in the above example, the function would return the value 2 for the left-endpoint and the value 6 for the right-endpoint.

Problem 2:

Let S be a sequence of integers. An stutter in S is a block of identical integers. The index of the left-most element in the stutter is called the left-endpoint of the stutter and similarly the index of the right-most element is called the right-endpoint of the stutter. The integer that is repeated in the stutter is called the stuttering element. For example, in the sequence 4, 3, 3, 3, 3, 4, 5, 1, 1, 5, 5, 5, 2 there is a stutter with stuttering element 3 whose left-endpoint is 1 and whose right-endpoint is 4. There is also a stutter with stuttering element 5 whose left-endpoint is 9 and whose right-endpoint is 11. Note that any integer belonging to the sequence, by itself, is also a stutter (of length 1).

Write a function that takes in a sequence of integers stored in an integer Vector and returns via reference parameters (a) the left-endpoint (b) the right-endpoint and (c) the stuttering element of the longest stutter in the sequence. If there are several longest stutters, it does not matter which one your function picks. Use the following function header for your function:

void stutter(int list[], int NumElements, int & left, int & right, int & element)

Problem 3:

For Homework 10, you wrote a recursive function called maximum that returned the maximum integer in a given Vector of integers. Modify this function so that in addition to the maximum, the function also returns (via a reference parameter) the position of the maximum element. If there are several maximum numbers in the Vector, your function should return the position of the first maximum element. Make sure that even after the modification your function is recursive.

Problem 4:

Write a recursive function that reads a sequence of n integers and returns 1 if the sequence is in ascending order and 0 otherwise. Note that the integers are being extracted from cin, they are not stored in a Vector of any sort.

Problem 5:

Write a recursive function that takes as a parameter a non-negative integer n and returns the number of digits in n. Your function should compute the number of digits in n by extracting one digit at a time.

Problem 6:

In mathematics is used to denote the number of ways in which k objects can be chosen from among n distinct objects. Since there is exactly one way of choosing n objects from among n objects, . By convention, the number of ways of choosing 0 objects from among n is said to be 1 and hence . For any value of k, 0 < k < n, can be computed using the following recursive formula:

So for example, can be computed as follows:

1. Write a recursive function called choose that takes as parameters a positive integer n and an integer k, , and returns the value .

2. Suppose that the function choose is called from the main function with arguments n = 5 and k = 2. Write down the list of all the calls made to the function choose as a result of this call, specifying for each call the values of its two arguments. The calls should be listed in the order in which they are made.