There is a river and there are n number of steps between two banks of the river to cross the river.
A frog wants to cross the river with the condition that he can jump max one step. Find the number of ways he can cross the river?
For e.g. if there are 3 steps in between, frog can go from paths: _123_, _2_, _13_ so there are 3 different ways frog can cross the river (in the example _ is two ends of the river)
Source: http://www.geeksforgeeks.org/forum/topic/adobe-interview-question-for-software-engineerdeveloper-about-algorithms-31
def frogJumps(n): """ Takes n, checks if it is base case and returns base case outputs. Else call frogJumps with n-1and n-2. Base Cases: 1&2 rocks returns a number and list of nodes hopped by frog for n """ if n ==1: # one rock no jump return (0, [[1]]) if n == 2: # two rocks, one jump return (1,[[1, 2]]) # recurse # previous stone ! jumpsX, rocksX = frogJumps(n-1) # one before previous jumpsY,rocksY = frogJumps(n-2) # jump from previous stones to current stone for x in rocksX: x.append(n) for xinrocksY: x.append(n) rocks = rocksX+rocksY jumps = len(rocks) return (jumps, rocks) jumps, rocks = frogJumps(6) print jumps print rocks
No comments:
Post a Comment