Find the number of different ways to climb a staircase with n stairs using steps of odd sizes only.
Disregard the physical limitations of step's size.
Case 1: The order of the steps is relevant.
Case 2: The order of the steps is irrelevant.
DECLARE SUB takeStepA (wh!)
DECLARE SUB takeStep (wh!)
CLEAR , , 25000
DIM SHARED h(100), ways, n, tot
CLS
FOR n = 1 TO 30
ways = 0: tot = 0
takeStep 1
PRINT n, ways
NEXT n
STOP
PRINT
FOR n = 1 TO 30
ways = 0: tot = 0
takeStepA 1
PRINT n, ways
NEXT n
SUB takeStep (wh)
FOR stSize = 1 TO n - tot STEP 2
tot = tot + stSize
h(wh) = stSize
IF tot = n THEN
ways = ways + 1
ELSE
takeStep wh + 1
END IF
tot = tot - stSize
NEXT
END SUB
SUB takeStepA (wh)
IF wh = 1 THEN st = 1: ELSE st = h(wh - 1)
FOR stSize = st TO n - tot STEP 2
tot = tot + stSize
h(wh) = stSize
IF tot = n THEN
ways = ways + 1
ELSE
takeStepA wh + 1
END IF
tot = tot - stSize
NEXT
END SUB
In Case 1, the resulting numbers are the Fibonacci numbers:
steps ways
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
In Case 2, the numbers are less familiar:
1 1
2 1
3 2
4 2
5 3
6 4
7 5
8 6
9 8
10 10
11 12
12 15
13 18
14 22
15 27
16 32
17 38
18 46
19 54
20 64
21 76
22 89
23 104
24 122
25 142
26 165
27 192
28 222
29 256
30 296
Sloane's OEIS finds A000009 as fitting these numbers.
|
|
Posted by Charlie
on 2013-05-08 17:40:00 |
computer solution
