编写跳台阶的算法
时间: 2023-07-26 14:12:57 浏览: 65
跳台阶是一个经典的递归问题。可以使用递归或动态规划算法解决。
递归算法实现:
```
int jumpFloor(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return jumpFloor(n-1) + jumpFloor(n-2);
}
```
动态规划算法实现:
```
int jumpFloor(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int f1 = 1, f2 = 2, f3;
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
```
其中,递归算法的时间复杂度是指数级别的,而动态规划算法的时间复杂度是线性级别的。因此,在实际应用中,应该尽量使用动态规划算法。
相关问题
用c语言中的迭代算法写猴子跳台阶的问题:有一只淘气的猴子一次可以跳1个台阶,也可以一次跳2个台阶,还以一次跳3个台阶,现有n个台阶,猴子从第1台阶跳到第n个台阶总共有多少种跳法。
以下是用 C 语言编写的迭代算法:
```c
#include <stdio.h>
int main() {
int n, i;
int a = 1, b = 2, c = 4, d; // 初始化 a、b、c,表示跳到第 1、2、3 个台阶的跳法数量
printf("请输入台阶数 n:");
scanf("%d", &n);
if (n == 1) { // 只有一个台阶时,只有一种跳法
printf("共 %d 种跳法\n", a);
return 0;
}
if (n == 2) { // 两个台阶时,有两种跳法
printf("共 %d 种跳法\n", b);
return 0;
}
if (n == 3) { // 三个台阶时,有四种跳法
printf("共 %d 种跳法\n", c);
return 0;
}
for (i = 4; i <= n; i++) { // 从第 4 个台阶开始计算跳法数量
d = a + b + c; // 计算跳到第 i 个台阶的跳法数量
a = b; // 更新 a、b、c 的值
b = c;
c = d;
}
printf("共 %d 种跳法\n", d); // 输出跳法数量
return 0;
}
```
代码思路:先初始化跳到第 1、2、3 个台阶的跳法数量,然后从第 4 个台阶开始计算跳法数量。用变量 a、b、c 分别表示跳到第 i-2、i-1、i 个台阶的跳法数量,每次计算跳到第 i 个台阶的跳法数量时,将 a、b、c 的值更新为 b、c、d,最后输出 d 即可。注意特判 n=1、2、3 的情况。
试题 算法训练 进击的青蛙
对于进击的青蛙的算法训练,可以提供一些思路和解法:
问题描述:有一只青蛙在跳台阶,它一次可以跳1个台阶或者2个台阶。请问,对于给定的n个台阶,青蛙有多少种跳法可以跳到第n个台阶上?
解法一:递归
青蛙跳到第n个台阶上的跳法数量,可以看成是青蛙从第n-1个台阶跳一步到达的跳法数量加上青蛙从第n-2个台阶跳两步到达的跳法数量,即f(n) = f(n-1) + f(n-2)。
使用递归的方式,可以编写如下的算法:
```python
def jump(n):
if n <= 2:
return n
else:
return jump(n-1) + jump(n-2)
```
这种方法虽然直观简单,但是存在大量的重复计算,效率较低。
解法二:动态规划
为了避免重复计算,可以使用动态规划的思想来解决问题。通过一个数组dp来保存中间结果,dp[i]表示青蛙跳到第i个台阶上的跳法数量。
初始条件为dp = 0,dp = 1,dp = 2。然后通过迭代计算出dp[i]的值,最后返回dp[n]即可。
具体的算法如下:
```python
def jump(n):
if n <= 2:
return n
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
```
这种方法时间复杂度为O(n),空间复杂度也为O(n)。
解法三:优化的动态规划
可以发现,解法二中的动态规划算法实际上只需要用到了三个变量,因此可以进一步优化空间复杂度。
具体的算法如下:
```python
def jump(n):
if n <= 2:
return n
a, b, c = 1, 2, 0
for i in range(3, n+1):
c = a + b
a, b = b, c
return c
```
这种方法的时间复杂度仍然为O(n),但是空间复杂度为O(1)。
以上就是几种解决进击的青蛙问题的算法训练方法,希望对你有帮助。