CS13002 Programming and Data Structures

Section: 5/E, Spring 2006

Assignment 4

Let n be a positive integer. Suppose that n persons are sitting on a straight line. Let us number the persons as 1,2,...,n in the order they appear on the line. The persons are very quarrelsome and fight whenever they are close to one another. A subcollection of these n persons is said to be nonbelligerent if the subcollection does not contain any two consecutive persons, i.e., persons i and i+1 for some value of i. The empty subcollection is also treated as nonbelligerent. Let Ln denote the number of of nonbelligerent subcollections of n persons on a line. These collections together with Ln for some small values of n are given in the next table.

nNonbelligerent collections on a lineLn

Write a recursive function in order to compute the value of Ln. The function should take two arguments: n and the last person l chosen so far. The next choice must be one from l+2,...,n. For each such choice m, pass n and m to a recursive call. Another possibility is that no other person is chosen in the collection at all. Take a sum of the counts from all possibilities and return the sum. The outermost call of the recursive function in the main() function must pass a suitable value for the second parameter.

Next suppose that the persons are sitting on a circle, so that persons 1 and n are now adjacent to one another. Let Cn denote the number of nonbelligerent subcollections of n persons in a circle. The following table summarizes some small values.

nNonbelligerent collections on a circleCn

Write a second recursive function for computing the value of Cn. Here break the computation in two parts according as whether the first person is chosen or not. In addition to n and the last person l chosen so far, you should also pass an indicator (flag) about the choice of the first person.

You are not asked to find out the nonbelligerent collections themselves (Solve Assignment 5 for that). You are asked only to compute their counts. These counts can be obtained in a variety of ways. Here I urge you strongly (almost force you) to follow the recursive strategy outlined above. This will help you in understanding recursive behavior of functions. Following other algorithms may defeat this basic purpose.

Report the values of Ln and Cn for n=20,25,30,35.

Sample output

Enter number of persons : 10
Number of nonbelligerent collections in a line   = 144
Number of nonbelligerent collections in a circle = 123

Enter number of persons : 15
Number of nonbelligerent collections in a line   = 1597
Number of nonbelligerent collections in a circle = 1364

Mathematical challenge: (Not for submission)

Find closed-form formulas for Ln and Cn.

[Submission site] [Lab home] [Course home]