华为OD-猴子爬山（解题思路+代码）
猴子爬山
题目描述
一天一只顽猴想要从山脚爬到山顶，途中经过一个有n个台阶的阶梯，，每一次只跳1步或3步，猴子通过这个阶梯有多少种不同的跳跃方式？
输入描述
输入只有一个数n， 0 < n < 50，代表此阶梯有多个台阶
输出描述
有多少种跳跃方式
示例：
#样例输入：
30
#样例输出：
58425
解题思路：
1.首先探索f[k]递推关系：
设n = 30 ,上山到最后一步30级台阶，完成上山。完成30级台阶共有f[30]种方法：那么到达f[30]前位于哪一级呢？第一种位于29级（上跳1级完成），第二种位于27级（上跳3级完成）于是有：
f[30] = f[29] + f[27]
以此类推，有递推关系：
f[k] = f[k -1] + f[k-3]
2.确定初始条件：
f[1] = 1 即 1=1
f[2] = 1 即 2 = 1+ 1
f[3] = 2 即 3 = 1 + 1+1 或者 3 = 3
3.实施递推：
根据以上地推关系和初始条件，设置一重循环使用递推即可求出f[n]。
#!E:pythonScriptvenv python3
# -*- coding: utf-8 -*-
"""
Date: 2023/3/8
Time: 16:08
Author: kang
"""
def fun(k):
if k == 1 or k == 2:
return 1
elif k == 3:
return 2
else:
return fun(k - 1) + fun(k - 3)
if __name__ == "__main__":
n = int(input())
print(fun(n)) 猴子爬山 题目描述 一天一只顽猴想要从山脚爬到山顶，途中经过一个有n个台阶的阶梯，，每一次只跳1步或3步，猴子通过这个阶梯有多少种不同的跳跃方式？ 输入描述 输入只有一个数n， 0 < n < 50，代表此阶梯有多个台阶 输出描述 有多少种跳跃方式 示例： #样例输入： 30 #样例输出： 58425 解题思路： 1.首先探索f[k]递推关系： 设n = 30 ,上山到最后一步30级台阶，完成上山。完成30级台阶共有f[30]种方法：那么到达f[30]前位于哪一级呢？第一种位于29级（上跳1级完成），第二种位于27级（上跳3级完成）于是有： f[30] = f[29] + f[27] 以此类推，有递推关系： f[k] = f[k -1] + f[k-3] 2.确定初始条件： f[1] = 1 即 1=1 f[2] = 1 即 2 = 1+ 1 f[3] = 2 即 3 = 1 + 1+1 或者 3 = 3 3.实施递推： 根据以上地推关系和初始条件，设置一重循环使用递推即可求出f[n]。 #!E:pythonScriptvenv python3 # -*- coding: utf-8 -*- """ Date: 2023/3/8 Time: 16:08 Author: kang """ def fun(k): if k == 1 or k == 2: return 1 elif k == 3: return 2 else: return fun(k - 1) + fun(k - 3) if __name__ == "__main__": n = int(input()) print(fun(n))
下一篇：
项目如何进行压力测试？