《剑指offer》刷题笔记（递归和循环）：变态跳台阶

Bertha 。 2022-06-09 13:48 109阅读 0赞

# 《剑指offer》刷题笔记（递归和循环）：变态跳台阶 #

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/AtOffer][https_github.com_WordZzzz_Note_tree_master_AtOffer]**
 *  **刷题平台：[https://www.nowcoder.com/][https_www.nowcoder.com]**
 *  **题  库：剑指offer**
 *  **编  者：WordZzzz**

--------------------

*  剑指offer刷题笔记递归和循环变态跳台阶
    
     *  题目描述
     *  解题思路
     *  C版代码实现
        
         *  递归
         *  循环
         *  移位
     *  Python 代码实现
        
         *  递归
         *  循环
         *  移位

## 题目描述： ##

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

## 解题思路： ##

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级  
跳1级，剩下n-1级，则剩下跳法是f(n-1)  
跳2级，剩下n-2级，则剩下跳法是f(n-2)  
所以f(n)=f(n-1)+f(n-2)+…+f(1)  
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)  
所以f(n)=2\*f(n-1)

实现f(n)=2\*f(n-1)的方法有很多种，递归、循环都可以。

## C++版代码实现： ##

### 递归： ###

class Solution {
    public:
        int jumpFloorII(int number) {
            if(number <= 0){
                return -1;
            }else if(number == 1){
                return 1;
            }else{
                return 2 * jumpFloorII(number -1);
            }
        }
    };

### 循环： ###

class Solution {
    public:
        int jumpFloorII(int number) {
            if(number == 0)
                return number;
            int total=1;
            for(int i=1; i<number; i++)
                total *= 2;
            return total;
        }
    };

### 移位： ###

class Solution {
    public:
        int jumpFloorII(int number) {
            return 1<<--number;
        }
    };

## Python 代码实现： ##

### 递归： ###

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number <= -1:
                return -1
            elif number == 1:
                return 1
            else:
                return 2*self.jumpFloorII(number-1)

### 循环： ###

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number == 0:
                return number
            total = 1
            for i in range(number-1):
                total *= 2
            return total

### 移位： ###

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            return 1<<(number-1);

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_Note_tree_master_AtOffer]: https://github.com/WordZzzz/Note/tree/master/AtOffer
[https_www.nowcoder.com]: https://www.nowcoder.com/