這題是用C寫的~
在牛客上半天找不著ACM模式,練習模式里只有核心代碼模式
這樣用C語言編譯器就不能自定義函數(shù)啊,不雞肋嗎???
解決方法:在核心代碼模式下用C++編譯器(反正C++完全兼容C的不是嗎~~)
但是這樣并不好,很氣!

---

題目描述

描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）。

示例1
輸入：

2

返回值：

2

示例2
輸入：

7

返回值：

21

---

解題思路

• 簡單遞歸,別說青蛙跳臺階了,兔子下樓也是一樣的
• 理解遞歸的思想很重要,至于什么是遞歸這里不多贅述(自行百度)
• 常見的遞歸:斐波那契數(shù)列(1,1,2,3,5,8,13…)
• 本題也是斐波那契哦~
• 在遞歸時,往往需要自己調(diào)用自己,判斷好停止時機很重要
• 理解什么時候sum++:撞墻(搜索到頭了)表示你已經(jīng)走出了一條路,此時sum++
• sum表示路徑數(shù)量
• 如果還不會,建議畫圖,本題是一個標準的二叉樹,還是滿二叉樹,數(shù)葉子結(jié)點的個數(shù)
• 一般遞歸都是數(shù)葉子結(jié)點的個數(shù),如果不好理解自己調(diào)用自己,可以去理解一下二叉樹
• 當然我給出的題解是用遞歸做的,但是你如果觀察除了斐波那契,那肯定是直接斐波那契時間復雜度低啊! 用一個數(shù)組存一串斐波那契,返回第n項a[n]就很完美了,保證AC
• 公式:求第n個斐波那契數(shù)
  
• 如果你想快速得到一個存有斐波那契數(shù)列的數(shù)組,用一個for循環(huán)不就可以搞定了么?時間復雜度O(n),真香啊!

---

題解

我的代碼(完整版)

#include<stdio.h>
#include<math.h>int sum = 0;
void jump(int step, int number)
{if (step >= number){sum++;return;}else{jump(step + 1, number);if (step + 2 <= number)jump(step + 2, number);}return;
}int jumpFloor(int number )
{sum = 0;jump(0, number);return sum;
}int main()
{// for testprintf("%d", jumpFloor(7));return 0;
}

在牛客上提交時的代碼(真的無力吐槽了)

總結(jié)

以上是生活随笔為你收集整理的[递归]一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。