递归地找到列表中的完美平方和

Question

我正在尝试以递归方式在动态分配的列表中找到完全平方和。 ~~由于某种原因，我的函数一直忽略第一个元素。~~

*A 是指向数组第一个元素的指针。 n 是元素的数量，意味着它们在 0 到 n-1 的范围内。当 n 小于或等于零时，n-1 不是有效索引，因此我将 0 返回到完美平方和。

int sum(int *A, int n)
{
    int i, num = 0;

    if (n <= 0)
        return num;

    for (i = 0; i < A[n - 1]; i++) {
        if (i*i == A[n - 1]) {
            num = A[n - 1];
        }
    }
    return num + sum(A, n - 1);
}

~~为什么第一个元素总是被忽略？它适用于列表中的所有其他元素。~~

编辑：我尝试再次调用该函数，似乎只有数字 1 被忽略了。这是通过修改 for 循环条件修复的，所以解决方案是：

int sum(int *A, int n)
{
    int i, num = 0;

    if (n <= 0)
        return num;

    for (i = 0; i <= A[n - 1]; i++) {
        if (i*i == A[n - 1]) {
            num = A[n - 1];
        }
    }
    return num + sum(A, n - 1);
}

Answer 1

数组中的第一个元素是 A[0]。当您调用 sum(A,0).

时，您将返回 0 而不是 A[0] 的值

您是否尝试将行更改为：if (n<=0) return A(0);？

Answer 2

对于初学者来说，由于 A 指向的数组没有改变，指针应该用限定符 const.

声明

C 中对象的大小是使用类型 size_t 估算的。所以第二个参数应该声明为 size_t.

类型

此外，完全平方和可以大于 int 类型的对象所能容纳的大小。所以最好使用类型long long int作为return类型。

如果我没记错的话，0 不是一个完美的正方形。虽然这不是很重要，但是循环可以从 1 而不是 0 开始..

我可以建议以下解决方案。

#include <stdio.h>

long long int sum( const int *a, size_t n )
{
    int perfect_square = 0;

    if ( n )
    {
        int i = 1;

        while ( i * i < a[n-1] ) i++;

        if ( a[n-1] == i * i ) perfect_square = a[n-1];
    }

    return n == 0 ? perfect_square : perfect_square + sum( a, n -1 );
}


int main(void) 
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    const size_t N = sizeof( a ) / sizeof( *a );

    printf( "The sum of perfect squares is %lld\n", sum( a, N ) );

    return 0;
}

程序输出为

The sum of perfect squares is 14

递归地找到列表中的完美平方和

Recursively finding a sum of perfect squares in a list

c

recursion

perfect-square