给定一个数组大小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);
}
我相信你可以简化你对这类问题的回答
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,或最小值达到最大值。即使删除第二个终止条件也不会改变结果,但可以提高性能和递归次数。
我认为您需要更改两个递归调用(这就是为什么它只达到值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;
}
从“{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;
}
给定一个2d数组,我需要返回一个具有路径的矩阵,该路径递归地求和到给定的数字。 路径矩阵应为零,但总计为给定数字的路径除外,该路径将标记为1。 路径只能在 我尝试过所有的可能性,首先检查我是否已经去过下一个街区。 问题是在一些迭代之后,它会停止,并且不会返回并再次将块清除为0。 给定 在通话中 我以为算法会回来 我得到 相反 调用paintPath(mat1400,path,0,0);我想 或 问
我遇到的问题如下: 对于给定的不同十进制数字数组(0,1,2,3...,8,9)编写一个递归函数,返回由给定数字组成的所有自然数的总和。例如,对于数组{1,2},您将获得12 21 2 1 = 36 我想的是如果你有一个数组1,2,3 您可以将最后一个数字“放在一边”,并将剩下的较小的一组按如下方式排列: 1 2 3 2 1 3 2 3 1 3 3 这将是10*[perm(1,2)]3*(重复次数
我正在编写一个递归函数,如下所示: 此函数用于接收员工并查找其管理者。如果找到管理器,则将管理器id推送到数组中($)- 所以我的问题是,如果我不在第6行返回递归调用(这是-
我是Java新手,正在尝试用Java编写n choose k。然而,我遇到了一个问题。 输出:这方面的许多迭代: 如果有人能帮忙,我将不胜感激。
我有一个很难处理的任务。 我试图编写一个递归函数(完全没有循环),给定一个数组及其长度,它将打印一对子数组,每个子数组的和将是整个数组和的一半。换句话说,数组被分成两组整数,以便它们的和相等。 例如,给定数组{1,2,2,0,5},函数应输出{1,2,2}{0,5} 我必须递归地做,用一个只得到数组本身及其大小的函数。我也只允许使用一个额外的递归函数来解决这个问题。 任何想法或想法都将受到最大的赞
我正在编写一个python类来寻找8皇后问题的解决方案。如何在方法中正确实现回溯?我认为递归应该可以工作,但是,程序在第一次尝试没有找到解决方案后停止,回溯也不会发生。所有helper方法都能正常工作。 我的问题是在添加女王之前缺少一个板子的深度副本,还是仅仅是缺少回溯?