一笑而过2222
2024-10-17 09:22 中山大学 测试工程师
关注
一、确定初始状态
当井高为 1 米时，青蛙只有一种跳法，即一天直接跳 1 米到达井口，所以 f(1)=1。
当井高为 2 米时，青蛙可以一天跳 2 米直接出来，或者分两天每天跳 1 米，这两种情况构成了跳上 2 米高井的所有方法，所以 f(2)=2。
二、推导递推关系
对于井高 n>2 的情况，考虑青蛙最后一步的跳法。
如果最后一步跳 1 米，那么前面 n - 1 米的跳法数量就是 f(n - 1)，因为最后一步确定了，只需要考虑前面 n - 1 米的跳法。
如果最后一步跳 2 米，那么前面 n - 2 米的跳法数量就是 f(n - 2)，同理最后一步确定为跳 2 米，只需要考虑前面 n - 2 米的跳法。
所以总的跳法数量 f(n)就是前面两种情况的和，即 f(n)=f(n - 1)+f(n - 2)。
三、计算 f(100)
依次计算 f(3)=f(2)+f(1)=2 + 1 = 3。
f(4)=f(3)+f(2)=3 + 2 = 5。
以此类推，逐步计算下去，直到计算出 f(100)，就能得到青蛙跳出 100 米井的方法数。
查看原帖
2 评论
相关推荐
点赞 评论 收藏
分享
查看16道真题和解析
04-16 03:09
中国地质大学（武汉） Java 
小浪_Coding：干程序员就不能怕被裁
一家公司一般待不会超过三年,就要跳槽的,大龄之后的岗位基本都不好找,目前找一份薪资还OK的工作就不错了. 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 商战，最累的是我们 #
717次浏览 11人参与
# 租房找室友 #
16814次浏览 107人参与
# 学历or实习经历，哪个更重要 #
100085次浏览 708人参与
# 深信服求职进展汇总 #
180439次浏览 1670人参与
# 你上一次加班是什么时候？ #
52506次浏览 368人参与
# 大疆求职进展汇总 #
480986次浏览 3197人参与
# 产品面经 #
170183次浏览 1895人参与
# 秋招想进国企该如何准备 #
51819次浏览 352人参与
# 你觉得通信/硬件有必要实习吗？ #
100624次浏览 898人参与
# 市场营销人求职交流聚集地 #
109658次浏览 1007人参与
# 实习要如何选择和准备？ #
60962次浏览 988人参与
# 摸鱼被leader发现了怎么办 #
51773次浏览 323人参与
# 秋招最大的收获是什么？ #
25791次浏览 275人参与
# 研究所笔面经互助 #
65419次浏览 430人参与
# 如果可以，你希望哪个公司来捞你 #
72913次浏览 314人参与
# 找工作，行业重要还是岗位重要？ #
30655次浏览 518人参与
# 2023届毁约公司名单 #
186359次浏览 935人参与
# 哪些公司面试官让你印象深刻？ #
252250次浏览 2651人参与
# 米哈游工作体验 #
12754次浏览 103人参与
# 秋招签约后的心态变化 #
75472次浏览 791人参与