所以练习是:
仅使用递归(无循环)
查找是否存在等于数组中给定数字的子地面,并遵循规则。
假设我有一个数组,我给予函数一个求和的数字,它必须遵守这个规则:你不能重复相同的数字,你不能在一行中对3个数字求和(不能做i+1和i+2)
int[] a = {5,4,2,1,3};
因此,在本例中:num 8 = true(4+3+1)(5+3)num 11 = false(4+5+2是3,但在一行中是三个)(5+2+1+3也是三个在一行中)
我的尝试是:
public static boolean sumRule(int[] a , int num){
if (num == 0){
return true;
} else {
return sumRule(a,num,0,a.length);
}
}
private static boolean sumRule(int[] a, int num, int low,int high){
if(low >= high || low < 0){
return false;
}
if (a[low] == -1){
return false;
}
if(a[low] == num || num-a[low] == 0 ){
return true;
}
int temp = a[low];
a[low] = -1;
return sumRule(a,num,low,high) || sumRule(a,num-temp,low+3,high) || sumRule(a,num-temp,low+1,high) ;
}
但是当我发送11到这个,它仍然返回true,有人知道我在这里错过了什么吗?
谢啦
4条答案
按热度按时间6kkfgxo01#
下面是完整的代码答案,下面是解释:
本质上,你需要把这个问题分解成一个递归问题,也就是说,你在每一步都要考虑选择(即是否在求和中使用一个数字),然后递归地计算两个选项。
基础案例:如果num == 0,那么我们知道它是真的。但是如果num!= 0,并且数组的长度为0,那么我们知道它是假的
递归情况:我们检查数组中的第一个数字是否小于或等于num。如果不是,那么我们不能使用它。所以我们使用所有相同的参数进行递归调用,除了数组现在是原始数组减去第一个数字。
如果我们可以使用这个数字(例如
a[0] <= num
),那么正确的答案可能使用这个数字,也可能不使用它。我们对每种情况进行递归调用,如果任何一个递归调用返回true,则返回true。连续数规则:这很容易执行。我们添加一个名为'left'的参数,它告诉我们可以从数组的开头连续取的元素的数量。首先,left是2,因为我们最多可以取2个连续的数字。然后,如果我们在求和中使用数组中的第一个数字,我们就向左递减。如果我们不使用数组中的第一个数字,我们将left重置为2。在left变为0的情况下,我们别无选择,只能跳过数组顶部的当前数字。
编辑-上面代码的变体,不复制数组:
kr98yfug2#
你可以添加的第一件事是检查一行中是否有3个数字被添加。用
-1
替换数组中的数字也会在递归调用中产生意想不到的副作用。下面是我的一些东西。你可以忽略我用来查看所使用的值的index
参数。说明:递归
sumRule
方法将问题分为两部分:在这个方法中,
lastIndex
会跟踪最后一个值的索引,因此,在第一次调用中,该值是0,第二次调用中是1,依此类推。(start - lastIndex <= 1 ? consecutive + 1 : 1)
是检查consecutive
的值是否应该增加。连续= 1意味着,当前值被添加到总和。vxqlmq5t3#
下面是我的实现。它包含解释不同部分的作用的注解。
deyfvvtc4#