Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Suppose you are given a number n, which represents the height of a flight of steps, and then given the following rules:
- 1) You must take at least 2 steps to traverse the stairs;
- 2) Each successive step must be less than the previous step
- and then told to find the number of possible ways you could traverse this flight of stairs. E.g. when n = 4, you can only take 3 steps then 1 step, so Tn = 1. When n = 5 you can either take 4 steps then 1 step or 3 steps then 2 steps, so Tn = 2.
- I initially thought that the height of the first step could only be from (nmin) to (n - 1) where nmin is a the smallest integer k whose triangular integer that is greater than n. (E.g. if given n = 5, then nmin would be 3 because the triangular number of 2 is 3 which is less than 5). As as seen from the previous example, the lowest height of the first step is 3.
- I then wrongly deduced that the relation was described as Tn = Σ Ti, where i is from 1 to n - nmin,with a base case of 3 and 4, as T3 and T4 = 1. My reasoning is that if the first step is i steps, then (n - i) steps remain, so my answer should be a sum of all the remaining possibilities for each i.
- The problem with my definition is that it ignores the possibility of the second step being higher than the first step, violating rule 2. For example, if I take n = 13, the first steps height will range from [5, 12], so by my definition the sum should be from i = [1, 7]. However, during the summing, when i = 5, again the remaining number of steps to be taken is 7, but T7 also counts the possibility 6 steps then 1 step, which would cause the answer to be one more than it should be.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement