''' 题目:一共有15台阶,小明每次可以爬一节,或者两节,或者三阶。 思路: 第一种 如果把她用数学语言符号化1阶台阶分解成1,意味着只有一种方法;2可以分解成2和1 1意味着二阶台阶有两种算法。3可以分解成 0 3,2 1,1 2 ,111 四种上法。用字典表达式{1:1,2:2,3:4} 思想是不管你上多少台阶都是由123台阶上法组合而来的。 考虑一下如何到达第4层楼梯 4可以分解成0 4,3 1 ,1 3 ,2 2,2 1 1,1 2 1,1 1 2 ,1 1 1 1分解成8种而只能用1 2 3 组合所以7种 5可以分解成16种,因为只能用1 2 3 组合所以13种 6可以分解为32种,因为只能用1 2 3 组合所以24种 删除元素的规律我没有找到,换下面的思路进行写题 第二种思路: 如何到达5台阶呢? 从4台阶上一个 从3台阶上两个 从2台阶上三个 只有以上这三种情况,三种情况相加就是就是达到5台阶的总算法 设到达4台阶有x种方法,到达3台阶有y种方法,到达2台阶有z种方法 所以到达5台阶就是x+y+z转成函数就是下列函数表达式 f(n)=f(n-1)+f(n-2)+f(n-3) n>=4 ''' def climbStairs1(n): #递推法 a=1 b=2 c=4 for i in range(n-3): c,b,a=a+b+c,c,b return c print(climbStairs1(15)) 上面用的是斐波那契数列算法 下面是递归算法 def climbStairs2(n): first={1:1,2:2,3:4} if n in first.keys(): return first[n] else: return climbStairs2(n-1)+climbStairs2(n-2)+climbStairs2(n-3) print(climbStairs2(15)) ''' 如果最多爬四阶台阶,原理是一样的 怎么到达15台阶? 14上一层 13上二层 12上三层 11上四层 f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4) ''' def climbStairs3(n): first={1:1,2:2,3:4,4:8} if n in first.keys(): return first[n] else: return climbStairs3(n-1)+climbStairs3(n-2)+climbStairs3(n-3)+climbStairs3(n-4) print(climbStairs3(15))
那个数学语言算法是我第一种想到的解法,奈何没有找到删除规律,只能搁浅。希望大家可以给我提下见解,谢谢你们在我修炼python路上提供的帮助。