数组B是否为数组B函数的反转版本[duplicate]

oewdyzsn  于 2022-12-29  发布在  其他
关注(0)|答案(4)|浏览(135)
    • 此问题在此处已有答案**:

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的一些元素,因此比较是错误的。

fslejnso

fslejnso1#

这段代码的问题在于,您传递的B的基数不正确,大小也不正确。
if (A[0] != B[n - 1])中,比较A的第一个元素和B的最后一个元素(n是数组的长度)。
所以在下一次迭代中,你必须把A提前1,但是B的基数必须保持不变,大小也必须减少1,所以正确的调用应该是return areReversed(A + 1, B, n - 1);
如果您这样做:

#include <stdio.h>

int areReversed(int* A, int* B, int n)
{
    if (n <= 0) return 1; // all elements have been compared and are equal

    printf("checking %d and %d, n is %d\n", *A, B[n-1], n); 

    // 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, n - 1); 
}

int main()
{
    int a[] = {1,2,3,4,5};
    int b[] = {5,4,3,2,1};

    printf("Palindrom? %d\n", areReversed(a,b, sizeof a / sizeof *a));
    return 0;
}

你就会得到正确的结果

$ ./a 
checking 1 and 1, n is 5
checking 2 and 2, n is 4
checking 3 and 3, n is 3
checking 4 and 4, n is 2
checking 5 and 5, n is 1
Palindrom? 1
kkih6yb8

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是否大于零(并且绝对不能小于零)。
记住,在写任何代码之前,用纸笔(或文本编辑器)仔细思考一个问题--这是一个非常宝贵的编程练习(尤其是在处理棘手的递归问题时)。

pbpqsu0x

pbpqsu0x3#

建议:如果我们添加一个递增的偏移量参数,我们根本不需要修改递归中的A和'B指针。
我们也不需要检查两个数组的 * 整个 * 长度,而只需要检查一半。

#include <stdio.h>

int areReversed(int* A, int* B, int n, int offset) {
    if (offset > n / 2) return 1;
    if (A[offset] == B[n - offset - 1] && A[n - offset - 1] == B[offset])
        return areReversed(A, B, n, offset+1);
    return 0;
}

int main(void) {
    int A[] = {1, 2, 3, 4, 5};
    int B[] = {5, 4, 3, 2, 1};

    if (areReversed(A, B, 5, 0)) {
        printf("They are mirrors of each other.\n");
    }

    return 0;
}

进一步说明一下,理解递归的工作原理是很重要的,但是除非你的编译器优化了尾部调用,否则当数组足够大时,你可能会遇到堆栈溢出。这个算法很容易适应在恒定堆栈空间中运行的循环。

int areReversed(int* A, int* B, int n) {
    for (int offset = 0; offset < n / 2; offset++)
        if (A[offset] != B[n - offset - 1] || A[n - offset - 1] != B[offset])
            return 0;

    return 1;
}
7kqas0il

7kqas0il4#

至少在我看来,如果你提前做出选择,会更干净、更简单:要么完全处理指针,要么完全处理数组下标。
但是,将这两者混合在一起,使用移动指针的下标,这是一种很难工作的代码配方,也很难长期维护。
如果我要做的话,我只会使用指针,现在,让我们假设你需要使用你所做的函数签名:

int areReversed(int* A, int* B, int n)

如果是这样的话,我会把它单独用作另一个函数的前端,该函数假定它正在接收一个指向A的开头和B的结尾的指针:

int areReversed(int *A, int *B, int n) { 
    return areReversedImpl(A, B+n-1, n);
}

然后,该函数将实现如下内容:

  • 如果n == 0,我们就完成了--返回true
  • 如果 *A!= *B,我们就完成了--返回false
  • 否则(即,如果 *A等于 *B)对(A+1,B-1,n-1)进行递归调用

对不起,但是不,我不会完全写你的家庭作业给你。

相关问题