• View
• Edit
• History
• Print
• PDF

CalculateSteps

(:source lang=python:)

1. !/usr/bin/env python

import sys

def Calculate(n):

    Calculates no of ways steps can be climbed
    if n == 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4

    Count=[0]*4
    Count[0],Count[1],Count[2] = 1,2,4
    shifter, a, b, c, d = 0, 0, 0, 0, 0
    for i in xrange(3,n):
        a, b, c, d = shifter%4, (shifter+1)%4, (shifter+2)%4, (shifter+3)%4
        Count[d] = Count[a] + Count[b] + Count[c]
        shifter = shifter+1
    return Count[d]

cache = {}

def bp_calc(n):

    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4

    global cache

    if n in cache:
        return cache[n]

    sum = 0
    for i in range(n-3, n):
        sum = sum + bp_calc(i)

    cache[n] = sum

    return sum

def bp_calc2(n):

    c = {}
    c[1] = 1
    c[2] = 2
    c[3] = 4

    for i in range(4, n+1):
        c[i] = c[i-1] + c[i-2] + c[i-3]

    return c[n]

print Calculate(int(sys.argv[1])) print bp_calc(int(sys.argv[1]))

(:sourceend:)