C递归函数检查两个数组是否颠倒

vsnjm48y 于 2022-12-26 发布在其他

关注(0)|答案(2)|浏览(129)

我需要检查两个数组是否颠倒，例如A[3] = {1, 2, 3}和B[3] = {3, 2, 1}
如果A不是给定长度的B的逆，则返回0，否则返回1。
以下是我目前所做的

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int* input_array(int);
int areReversed(int*, int*, int);

int main()
{
    int n = 0;
    int* A, * B;
    printf("please enter the size of arrays: \n");
    scanf("%d", &n);
    printf("please enter elements of the first array: \n");
    A = input_array(n);
    printf("please enter elements of the second array: \n");
    B = input_array(n);
    areReversed(A, B, n) ? printf("Arrays are the opposite to one another.\n") : printf("Arrays are not the opposite to one another.\n");
    free(A); free(B);
}

int areReversed(int* A, int* B, int n) {
    int i = 0, j = n-1;
    int reverse = 0;
    if (n > 1)
    {
        for (i = 0, j = 0; i < n && j >= 0; i++, j--)
        {
            if (A[i] == B[j])
            {
                return areReversed(A + 1, B + 1, n);
            }
            if (A[i] != B[j])
                return 0;

        }
        return 1;
    }
}

int* input_array(int n) {
    int i;
    int* A = (int*)malloc(n * sizeof(int));
    assert(A);
    printf("Enter %d integers\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", A + i);
    }
    return A;
}

'
但可悲的是，它不起作用，我已经尝试了这么多的事情...即使你能给予提示，它将是可怕的

来源：https://stackoverflow.com/questions/74902451/c-recursive-function-to-check-between-two-arrays-if-they-are-reversed-or-not

2条答案

按热度按时间

vwkv1x7d1#

areReversed可以简单地表示为：

int areReversed(int *A, int *B, int n) 
{
    return n == 0 || A[0] == B[n-1] && areReversed(A+1, B, n-1);
}

这是可行的：

如果n为0，那么这两个数组是相互颠倒的，因为它们都是空的（我们期望n不为负）。
否则，我们比较A的第一个元素和B的最后一个元素，如果它们不相等，则==和&&失败（对于"false"产生0），并返回"false"，因为数组不是彼此相反的。
如果它们相等，我们还要求数组的其余部分被反转，这通过递归case来处理：A的最后n-1个元素（从A+1开始）必须与B的前n-1个元素（从B开始）相反。

赞(0）回复(0）举报 2022-12-26

vxbzzdmp2#

递归的关键是：
1.具有将被满足并且具有确定答案的健壮终止条件。
1.这个问题是一个更小但相同的问题的函数。
在这种情况下，终止条件是数组n的长度为零（返回true），或者A[0] != B[n-1]（返回false）
对于长度为n的数组，其中两个相反的端点相等（A[0] == B[n-1]），A * 可能是B的反转，因此您将问题转换为更小的问题并进行测试。更小的问题是从每个数组的每一端“一入”-即：

areReversed( &A[1], B, n - 1 ) ;

如果你是迭代地而不是递归地做这个，那么在比较A[0]和B[n-1]之后，“较小的”测试将是比较A[1]和B[n-2]。但是递归调用修改参数来达到相同的效果，所以这里递归调用的A是父调用&A[1]（或者A + 1，如果你喜欢的话--我不喜欢），并且数组长度短一，这样递归调用的B[n-1]就是父调用B[n-2]。
因此，

#include <stdio.h>
#include <stdbool.h>

bool areReversed( int* A, int* B, int n) 
{
    int is_reverse = false ;
    if( n == 0 )
    {
        is_reverse = true ;
    }
    else if( A[0] == B[n-1] )
    {
        is_reverse = areReversed( &A[1], B, n - 1 ) ;
    }

    return is_reverse ;
}

int main()
{
    int A1[] = {1, 2, 5, 14, 9, 3} ;
    int B1[] = {3, 9, 14, 5, 2, 1} ;
    int A2[] = {1, 2, 5, 14, 9, 3} ;
    int B2[] = {3, 9, 14, 5, 2, 7} ;
    
    bool R1 = areReversed( A1, B1, sizeof(A1) / sizeof(*A1) ) ;
    bool R2 = areReversed( A2, B2, sizeof(A2) / sizeof(*A2) ) ;

    printf( "A1 %s the reverse and B1\n", R1 ? "is" : "is not" ) ;
    printf( "A2 %s the reverse and B2\n", R2 ? "is" : "is not" ) ;
}

输出：

A1 is the reverse and B1
A2 is not the reverse and B2

用奇数个元素来演示它的功能：

int A1[] = {1, 2, 5,   99, 14, 9, 3} ;
int B1[] = {3, 9, 14, 101, 5, 2, 1} ;
int A2[] = {1, 2, 5,  100, 14, 9, 3} ;
int B2[] = {3, 9, 14, 100, 5, 2, 1} ;

则输出为：

A1 is not the reverse and B1
A2 is the reverse and B2

为了理解递归，我建议您使用调试器来逐步执行代码，逐步进入每个递归调用，以观察“较小的问题”和是否满足终止条件。和 stepping-out 来观察算法的“展开”和最后的返回。无论如何，你应该学习如何有效地使用调试器-它是一个很好的学习工具，可以观察代码的精确行为和变量的状态，也可以帮助调试。
我还建议，虽然像这样一个简单的函数是探索递归概念的一种有用的方式，但它也可以通过迭代来实现，并且在实践中可能应该这样做。有些问题不太适合迭代，而适合递归。我会为这样的问题保留递归--例如，* 二叉搜索树 * 和 * 洪水填充 *。尽管即使这样也不需要递归，仅仅是更简单。
递归的问题在于它有一个不确定的调用堆栈要求，并且调用堆栈是一个有限的资源--你可以直接得到一个_stack-overflow。在 * 你的 * 测试用例中，数据是在运行时提供的，并且长度是无限的，一个恶意的或不小心的用户可能会导致堆栈溢出，而你的代码中没有任何方法来防止这样的攻击或误用。

赞(0）回复(0）举报 2022-12-26

我来回答

C递归函数检查两个数组是否颠倒

2条答案

相关问题

热门标签

最新问答