递归问题 - 给定数组 n 和数字 k [英] Recursion Problem - given array n and a number k

问题描述

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

Given an array size n, and a positive number max(max represent the range of the numbers that we can use to place in the array).

我想计算可以在数组中放置多少种排序数字组合.

I would like to count how many combinations of sorted numbers I can place in the array.

例如:

如果n = 3，max = 2.(我们唯一可以使用的数字是1/2，因为max是2)所以排序数组有4种组合

If n = 3, max = 2.(the only numbers we can use is 1/2 as max is 2) so there are 4 combinations of sorted arrays

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

我写了一些代码并成功通过了这个特定的例子，但是任何其他例子 max >2 没有返回正确答案.

I wrote some code and succeed to pass this specific example but any other example that max > 2 doesn't return the correct answer.

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

the problem as I identify it is when the recursion reaches the last index it doesn't try a third number it just folds back.

我的代码:

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);
}

推荐答案

以{1"开头，并在每次递归时添加元素{1,1"和/或值{2".当它到达 n 个元素数组时，我们将其添加到计数器中.n 是数组中的元素数 max 是每个元素的最大值.最小为 1. element 是正在操作的数组中的当前单元格.我们从 1 开始(在实际数组中意味着 0).value 是当前元素的当前值.我们从 1 开始.

start with "{1," and add elements "{1,1" and/or value "{2," with each recursion. when it reach n elements array we add to the counter. n is the number of elements in the array max is the maximal value for each element. minimal is 1. element is the current cell in the array being manipulated. we start with 1 (in actual array means 0). value is the current value of the current element. we start with 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;
}

这篇关于递归问题 - 给定数组 n 和数字 k的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！