通往楼梯顶部的可能路径 [英] possible paths to the top of a staircase

问题描述

这是一个非常经典的问题，我听说谷歌在他们的面试中使用了这个问题.

This is a pretty classic question, and I've heard Google has used this question in their interviews.

问题:制作一个递归方法，打印从楼梯底部到楼梯顶部的所有可能的独特方式，有 n 个楼梯.您一次只能走 1 步或 2 步.

Problem: Make a recursive method that prints all the possible unique ways from the base of a staircase to the top of the staircase with n stairs. You can only take 1-step or 2-steps at a time.

示例输出:如果是3个楼梯的楼梯...

Sample output: If it is a staircase with 3 stairs...

1 1 1

2 1

1 2

如果是4个楼梯的楼梯...

If it is a staircase with 4 stairs...

1 1 1 1

1 1 2

1 2 1

2 1 1

2 2

*输出顺序无关紧要

我在这里看到过类似的问题，但他们都要求提供路径总数.这种递归方法需要打印出所有可能的路径.这里唯一的限制是您必须在方法的某处使用递归.如果需要，您可以使用 1 种以上的方法.

I've seen similar questions posted here but all of them asked for the total number of paths. This recursive method needs to print out all the possible paths. The only restriction here is that you must use recursion somewhere in the method. You can use more than 1 method if you want.

推荐答案

好吧，如果您还剩 0 个楼梯，那么您已经到了尽头；如果您还有 1 个楼梯，则下一步只能是 1 号楼梯；如果前面有更多楼梯，下一步可能是 1 或 2 楼梯，因此递归变得非常简单:

Well, if you have 0 stair left, you've reached the end; if you have 1 more stair, next move can be only of size 1; if you have more stairs ahead, next move may be 1 or 2 stairs, so recursion becomes quite simple:

void makeSteps(List<Integer> prevSteps, int s) {
    if (s == 0) {                        // no more stairs left
        System.out.println(prevSteps);
    } else {                             // 1 or more stairs left
        List<Integer> n1 = new ArrayList<>(prevSteps);
        n1.add(1);
        makeSteps(n1, s - 1);
        if (s > 1) {                     // 2 or more stairs left
            List<Integer> n2 = new ArrayList<>(prevSteps);
            n2.add(2); 
            makeSteps(n2, s - 2);
        }           
    }
}

prevSteps 表示上一条路径，s 表示剩下的楼梯数.要打印 n 步楼梯的所有可能方式，请调用:

prevSteps represents previous path, s stores number of stairs left. To print all possible ways for n-step stairs, call:

makeSteps(new ArrayList<>(), n);

很容易将这段代码重构为更通用的形式，其中可能的步长不仅可以是 1 或 2，还可以是maxStep 以内的任意数字:

Very easily this code can be refactored into more generalized form, where possible step size can be not only 1 or 2, but any number up to maxStep:

void makeSteps(List<Integer> prevSteps, int s, int maxStep) {
    if (s == 0) {                        // no more stairs left
        System.out.println(prevSteps);
    } else {                             // 1 or more stairs left
        for (int step = 1; step <= Math.min(maxStep, s); step++) {
            List<Integer> newSteps = new ArrayList<>(prevSteps);
            newSteps.add(step);
            makeSteps(newSteps, s - step, maxStep);
        }           
    }
}

要获得相同的结果，请使用第三个参数调用它:

To receive the same result, call it with the third argument:

makeSteps(new ArrayList<>(), 4, 2);

这篇关于通往楼梯顶部的可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！