Jump to content
BrainDen.com - Brain Teasers
  • 0

Climbing Stairs


BMAD
 Share

Question

2 answers to this question

Recommended Posts

  • 0

Same as rocdocmac

Spoiler

Before reaching 20 (n) stairs, you can either:
- go up 1 stair  and apply the solution for 19 (n-1) stairs -- or --
- go up 2 stairs and apply the solution for 18 (n-2) stairs.

This gives the formula: f(n)=f(n-1)+f(n-2). (Looks like Fibonacci...)

For 1 stair,  there is 1 possibility.
For 2 stairs, there is 2 possibilities. => Fibonacci

Combinatorics:

Spoiler

Maximum number of double stair steps is given by the integer division of number of stairs by 2.
Complete sigle stair steps.
Take all permutations with repetitions:

Spoiler

from math import factorial as MF

FIBO_1,FIBO_2=1,1

# staircase will take the values 1,2,3,...20 (yes, 20)
for staircase in range(1,21):
  FIBO_1,FIBO_2=FIBO_2,FIBO_1+FIBO_2
  combi=0
  doubles=staircase//2

  # double will take values 0,1,2...doubles (see staircase)
  for double in range(0,doubles+1):
    single=staircase-double*2
    combi=combi+MF(single+double)//MF(double)//MF(single)
  # remove # in the next line for intermediate results
  # print(staircase,single,double,combi)

  print('stairs =',staircase,'combinations =',combi,'Fibonacci =',FIBO_1)
 

Output:

Spoiler

stairs = 1 combinations = 1 Fibonacci = 1
stairs = 2 combinations = 2 Fibonacci = 2
stairs = 3 combinations = 3 Fibonacci = 3
stairs = 4 combinations = 5 Fibonacci = 5
stairs = 5 combinations = 8 Fibonacci = 8
stairs = 6 combinations = 13 Fibonacci = 13
stairs = 7 combinations = 21 Fibonacci = 21
stairs = 8 combinations = 34 Fibonacci = 34
stairs = 9 combinations = 55 Fibonacci = 55
stairs = 10 combinations = 89 Fibonacci = 89
stairs = 11 combinations = 144 Fibonacci = 144
stairs = 12 combinations = 233 Fibonacci = 233
stairs = 13 combinations = 377 Fibonacci = 377
stairs = 14 combinations = 610 Fibonacci = 610
stairs = 15 combinations = 987 Fibonacci = 987
stairs = 16 combinations = 1597 Fibonacci = 1597
stairs = 17 combinations = 2584 Fibonacci = 2584
stairs = 18 combinations = 4181 Fibonacci = 4181
stairs = 19 combinations = 6765 Fibonacci = 6765
stairs = 20 combinations = 10946 Fibonacci = 10946

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...