原文:

给定一个正整数 n 代表 n 楼梯和一个人它在第一个楼梯，任务是打印所有到达 n 第楼梯的方式，一次跳转 1 或 2 个单位。

示例:

输入: n = 3 输出: 112* 说明:*第 n 级楼梯可通过以下方式到达，每级跳 1 或 2 个单位为:

  1. 执行 1 个单位的两次跳跃，每次为 1 -> 1。
  2. 执行两次跳跃，每次 1 个单位，作为 2。

输入:n = 5 t5】输出: 1111 112 121 211 22

方法:给定的问题可以使用来解决。这个想法是涵盖每次一两次跳跃的情况，并打印所有可能到达nthstage的方法。按照以下步骤解决给定的问题:

  • 定义一个递归函数，比如total 可能性跳跃(int n) ，返回所有可能的跳跃方式到达 n 第级。
    • 在递归的起点，检查基本情况如下:
      • 如果 n < 0 ，那么就不是有效的方式。所以返回一个空数组
      • 如果 n = 0 ，则是有效方式。所以返回一个包含一个空白空间的大小为 1 的数组。
    • 每次递归调用两次，一次用于 1 单元跳转，另一次用于 2 单元跳转，并分别存储结果。
    • 初始化一个字符串的
  • 完成上述步骤后，将上述递归调用返回的所有可能的组合打印为total 可能性跳转(n) 。

下面是上述方法的实现:

c 

// c   program for the above approach
#include 
using namespace std;
// function to find all the ways to reach
// nth stair using one or two jumps
vector totalpossiblejumps(int n)
{
    // base cases
    if ((n - 1) == 0) {
        vector newvec;
        newvec.push_back("");
        return newvec;
    }
    else {
        if (n < 0) {
            vector newvec;
            return newvec;
        }
    }
    // recur for jump1 and jump2
    vector jump1
        = totalpossiblejumps(n - 1);
    vector jump2
        = totalpossiblejumps(n - 2);
    // stores the total possible jumps
    vector totaljumps;
    // add "1" with every element
    // present in jump1
    for (string s : jump1) {
        totaljumps.push_back("1"   s);
    }
    // add "2" with every element
    // present in jump2
    for (string s : jump2) {
        totaljumps.push_back("2"   s);
    }
    return totaljumps;
}
// driver code
int main()
{
    int n = 3;
    vector ans = totalpossiblejumps(n);
    for (auto& it : ans)
        cout << it << '\n';
    return 0;
}

java 语言(一种计算机语言，尤用于创建网站)

// java program for the above approach
import java.util.*;
class gfg {
    // function to find all the ways to reach
    // nth stair using one or two jumps
    static arraylist totalpossiblejumps(int n)
    {
        // base cases
        if ((n - 1) == 0) {
            arraylist newvec
                = new arraylist();
            newvec.add("");
            return newvec;
        }
        else {
            if (n < 0) {
                arraylist newvec
                    = new arraylist();
                return newvec;
            }
        }
        // recur for jump1 and jump2
        arraylist jump1 = totalpossiblejumps(n - 1);
        arraylist jump2 = totalpossiblejumps(n - 2);
        // stores the total possible jumps
        arraylist totaljumps
            = new arraylist();
        // add "1" with every element
        // present in jump1
        for (string s : jump1) {
            totaljumps.add("1"   s);
        }
        // add "2" with every element
        // present in jump2
        for (string s : jump2) {
            totaljumps.add("2"   s);
        }
        return totaljumps;
    }
    // driver code
    public static void main(string[] args)
    {
        int n = 3;
        arraylist ans = totalpossiblejumps(n);
        for (string it : ans)
            system.out.println(it);
    }
}
// this code is contributed by ukasp.

python 3

# python program for the above approach
# function to find all the ways to reach
# nth stair using one or two jumps
def totalpossiblejumps(n):
    # base cases
    if ((n - 1) == 0):
        newvec = []
        newvec.append("")
        return newvec
    else:
        if (n < 0):
            newvec = []
            return newvec
    # recur for jump1 and jump2
    jump1 = totalpossiblejumps(n - 1)
    jump2 = totalpossiblejumps(n - 2)
    # stores the total possible jumps
    totaljumps = []
    # add "1" with every element
    # present in jump1
    for s in jump1:
        totaljumps.append("1"   s)
    # add "2" with every element
    # present in jump2
    for s in jump2:
        totaljumps.append("2"   s)
    return totaljumps
# driver code
if __name__ == "__main__":
    n = 3
    ans = totalpossiblejumps(n)
    for it in ans:
        print(it)
    # this code is contributed by rakeshsahni

c

// c# program for the above approach
using system;
using system.collections.generic;
class gfg{
// function to find all the ways to reach
// nth stair using one or two jumps
static list totalpossiblejumps(int n)
{
    // base cases
    if ((n - 1) == 0) {
        list newvec = new list();
        newvec.add("");
        return newvec;
    }
    else {
        if (n < 0) {
            list newvec = new list();
            return newvec;
        }
    }
    // recur for jump1 and jump2
    list jump1
        = totalpossiblejumps(n - 1);
    list jump2
        = totalpossiblejumps(n - 2);
    // stores the total possible jumps
    list totaljumps = new list();
    // add "1" with every element
    // present in jump1
    foreach (string s in jump1) {
        totaljumps.add("1"   s);
    }
    // add "2" with every element
    // present in jump2
    foreach (string s in jump2) {
        totaljumps.add("2"   s);
    }
    return totaljumps;
}
// driver code
public static void main()
{
    int n = 3;
    list ans = totalpossiblejumps(n);
    foreach(string it in ans)
        console.writeline(it);
}
}
// this code is contributed by surendra_gangwar.

java 描述语言

output: 

11
2

时间复杂度:o(2n) t5】辅助空间: o(n)

麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处

本文链接：http://www.moonapi.com/news/38469.html