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.

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: