递归问题-给定数组n和数字k

Question

给定一个数组大小n和一个正数max（max表示我们可以用来放置在数组中的数字范围）。

我想计算我可以在数组中放置多少个排序数字的组合。

例如：

如果n=3，则最大值为2。（我们只能使用1/2的数字，因为最大值是2）因此有4种排序数组组合

 1. {1,1,1}
 2. {1,1,2}
 3. {1,2,2}
 4. {2,2,2}

我编写了一些代码，并成功地通过了这个特定的示例，但任何其他示例

我发现的问题是，当递归到达最后一个索引时，它不会尝试第三个数字，而是向后折叠。

我的代码：

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {        
    // If the value is bigger then max return 0
    if(numToMax > max) {
        return 0;
    }
    if (numToMax < prevNum) {
        return 0;
    }
    //If Index reached the end of the array return 1
    if(index == n) {
        return 1;
    }

    int sortTwo =  howManySorted(n, max, index+1, numToMax, numToMax);
    int sortOne =  howManySorted(n, max, index+1, numToMax+1, numToMax);
    return ((sortOne+sortTwo));
}

public static int howManySorted(int n, int max) {
    return howManySorted(n, max, 0, 1, 0);
}

Answer 1

我相信你可以简化你对这类问题的回答

private static long howManySorted(int length, int min, int max) {
    if (length == 1) {
        return max - min + 1;
    }

    // if (min == max) {
    //    return 1;
    // }

    long result = 0;
    for (int i = min; i <= max; i++) {
        result += howManySorted(length - 1, i, max);
    }
    return result;
}

public static long howManySorted(int length, int max) {
    if ((length < 1) || (max < 1)) {
        throw new IllegalArgumentException();
    }

    return howManySorted(length, 1, max);
}

客户端应该调用public方法。

如您所见，终止条件是剩余长度为1，或最小值达到最大值。即使删除第二个终止条件也不会改变结果，但可以提高性能和递归次数。

Answer 2

我认为您需要更改两个递归调用（这就是为什么它只达到值2），并执行与您的max参数一样多的调用：

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {
    // If the value is bigger then max return 0
    if (numToMax > max) {
        return 0;
    }
    if (numToMax < prevNum) {
        return 0;
    }
    //If Index reached the end of the array return 1
    if (index == n) {
        return 1;
    }

    int result = 0;
    for (int i = 0; i < max; i++)
        result += howManySorted(n, max, index + 1, numToMax + i, numToMax);

    return result;
}

Answer 3

从“{1”开始，在每个递归中添加元素“{1,1”和/或值“{2”。当它到达n个元素数组时，我们将其添加到计数器。n是数组中的元素数max是每个元素的最大值。minimal是1。element是数组中被操作的当前单元格。我们从1开始（在实际数组中表示0）。value是当前元素的当前值。我们从1开始。

// external function according to the given question
public static int count (int n, int max) 
{
    return count(n,max, 1, 1);
}

private static int count (int n, int max, int element, int value) 
{
    int counter = 0;
    // only if our array reached n elements we count the comination
    if (element == n) 
        counter++;
    else // we need to continue to the next element with the same value
        counter += count(n, max, element +1, value);
    if (value < max) // if our current element didn't reach max value
        counter += count (n, max, element, value+1); 
    return counter;
}