网站的建设合同是否交印花税,网站质量度,wordpress插件 乱码,c 类似wordpress问题描述#xff1a;
一只青蛙要跳上n级台阶#xff0c;它每次可以跳 1级或者2级。问#xff1a;青蛙有多少种不同的跳法可以跳完这些台阶#xff1f; 举个例子#xff1a;
假设台阶数 n 3 #xff0c;我们来看看青蛙有多少种跳法。
可能的跳法#xff1a; 1. 跳1级…问题描述
一只青蛙要跳上n级台阶它每次可以跳 1级或者2级。问青蛙有多少种不同的跳法可以跳完这些台阶 举个例子
假设台阶数 n 3 我们来看看青蛙有多少种跳法。
可能的跳法 1. 跳1级再跳1级再跳1级。111 2. 跳1级再跳2级。12 3. 跳2级再跳1级。21
所以当 n 3 时总共有 3种跳法。
规律是什么
我们可以发现青蛙跳到第 \( n \) 级台阶的跳法数取决于它跳到前两级台阶的跳法数 1. 如果青蛙最后一步跳 1级那么它之前一定是从第 n-1 级跳上来的。 2. 如果青蛙最后一步跳 2级那么它之前一定是从第 n-2 级跳上来的。
递推公式
f(n) f(n-1) f(n-2) 其中 f(1) 1 只有1级台阶只有一种跳法 f(2) 2 2级台阶可以跳11或者直接跳2
具体计算
我们用一个表格来计算 \( f(n) \) 的值
台阶数n跳法数f(n)计算方式11只有一种跳法122两种跳法11或233f(2f(1)2145f(3)f(2)3258f(4)f(2)53.........
代码实现
用代码来计算f(n)的值
def jump_ways(n):if n 0:return 0elif n 1:return 1elif n 2:return 2# 初始化前两级台阶的跳法数prev1, prev2 1, 2 # f(1) 1, f(2) 2# 从第3级开始计算for i in range(3, n 1):current prev1 prev2prev1, prev2 prev2, currentreturn prev2# 示例
n 5
print(f跳上 {n} 级台阶的跳法数{jump_ways(n)})
输出
跳上 5 级台阶的跳法数8
总结 跳到第 n 级台阶的跳法数等于跳到第 n-1 级的跳法数加上跳到第n-2级的跳法数。 - 这个规律和斐波那契数列是一样的。 - 通过动态规划我们可以高效地计算出结果。
