| CS29003 Algorithms Laboratory | Autumn 2013, L-T-P: 0-0-3 |
Warmup Assignment
Danger of Recursion
A frog stands in front of a flight of n stairs. In one jump, the frog can cover one, two or three steps. In how many ways can the frog cross all the steps? Call it C(n).
For example, if n = 4, then all the possibilities for the frog are (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2) and (3,1). Therefore, C(4) = 7.
Part 1
Frame a recurrence relation for C(n), and make a straightforward recursive implementation. (Write a recursive function.)
Part 2
Make an efficient (linear-time and constant-space in n) iterative implementation. (Write a non-recursive function.)
Part 3
Suppose you want to compute C(n,m) which stands for the number of ways the frog can cross n steps in exactly m jumps. Derive a recurrence relation for C(n,m), and write a recursive function for it.
Part 4
Make an efficient iterative function to compute C(n,m). You are permitted to use only one local array of size n + 1, and some constant number of local variables.
The main() function
- Read n from the user. (Take n no larger than 37.)
- Run the function of Part 1 on n.
- Run the function of Part 2 on n.
- Run the function of Part 3 on n,m for all m in [0,n]. Report the sum of all these return values.
- Run the function of Part 4 on n,m for all m in [0,n]. Report the sum of all these return values.
For n above 30, you can see how slow your recursive functions are.
Sample Output
n = 16 +++ Any number of jumps... Recursive function returns count = 10609 Iterative function returns count = 10609 +++ Fixed number of jumps... Recursive function returns count = 0 for m = 0 Recursive function returns count = 0 for m = 1 Recursive function returns count = 0 for m = 2 Recursive function returns count = 0 for m = 3 Recursive function returns count = 0 for m = 4 Recursive function returns count = 0 for m = 5 Recursive function returns count = 21 for m = 6 Recursive function returns count = 266 for m = 7 Recursive function returns count = 1107 for m = 8 Recursive function returns count = 2304 for m = 9 Recursive function returns count = 2850 for m = 10 Recursive function returns count = 2277 for m = 11 Recursive function returns count = 1221 for m = 12 Recursive function returns count = 442 for m = 13 Recursive function returns count = 105 for m = 14 Recursive function returns count = 15 for m = 15 Recursive function returns count = 1 for m = 16 --------------------------------------------- Total number of possibilities = 10609 Iterative function returns count = 0 for m = 0 Iterative function returns count = 0 for m = 1 Iterative function returns count = 0 for m = 2 Iterative function returns count = 0 for m = 3 Iterative function returns count = 0 for m = 4 Iterative function returns count = 0 for m = 5 Iterative function returns count = 21 for m = 6 Iterative function returns count = 266 for m = 7 Iterative function returns count = 1107 for m = 8 Iterative function returns count = 2304 for m = 9 Iterative function returns count = 2850 for m = 10 Iterative function returns count = 2277 for m = 11 Iterative function returns count = 1221 for m = 12 Iterative function returns count = 442 for m = 13 Iterative function returns count = 105 for m = 14 Iterative function returns count = 15 for m = 15 Iterative function returns count = 1 for m = 16 --------------------------------------------- Total number of possibilities = 10609
Submission site | Miscellaneous information | Home