Archangel Macsika
3. In how many ways can an elf climb a staircase of 15 stairs if each step it takes can cover 1 or 2 or 3 stairs? Explain why your solution is valid. (Hint: Work on fewer number of stairs first and try to generalize.)
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
A recurrence relation for the number of ways to climb n stairs:
S(n) = S(n-1) + S(n-2) + S(n-3), where S(-2) = S(-1) = 0, S(0) = 1;
It's possible to calculate S(15) by sequential counting. S(2) = 2, S(3) = 4, S(4) = 7, S(5) = 13, ... S(15) = 5768
It's also possible to calculate it with python code:
def findStep( n) :
if (n == 1 or n == 0) :
return 1
elif (n == 2) :
return 2
else :
return findStep(n - 3) + findStep(n - 2) + findStep(n - 1)
n = 15
print(findStep(n)) So we can find S(15) = 5768