c++ - 计算 N 个整数组合的绝对值

Question

对于 N 个数 (a..N)，我通过以下方式找到所有组合的集合:

void create_print_combinations(int *t, int x, int n) {
    if(x == 0) {
        char p [2 * r + 2];
        memset (p, 0, 2 * r +2);
        for (int j=c;j>0;j--)
            if(j == c)
                sprintf(p, "%d", t[j]);
            else
                sprintf(p, "%s,%d", p,t[j]);
            print_combi(p);
    } else {
         for (int i= n; i < r; i++) {
             t[x] = a[i];
             create_print_combinations(t, x-1, i+1);
         }
    }
}

所以调用函数如下:

int main() {
    unsigned long int start=0, end=0;
    printf ("\nEnter the a positive integer N:");
    scanf("%d", &r);
    start=time(NULL);
    a = new int[r];
    for (int i = 0;i<r;i++)
    a[i]=i+1;
    for(int j=1;j<=r;j++) {
        a1 = new int[j];
        c=j;
        create_print_combinations(a1, c, 0);
        delete[] a1;
    }
    end=time(NULL);
    printf("Total time taken = %llu\n" , end - start);
    return 0;
}

给我 N=4 这样的组合:

输入一个正整数N:4

Combo : [1]
Combo : [2]
Combo : [3]
Combo : [4]
Combo : [1,2]
Combo : [1,3]
Combo : [1,4]
Combo : [2,3]
Combo : [2,4]
Combo : [3,4]
Combo : [1,2,3]
Combo : [1,2,4]
Combo : [1,3,4]
Combo : [2,3,4]
Combo : [1,2,3,4]

现在我的任务是喜欢所有组合的绝对值，例如:

对于 Combo [1,2,3,4] 应该是:

1+2+3+4 = abs(1+2+3+4)
1+2+3-4 = abs(1+2+3-4)
1+2-3-4 = ..
1-2-3+4 = ...

回答等等

我正在尝试以下逻辑:

while(pos > 0)
{
for(int a=0; a < i; a++)
{
if(a==0)
sprintf(p,"%d", t[a]);
else if(a == pos)
sprintf(p,"%s%c%d",p, minus, t[a]);
else
sprintf(p,"%s%c%d",p, plus, t[a]);
}
print(p);
memset (p , 0, 2 * r +2);
pos --;
}

但我相信我做错了什么，因为所有的集合都没有被打印出来。尽管我觉得我快要完成了，但我无法构建逻辑。下面是我的整个程序:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>

int *a;
int *a1;
int r;
int c;
unsigned long int no =1;

int stoi(char *var)
{
int n1 = 0;
int n2 = 0;
int n3 = 0;
char sign=0;
while(*var)
{
if(isspace(*var))
{
var++;
continue;
}
while(*var >= '0' && *var <= '9')
{
n1=(n1*10) + (*var - '0');
var++;
continue;
}
if(sign == '+')
{
n2=n2+n1;
n1=0;
}
else if(sign == '-')
{
n2=n2 - n1;
n1=0;
}
if(*var == '+' || *var == '-')
{
if(sign == 0)
{
n2=n1;
n1=0;
}
sign = *var;
}
var++;
}
if(sign == 0)
return abs(n1);
return abs(n2);
}

void print(char* var)
{
printf("[Combo %llu.] %s = %d\n" , no++, var, stoi(var));
}

void print_combi(char * a)
{
int t[c];
char *x = NULL;
char *y = a;
int i=0;
while((x=strchr(y, ',')) != NULL)
{
*x = '\0';
t[i++]=atoi(y);
y=x+1;
}
t[i++]=atoi(y);
int count =0;
int loop = 0;
char p [2 * r + 2];
memset (p , 0, 2 * r +2);
char plus = '+';
char minus = '-';
for(int k=0;k<2;k++)
{
if(k==1)
{
plus =  '-';
minus = '+';
}
if(i>1)
{
for(int a=0; a < i; a++)
{
if(a==0)
sprintf(p,"%d", t[a]);
else
sprintf(p,"%s%c%d",p, plus, t[a]);
}
}
else if(i==1)
{
sprintf(p,"%d", t[i-1]);
print(p);
break;
}
print(p);
memset (p , 0, 2 * r +2);
if(i==2)
continue;
if(i==3 && k ==1)
break;
int pos = i-1;
while(pos > 0)
{
for(int a=0; a < i; a++)
{
if(a==0)
sprintf(p,"%d", t[a]);
else if(a == pos)
sprintf(p,"%s%c%d",p, minus, t[a]);
else
sprintf(p,"%s%c%d",p, plus, t[a]);
}
print(p);
memset (p , 0, 2 * r +2);
pos --;
}
}
}

void create_print_combinations(int *t, int x, int n)
{
if(x == 0)
{
char p [2 * r + 2];
memset (p, 0, 2 * r +2);
for (int j=c;j>0;j--)
if(j == c)
sprintf(p, "%d", t[j]);
else
sprintf(p, "%s,%d", p,t[j]);
print_combi(p);
}
else
for (int i= n; i < r; i++)
{
t[x] = a[i];
create_print_combinations(t, x-1, i+1);
}
}
int main()
{
unsigned long int start=0, end=0;
printf ("\nEnter the a positive integer N:");
scanf("%d", &r);
start=time(NULL);
a = new int[r];
for (int i = 0;i<r;i++)
a[i]=i+1;
for(int j=1;j<=r;j++)
{
a1 = new int[j];
c=j;
create_print_combinations(a1, c, 0);
delete[] a1;
}
end=time(NULL);
printf("Total time taken = %llu\n" , end - start);
return 0;
}

根据程序逻辑，我将组合计算为字符串并生成表达式的绝对值。

Answer 1

对于您正在做的事情，有一种更简单的方法。您想将 N 个整数的 vector 相加:

[ 1*k1, 2*k2, 3*k3 ... N*kN ]

其中 kx = -1、0、+1。

对于x=1..N，kx有3^N种组合。