C语言 需要有关算法的帮助(堆栈溢出)

Question

这是我的一个朋友给我的挑战。我已经设法提出了一种递归算法，该算法适用于小输入，但是对于大值，我遇到了分割错误。我想这是因为堆栈溢出。我使用C语言来解决问题。

你会得到一个由 n 个数字组成的数组。查找并打印子集的最大长度，以便对于构成该子集的任何两个数字，数字的总和不能被 k 整除。

输入在第一行包含 2 个数字 n 和 k，在下一行有 n 个数字 a[i]，使得：

1 <= n <= 10^5
0 <= a[i] <= 10^9
1 <= k <= 100
# Example input:
4 3
1 7 4 2
# Output:
3

说明：(1 7 4) 1 + 7 = 8; 1 + 4 = 5; 7 + 4 = 11;它们都不能被 3 整除。

我的解决方案基于以下想法：对于数组中的所有数字，如果它能被 k 整除，请检查与其他数字的总和。如果我们找到匹配项，则创建 2 个数组，一个排除总和的第一项，另一个排除第二个，这样我们就从子集中排除了这些对。然后对它们两个数组执行我们对第一个数组所做的相同操作。如果我们已经检查了数组中的所有元素，则将解决方案设置为数组的长度，并继续将"求解器"仅应用于长度大于已找到的解决方案的数组。这个算法适用于 n <47 ，不仅如此，它给了我一个 seg 错误。我希望看到解决问题的任何解决方案。

#include <stdio.h>
int n, k;
int * deleteElement(int * a, int n, int j){
int *c = (int*) malloc((n-1) * sizeof(int));
int k = 0;
for(int i = 0; i < n; i++){
if(i == j) continue;
c[k] = a[i];
k++;
}
return c;
}
int sol = 0;
void solver(int *a, int n, int *sol){
int *b, *c;
if(n <= *sol) return;
for(int i = 0; i <  n-1; i++){
for(int j = i + 1; j < n; j++){
if((a[i] + a[j]) % k == 0){
c = deleteElement(a, n, i);
b = deleteElement(a, n, j);
solver(c, n-1, sol);
solver(b, n-1, sol);
return; 
}
}
}
*sol = n;
}
int main(){
scanf("%d", &n);
scanf("%d", &k);
int a[n];
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
solver(a, n, &sol);
printf("%dn", sol);
return 0;
}

Answer 1

你可以使用迭代来摆脱两个递归调用中的一个，但这对堆栈空间没有帮助，因为它们具有相同的深度——一个调用和 2 个一样糟糕。

编写一个完全迭代的算法来实际测试所有有效集合很容易，但这仍然是一个指数时间算法。 无论如何，这将使您免于堆栈溢出，运行时间太长。 由于该算法也很糟糕，因此我不想编写它。

解决此问题的合理线性时间方法是：

1. 计算一个映射 MODCOUNTS，其中 MODCOUNTS[m] = 元素的数量 x 使得 x%k == m
2. 由于任何有效子集只能有一个可被 k 整除的元素，如果 MODCOUNTS[0]> 1，则设置 MODCOUNTS[0]=1
3. 类似地，如果 k 是偶数，并且 MODCOUNTS[k/2]> 1，则设置 MODCOUNTS[k/2]=1
4. 现在，将 MODCOUNTS 中的所有值相加，但在以下情况下省略一个值 MODCOUNTS[i]： i> 0， i*2 <k，>
   • <MODCOUNTS[k-i];或>
   i*2> k 和模数[i]
   • <= 模数[k-i]

规则4 反映了这样一个事实，即对于我们在规则 2 和 3 中未处理的情况，有效子集不能包含任何元素 x 和 y，使得 (x+y)%k = 0。 最大的有效子集包括 MODCOUNTS[i] 中的所有元素，或 MODCOUNTS[k-i] 中的所有元素，但不包括两者中的元素。

如果你使用像哈希表这样的稀疏数据结构来实现 MODCOUNTS，那么整个事情需要 O(N) 时间。