一只青蛙一次可以跳1阶或者2阶，n阶，有多少种到达终点的方式。

前两天面试遇到的一个题，当时没有想清楚，今天想了一下，po出来；

# -*-encoding:utf-8-*-

import sys

end = 0 # 终点

cnt = 0 # 统计组合方式

def jump(start):

    global cnt

    for i in [1,2]:

        cur = str(start)+"+"+str(i)

        if eval(cur) >= end:

            print cur

            cnt += 1

            continue

        jump(cur)

def main(n):

    """

    一只青蛙一次可以跳1阶或者2阶，n阶，有多少种到达终点的方式。

    """

    global end

    end = n

    jump(0)

    print "count: "+str(cnt)

if __name__ == "__main__":

    main(int(sys.argv[1]))

D:\myGit\test>testFrog1.py 4
0+1+1+1+1
0+1+1+1+2
0+1+1+2
0+1+2+1
0+1+2+2
0+2+1+1
0+2+1+2
0+2+2
count: 8

D:\myGit\test>testFrog1.py 5
0+1+1+1+1+1
0+1+1+1+1+2
0+1+1+1+2
0+1+1+2+1
0+1+1+2+2
0+1+2+1+1
0+1+2+1+2
0+1+2+2
0+2+1+1+1
0+2+1+1+2
0+2+1+2
0+2+2+1
0+2+2+2
count: 13

这个题主要就是考算法-递归，当时没有想清楚乱写一通，还是自己有些紧张；

巴特西

一只青蛙一次可以跳1阶或者2阶，n阶，有多少种到达终点的方式。

最新文章

热门文章