c - 使用递归的成对差异

Question

我被要求将这段伪代码翻译成 C 程序:

rep := 0
while A not empty:
    B := []
    for x in A, y in A:
        if x != y: append absolute_value(x - y) to B
    A := B
    rep := rep + 1

最后我得到了这个:

int iterateIt(int a_count, int* a) {
    unsigned long long i, j, k;
    unsigned long long count = a_count;

    for( i = 1 ; i < a_count ; i++ )
        count *= count-1;

    int *b = (int *) malloc(count * sizeof(int));
    count = 0;
    k = 0;
    for( i = 0 ; i < a_count ; i++ ){
        for( j = i ; j < a_count ; j++ ){
            if(a[i] != a[j]){
                b[k] = abs(a[i] - a[j]);
                k++;
            }
        }
    }

    if( k > 0){
        return 1 + iterateIt(k, b);
    }
    free(b);
    return 1;
}

我使用递归来返回算法的迭代次数。实际上，我取 A 的任意两个不同对象之间的差异，并将绝对值放入 B 中，我在其上重复。对于简单的输入，我得到了正确的结果，但我不明白为什么输入如下:16 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768或 4 1 352 9483 50000(第一个数字是A的元素个数)

我收到段错误。

谢谢你的帮助

Answer 1

我认为你的 count 是错误的。您的第二次迭代已经很庞大了。

#include <stdio.h>
#include <stdlib.h>

size_t total_allocated = 0;

int iterateIt(int a_count, int* a) {
    unsigned long long i, j, k;
    unsigned long long count = a_count;

    for( i = 1 ; i < a_count ; i++ )
        count *= count-1;

    size_t size = count * sizeof(int);
    printf("Allocating %llu ints: %llu bytes\n", count, (unsigned long long)size);
    total_allocated += size;
    printf("Total allocated: %llu bytes\n", (unsigned long long)total_allocated);
    int *b = (int *) malloc(count * sizeof(int));
    count = 0;
    k = 0;
    for( i = 0 ; i < a_count ; i++ ){
        for( j = i ; j < a_count ; j++ ){
            if(a[i] != a[j]){
                b[k] = abs(a[i] - a[j]);
                k++;
            }
        }
    }

    if( k > 0){
        return 1 + iterateIt(k, b);
    }
    free(b);
    return 1;
}

int main (void)
{
    iterateIt(4, (int[4]){1,352,9483,50000});
    return 0;
}

结果:

Allocating 17292 ints: 69168 bytes
Total allocated: 69168 bytes
Allocating 12550317587327992670 ints: 13307782201892867448 bytes
Total allocated: 13307782201892936616 bytes