1 + 2的所有组合加到n [英] All combinations of 1 + 2 that adds to n

问题描述

在尝试进行编程面试时，我正在尝试解决这个问题：

I am trying to solve this question as the preparation for a programming interview:

青蛙只会向前移动，但是它可以向前移动步长为1英寸，跳跃为2英寸。青蛙可以使用不同的步距和跳跃组合来覆盖相同的距离。

A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

编写一个函数，该函数计算青蛙可以用于覆盖给定距离的不同组合的数量。

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

例如，可以通过三种方式来覆盖3英寸的距离：逐步，跳跃和跳跃。

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.

我认为有一个非常简单的解决方案，但我似乎找不到。我想使用递归，但是看不到。这是我到目前为止所拥有的：

I think there is a quite simple solution to this, but I just can't seem to find it. I would like to use recursion, but I can't see how. Here is what I have so far:

public class Frog {

    static int combinations = 0;
    static int step = 1;
    static int jump = 2;
    static int[] arr = {step, jump};

    public static int numberOfWays(int n) {
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            sum += arr[i];
            System.out.println("SUM outer loop: " + sum + " : " + arr[i]);
            while (sum != 3) {
                for (int j = 0; j < arr.length; j++) {
                    if (sum + arr[j] <= 3) {
                        sum += arr[j];
                        System.out.println("SUM inner loop: " + sum + " : " + arr[j]);
                        if (sum == 3) {
                            combinations++;
                            System.out.println("Combinations " + combinations);
                        }
                    }
                }
            }
        }
        return combinations;
    }

    public static void main(String[] args) {
        System.out.println(numberOfWays(3));
    }
}

它没有找到所有组合，我认为代码很糟糕。任何人都可以很好地解决这个问题吗？

It doesn't find all combinations, and I think the code is quite bad. Anyone have a good solution to this question?

推荐答案

认为您有一个知道如何解决较小问题的预言家，您只需要提供它即可较小的问题。这是递归方法。

Think you have an oracle that knows how to solve the problem for "smaller problems", you just need to feed it with smaller problems. This is the recursive method.

在您的情况下，通过拆分可能的移动来解决 foo（n）青蛙可以在最后一步中完成并求和）：

In your case, you solve foo(n), by splitting the possible moves the frog can do in the last step, and summing them):

foo(n) = foo(n-1) + foo(n-2)
            ^         ^
         1 step    2 steps

此外，您需要一个 foo（0）= 1，foo（1）= 1 （一种移动0或1英寸的方法）的stop子句。

In addition, you need a stop clause of foo(0) = 1, foo(1)=1 (one way to move 0 or 1 inches).

这个递归公式看起来很熟悉吗？您能比单纯的递归解决方案更好地解决它吗？

Is this recursive formula looks familiar? Can you solve it better than the naive recursive solution?

扰流器：

^{_{斐波那契数列}}

这篇关于1 + 2的所有组合加到n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！