| CS21003 Algorithms I
CS29003 Algorithms Laboratory
|Autumn 2012, L-T-P: 3-1-0
You are given R red marbles and B blue marbles. Your task is to arrange the R + B marbles in a line such that certain restrictions are satisfied (see below). You print all possible arrangements under the given restrictions, and the total count of arrangements possible.
In this part, the restriction is that no two red marbles may be placed consecutively. Write a single recursive function to print the arrangements and return the count of possibilities. Do not use any global or static variables. Place the available marbles one by one in an array of size R + B. When u red and v blue marbles are placed, find out the options (red and/or blue) at the (u + v + 1)-st position. For each available option, recursively compute the acceptable configurations with u + v + 1 marbles placed in the array.
In this part, two red marbles may appear in consecutive positions, but three or more red marbles are not allowed to come consecutively. Write a second recursive function following the same line of programming logic as in Part 1.
Sample outputEnter number of red marbles (R) : 2 Enter number of blue marbles (B) : 4 Part 1 rbrbbb rbbrbb rbbbrb rbbbbr brbrbb brbbrb brbbbr bbrbrb bbrbbr bbbrbr Total number of possibilities is 10 Part 2 rrbbbb rbrbbb rbbrbb rbbbrb rbbbbr brrbbb brbrbb brbbrb brbbbr bbrrbb bbrbrb bbrbbr bbbrrb bbbrbr bbbbrr Total number of possibilities is 15
- Construct recurrence relations for computing these counts of arrangements.
- Analyze the running times of these recursive algorithms.