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.
Programming Praxis 
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)
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