c - 如何将数组的每个元素与同一数组的其他元素相加？

Question

假设我有一个数组

a[3]={1,3,8}  

我希望输出是一个数组，其中包含通过将数组 a 中的数字相加获得的数字以及数组 aie 的元素，

b[0]=1
b[1]=3
b[2]=8
b[3]=4  //(1+3)
b[4]=9  //(1+8)
b[5]=11 //(3+8)
b[6]=12 //(1+3+8) 

我该怎么做呢？

Answer 1

因此，您想要生成一组数字的所有可能子集并列出它们的总和。

首先，您要枚举所有子集。由于2 ^ N在包含N元素的集合中有子集，您可以简单地通过从 0 到自然数迭代1 << (sizeof(arr) / sizeof(arr[0]))并按以下方式处理数字的二进制表示来做到这一点：如果特定位设置在 position k，则第kth 元素在当前生成的子集中，否则不在。

然后，您应该将所有选定的元素添加在一起，并将结果存储在另一个数组的下一个槽中（2 ^ N显然是大小）。

#define COUNT(a) (sizeof(a) / sizeof(a[0]))
#include <limits.h> // for CHAR_BIT

unsigned a[3] = { 1, 3, 8 };
unsigned sums[1 << COUNT(a)] = { 0 };

for (unsigned i = 0; i < COUNT(sums); i++) {
    for (unsigned j = 0; j < sizeof(i) * CHAR_BIT; j++) {
        if ((i >> j) & 1) {
            sums[i] += a[j];
        }
    }
}

for (unsigned i = 0; i < COUNT(sums); i++) {
    printf("%d\n", sums[i]);
}

Answer 2

我会这样做：

b[0] = 0;  //This is not listed in the question, but should be included in the result IMHO.
for(long i = 0; i < elementsA; i++) {
    long preexistingElements = 1 << i;
    long curElement = a[i];
    for(long j = 0; j < preexistingElements; j++) {
        b[j + preexistingElements] = b[j] + curElement;
    }
}

该算法在结果数组的大小上是线性的，因为它的每个元素都是以恒定成本计算的。

如果您确实必须排除零并且想要 malloc 结果数组，请反转算法，以便 b 从后面填充零元素作为最后一个元素。