## One Step, Two Steps

### August 18, 2017

Today’s exercise is a simple matter of counting:

Suppose you can take either one or two steps at a time. How many ways can you travel a distance of n steps? For instance, there is 1 way to travel a distance of 1 step, 2 ways (1+1 and 2) to travel two steps, and 3 ways (1+1+1, 1+2 and 2+1) to travel three steps.

Your task is to write a program to count the number of ways to travel a distance of n steps, taking 1 or 2 steps at a time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 2 Responses to “One Step, Two Steps”

1. Rutger said

Given you have reached step n, you could have gotten there in two ways:
a) stepping to n-2 and doing a +2 step
b) stepping to n-1 and going a +1 step

so f(n) = f(n-2) + f(n-1), which reeks of Fibonacci with f(1) = 1 (take a +1 step), f(2) = 2 (take two +1 steps or one +2 step).

For in implementation of Fibonacci I keep on ging this guy credits for his beautiful (although inefficient) Fib oneliner: http://paulhankin.github.io/Fibonacci/

def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) – (2 << n) – 1) & ((2 << n) – 1)

2. ZSG1 ;
Q
;
DO ;
F I=1:1:10 W !,I," –> ",\$\$F^ZSG1(I,0,0)
Q
;
F(GOAL,SUBTOTAL,TALLY) ;
S TALLY=\$\$G(GOAL,SUBTOTAL,TALLY,1)
S TALLY=\$\$G(GOAL,SUBTOTAL,TALLY,2)
Q TALLY
;
G(GOAL,SUBTOTAL,TALLY,NUM) ;
I SUBTOTAL+NUM>GOAL Q TALLY
I SUBTOTAL+NUM=GOAL Q TALLY+1
Q \$\$F(GOAL,SUBTOTAL+NUM,TALLY)

1 –> 1
2 –> 2
3 –> 3
4 –> 5
5 –> 8
6 –> 13
7 –> 21
8 –> 34
9 –> 55
10 –> 89