当前位置:网站首页>青蛙跳台阶(递归和非递归)-------小乐乐走台阶
青蛙跳台阶(递归和非递归)-------小乐乐走台阶
2022-07-30 19:29:00 【果辰辰果】
小青蛙跳台阶
一、 问题描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法???
二、分析问题
当n=1时,有一种跳法
当n=2时,有两种跳法
1.跳一级,跳一级
2.跳两级
当n=3时,有三种跳法
1.跳一级,跳一级,跳一级
2.跳一级,跳两级
3.跳两级,跳一级
先假设f(n)为 n 级台阶的总跳法数;
那么第一次如果选择跳一级的话,剩下的 n-1 级台阶的跳法数就为f(n−1)。
如果第一次跳两级的话,剩下的 n-2 级台阶的跳法就是f(n−2);
所以,当有n个台阶时有f(n)=f(n-1)+f(n-2)种跳法。
三、代码实现(递归)
#include<stdio.h>
int steps(int x)
{
if (x == 1)
{
return 1;
}
if (x == 2)
{
return 2;
}
return steps(x - 1) + steps(x - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", steps(n));
return 0;
}
四、代码实现(非递归)
#include<stdio.h>
int steps(int x)
{
if (x < 3)
{
return x;
}
int final1 = 1;//倒数第一个跳法
int final2 = 2;//倒数第二个跳法
int sum = 0;//计算一共多少种
for (int i = 3; i <= x; i++)
{
sum = final1 + final2;
final1 = final2;
final2 = sum;
}
return sum;
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", steps(n));
return 0;
}
边栏推荐
- Swiper rotates pictures and plays background music
- After watching "Second Uncle", I was even more internalized
- 防抖和节流有什么区别,分别用于什么场景?
- Start foreground Activity
- Witness the magical awakening of the mini world in HUAWEI CLOUD
- 看完《二舅》,我更内耗了
- Difference between Object and Map
- 自己需要努力
- - daily a LeetCode 】 【 191. A number of 1
- MindSpore:【resnet_thor模型】尝试运行resnet_thor时报Could not convert to
猜你喜欢
Download Win11 how to change the default path?Download Win11 change the default path method
What is the difference between a cloud database and an on-premises database?
Delay queue optimization (2)
MindSpore:【模型训练】【mindinsight】timeline的时间和实际用时相差很远
VBA批量将Excel数据导入Access数据库
Swiper rotates pictures and plays background music
MySQl数据库————DQL数据查询语言
SimpleOSS第三方库libcurl与引擎libcurl错误解决方法
Spark学习:用spark实现ETL
Perfectly Clear QuickDesk & QuickServer图像校正优化工具
随机推荐
MindSpore:【MindSpore1.1】Mindspore安装后验证出现cudaSetDevice failed错误
The advanced version of the Niu Ke brushing series (team competition, sorting subsequences, inverting strings, deleting common characters, repairing pastures)
Does the satellite phone communicate directly with the satellite or through a ground station?
【刷题篇】计算质数
云数据库和本地数据库有什么区别?
Golang logging library zerolog use record
部分分类网络性能对比
C# wpf borderless window add shadow effect
牛客刷题系列之进阶版(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)
musicApp 的.eslintrc.js
卫星电话是直接与卫星通信还是通过地面站?
MySQL分库分表
How architects grow
Correct pose of Vulkan open feature
Zabbix 5.0 监控教程(一)
MindSpore:ImageFolderDataset数据读取问题
MySql中@符号的使用
电脑死机的时候,发生了什么?
iPhone真是十三香?两代产品完全对比,或许上一代更值得买
来了!东方甄选为龙江农产品直播带货