## CS19002 Programming and Data Structures Laboratory, Section 5 |
## Spring 2007 |

[ Submission site | Show solution | Hide solution ]

## Part 1 [Credit: 70%]

Let

nbe a positive integer. Apartitionofnis a way of writingnas a sum of positive integers. For example, all the partitions of 5 are:1+1+1+1+1 1+1+1+2 1+1+3 1+2+2 1+4 2+3 5Permuting the summands in a partition does not give a new partition. For example, the partition 1+2+2 is treated the same as 2+1+2 and also as 2+2+1.

In this part, you are asked to compute the number of partitions of

n. Write a recursive function to this effect. In order to avoid repetitions, we choose the summands in a non-decreasing order. That is, if 1 and 2 are already chosen as the previous summands, the next summand cannot be less than 2. Pass two arguments to your recursive function. The first stands for the amount left to be balanced by summands and the second stands for the largest summand chosen so far. Recursion stops when the first argument becomes 0. Here is a possible prototype for the function.unsigned long countP ( unsigned long balance , unsigned long minchoice );## Part 2 [Credit: 20%]

Repeat Part 1 with the added constraint that no summand is repeated in the partition. For example, only three out of the seven partitions of 5 correspond to no repetitions:1+4 2+3 5Modify the recursive function of Part 1 slightly so as to generate the count of partitions without repetitions. A prototype for this function would be:

unsigned long countPNoRep ( unsigned long balance , unsigned long minchoice );## Part 3 [Credit: 10%]

In this part, you are asked to compute the number of partitions having an odd number of summands. For example, four out of the seven patitions of 5 contain odd numbers of summands:1+1+1+1+1 1+1+3 1+2+2 5Modify the recursive function of Part 1 in order to count the number of partitions of

ninto odd number of summands. Pass a third argument to the function in order to pass the information about how many summands have been chosen so far. When the balance (first argument) becomes zero, check whether an odd number of summands have been chosen so far. If so, that choice contributes to the total count, else not. A possible prototype is:unsigned long countPOdd ( unsigned long balance , unsigned long minchoice , unsigned int nsummands );Finally, here is a recommended

main()function for your program.int main () { unsigned long n; printf("Enter n: "); scanf("%lu", &n); printf("Count of all partitions = %lu\n", countP(n,1)); printf("Count of partitions without repetitions = %lu\n", countPNoRep(n,1)); printf("Count of partitions in odd no. of parts = %lu\n", countPOdd(n,1,0)); }Report the output of your program on the following values of

n.6 10 25 50 100## Sample output

Enter n: 5 Count of all partitions = 7 Count of partitions without repetitions = 3 Count of partitions in odd no. of parts = 4 Enter n: 40 Count of all partitions = 37338 Count of partitions without repetitions = 1113 Count of partitions in odd no. of parts = 18646 Enter n: 80 Count of all partitions = 15796476 Count of partitions without repetitions = 77312 Count of partitions in odd no. of parts = 7897846

[ Submission site | Show solution | Hide solution ]