- 此问题在此处已有答案**:
C recursive function to check between two arrays if they are reversed or not(2个答案)
昨天关门了。
我需要一个指导来理解我的逻辑在哪里不起作用。我需要编写一个递归函数,从用户输入接收数组A和数组B。该函数检查数组是否颠倒。例如:A = {1,4,6,7,5,3,2},B = {2,3,5,7,6,4,1},函数将返回1。如果它们不颠倒,函数将返回0。数组的大小无关紧要,因为它对A和B都是相同的。当我运行程序时,无论输入是什么,结果都是0,即使输入正确(B与A相反)。
int areReversed(int* A, int* B, int n)
{
if (n <= 0) return 1; // all elements have been compared and are equal
// Compare first element of array A and last element of array B
if (A[0] != B[n - 1])
return 0; // elements are not equal
// Recursively compare remaining elements of arrays A and B
return areReversed(A + 1, B - 1, n - 2);
}
到目前为止,这是我的代码。我很想知道函数总是返回0的原因,以及我的逻辑在哪里失败。理论上,它应该可以从我所看到的工作。
我玩了一下,并改变了递归调用(A +1,B,n-1)做了一些测试,它似乎是工作。希望对变化的第二个意见,看看它是否完美或仍有一些工作要做。在原来的代码中,我减少了n太多,所以它跳过了B的一些元素,因此比较是错误的。
4条答案
按热度按时间fslejnso1#
这段代码的问题在于,您传递的
B
的基数不正确,大小也不正确。在
if (A[0] != B[n - 1])
中,比较A
的第一个元素和B
的最后一个元素(n
是数组的长度)。所以在下一次迭代中,你必须把
A
提前1,但是B
的基数必须保持不变,大小也必须减少1,所以正确的调用应该是return areReversed(A + 1, B, n - 1);
。如果您这样做:
你就会得到正确的结果
kkih6yb82#
好了,我们想看看数组
B
是否是A
的反向拷贝。下面是两个数组:
A = x一米二纳米一x一米三纳米一x一米四纳米一x一米五纳米一x一米六纳米一x
B = x一米七纳一x一米八纳一x一米九纳一x一米十纳一x一米十纳一x一米十一纳一x
递归通过做一些"可重复"的事情来将问题简化为一个更简单的版本。OP有一个正确的想法(不是"唯一"正确的想法,而是一个有效的想法):
A =[x一米十二纳米一x] x一米十三纳米一x一米十四纳米一x一米十五纳米一x
5
它们是相等的乙=
5
x1米18英寸x1米19英寸x1米20英寸[x1米21英寸]A =
1
x1米23英寸1x x x 1米24英寸1x 1米25英寸1x [x1米26英寸1x] 它们是相等的B =[x一米27纳米1 x] x一米28纳米1 x一米29纳米1 x一米30纳米1 x
1
由于两个数组的第一个元素和最后一个元素是相反的,我们可以继续每个数组的 * inner * 元素:
A ′ = x一米32纳米1 x一米33纳米1 x一米34纳米1 x
B ′ = 1米35纳1x 1米36纳1x 1米37纳1x
重复,直到我们用完所有元素:
A ″ =
3
B ″ =
3
A =
B =
没有更多元素,返回
true
。用代码实现
作为一个函数的参数,一个数组只是由一个指针给出的,非常方便的是,我们可以在指针值上加1来得到下一个元素,或者,更直接一点,一个以下一个元素开始的 * sub -数组。
我们还需要减少每个数组中的元素数。每次从数组中减少多少个元素?
请注意, single * 元素的数组是一个特殊条件:如果我们减去两个元素,我们得到... -1。
在尝试比较第一个和最后一个元素之前,请确保检查
n
是否大于零(并且绝对不能小于零)。记住,在写任何代码之前,用纸笔(或文本编辑器)仔细思考一个问题--这是一个非常宝贵的编程练习(尤其是在处理棘手的递归问题时)。
pbpqsu0x3#
建议:如果我们添加一个递增的偏移量参数,我们根本不需要修改递归中的
A
和'B指针。我们也不需要检查两个数组的 * 整个 * 长度,而只需要检查一半。
进一步说明一下,理解递归的工作原理是很重要的,但是除非你的编译器优化了尾部调用,否则当数组足够大时,你可能会遇到堆栈溢出。这个算法很容易适应在恒定堆栈空间中运行的循环。
7kqas0il4#
至少在我看来,如果你提前做出选择,会更干净、更简单:要么完全处理指针,要么完全处理数组下标。
但是,将这两者混合在一起,使用移动指针的下标,这是一种很难工作的代码配方,也很难长期维护。
如果我要做的话,我只会使用指针,现在,让我们假设你需要使用你所做的函数签名:
如果是这样的话,我会把它单独用作另一个函数的前端,该函数假定它正在接收一个指向A的开头和B的结尾的指针:
然后,该函数将实现如下内容:
对不起,但是不,我不会完全写你的家庭作业给你。