【C语言刷题】青蛙跳台阶

简介: 【C语言刷题】青蛙跳台阶

一、问题描述

一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

二、问题分析

青蛙跳台阶,相信大家一开始看到这道题也是没有一点思路,但是不要担心,相信自己一定能解决这道经典题目的。

这道题我们无法直接肉眼观察出一些规律,但是我们有数学归纳法,直接看不出来,我们先写三项,三项看不出来,我们写五项,写的多了总会看出来的。

1.当n=1时

显然只有1级台阶,那么肯定只有一种跳法了。

2.当n=2时

这个时候我们有两种跳法,一种是直接跳两级,另外一种是先跳一级,再跳一级。

3.当n=3时

这个时候我们的选择可就多了,单纯的打字打出来并不是一种明智的选择,我们画一个图试试看

青蛙第一次可以选择跳一层,也可以第一次跳两层,为了方便起见,不妨我们定义青蛙跳n层台阶共有f(n)种跳法

那么f(3)就有如下图所示,第一次跳1或者2,如果是1,则第二次继续跳1,或者2,如果第一次是2,那么直接跳1即可

4.n=4,n=5........n=n时

其实在这块已经有人能看到规律了,因为第一步无非就两种跳法,要么跳1,要么跳2。如果假设n个台阶有f(n)种跳法。那么则第二步有f(n-1)和f(n-2)种跳法。然后我们就发现,这不就是斐波那契数列吗。只不过就是把第二项变为2了。其余一个都没变

事实上,确实是这样的,这道题规律是比汉诺塔要好找很多的。

三、代码实现

既然本质上上就是一个斐波那契数列求第n项,只不过是第二项变为2了这种情况。那么问题迎刃而解,斐波那契数列在之前的文章中花费了大量的篇幅去详细讲解,这里给出传送门:http://t.csdn.cn/Khk31

我们直接实现代码吧

#include<stdio.h>
int f(int n)
{
  if (n == 1)
  {
    return 1;
  }
  else if (n == 2)
  {
    return 2;
  }
  else
  {
    return f(n - 1) + f(n - 2);
  }
}
int main()
{
  int n;
  scanf("%d", &n);
  int ret = f(n);
  printf("%d", ret);
  return 0;
}

总结

好了本期内容就讲解这么多,青蛙跳台阶和汉诺塔问题有点类似,都是需要透过现象看本质。寻找规律,从而一举制胜。

相关文章
|
27天前
|
C语言
【C语言刷题系列】合并两个有序数组
【C语言刷题系列】合并两个有序数组
|
27天前
|
C语言
【C语言刷题系列】删除公共元素
【C语言刷题系列】删除公共元素
|
27天前
|
存储 C语言
【C语言刷题系列】对数字添加逗号
【C语言刷题系列】对数字添加逗号
|
27天前
|
C语言
【C语言刷题系列】喝汽水问题
【C语言刷题系列】喝汽水问题
|
27天前
|
存储 C语言
【C语言刷题每日一题#牛客网HJ73】——计算日期到天数转换(给定日期,计算是该年的第几天)
【C语言刷题每日一题#牛客网HJ73】——计算日期到天数转换(给定日期,计算是该年的第几天)
|
27天前
|
C语言
【C语言刷题每日一题#牛客网BC6】输入三个整数,输出第二个整数
【C语言刷题每日一题#牛客网BC6】输入三个整数,输出第二个整数
|
26天前
|
C语言
C语言刷题(函数)
C语言刷题(函数)
|
26天前
|
C语言
C语言刷题(数组)
C语言刷题(数组)
|
27天前
|
C语言
【C语言刷题每日一题】一维数组的交换
【C语言刷题每日一题】一维数组的交换
|
27天前
|
存储 C语言
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m