¿Cuál sería la mejor manera (en C) de obtener todas las sumas de N números en una matriz, usando sumas y restas?
Por ejemplo (N = 3):
arr[] = [30, 14, 2] results: -30-14-2 = -46 -30-14+2 = -42 -30+14-2 = -18 -30+14+2 = -14 30-14-2 = 14 30-14+2 = 18 30+14-2 = 42 30+14+2 = 46Como se puede ver, hay soluciones 2^N.
También noté que los símbolos de suma y resta se alternan de la misma manera que el conteo binario (000 001 … 110 111), lo que podría ser útil.
Probablemente sería mejor un enfoque recursivo, pero me resulta muy difícil pensar recursivamente.
Por lo tanto, espero que alguien pueda explicarme cuál sería la mejor estrategia para abordar este problema.
——————————
EDITAR:
Tengo un código de Python que funciona, pero usa sets set() , que no están disponibles en C. ( arr es una matriz que contiene todos los números).
out = set() out.add(0) for i in range(0, len(arr)): tmp = set() for j in out: tmp.add(j + arr[i]) tmp.add(j - arr[i]) out = tmp print(out)——————————
EDITAR:
Al reemplazar los conjuntos por matrices y hacer algunos pequeños cambios, lo hice funcionar. ¡Gracias a todos los que comentaron!
Este es un caso en el que la recursión parece preferible a una estructura de datos porque la naturaleza exponencial del problema significa que no hay riesgo de un desbordamiento de pila en cualquier valor de n que pueda probar de manera realista, pero puede aprovechar las capacidades de almacenamiento implícitas de la pila.
La lógica recursiva se puede escribir muy directamente usando un índice i . El caso base es cuando i >= n ; imprime la suma que has acumulado. De lo contrario, reste el i -ésimo elemento de la suma y recurra al resto de la lista de números sin i . En una segunda rama, agregue el i -ésimo elemento a la suma y recurra al resto de la lista de números sin i . También puede cambiar los elementos de la matriz usando un puntero si i como se indica en los comentarios.
Tenga en cuenta que este procedimiento incluirá resultados duplicados, por lo que si desea eliminarlos, vale la pena continuar con su idea de conjunto original.
Por lo general, es un diseño deficiente mezclar IO y lógica en las funciones, pero por motivos de simplicidad, romperé esa regla aquí:
#include <stdio.h> void print_possible_sums(int nums_len, int *nums, int sum, int i) { if (i >= nums_len) { printf("%d\n", sum); } else { print_possible_sums(nums_len, nums, sum - nums[i], i + 1); print_possible_sums(nums_len, nums, sum + nums[i], i + 1); } } int main() { int arr[] = {30, 14, 2}; print_possible_sums(sizeof(arr) / sizeof(arr[0]), arr, 0, 0); return 0; }Producción:
-46 -42 -18 -14 14 18 42 46He hecho un algoritmo que realiza este problema. Tal vez lo que escribí no sea lo más eficiente posible (así que tal vez se pueda mejorar), pero al menos funciona.
Hazme saber si está bien.
#include <stdio.h> #include <math.h> #include <stdlib.h> #define MAX 4 void cycle(int arr[MAX]); int toRepeat(int arr[MAX], int s); int main(){ int arr[MAX] = {1, 2, 3, 4}; cycle(arr); } void cycle(int arr[MAX]){ int a, ris; a = pow(2, MAX); for (int i= 0; i < a; i++){ ris = toRepeat(arr, i); printf(" = %3d \n", ris); } } int toRepeat(int arr[MAX], int s){ int pos = 0; int ris = 0; int a; bool flag; a = pow(2, MAX); if (s < a/2) { ris += arr[pos]; printf("+%d", arr[pos]); } else { ris -= arr[pos]; printf("-%d", arr[pos]); } pos++; for (int i= 2; i < a; i = i * 2){ for (int j= 0; j < i/2; j++) { if (s%i == j) { ris += arr[pos]; printf("+%d", arr[pos]); pos++; flag = true; break; } } if (!flag){ ris -= arr[pos]; printf("-%d", arr[pos]); pos++; } flag = false; } return ris; }Producción:
+1+2+3+4 = 10 +1-2+3+4 = 6 +1+2-3+4 = 4 +1-2-3+4 = 0 +1+2+3-4 = 2 +1-2+3-4 = -2 +1+2-3-4 = -4 +1-2-3-4 = -8 -1+2+3+4 = 8 -1-2+3+4 = 4 -1+2-3+4 = 2 -1-2-3+4 = -2 -1+2+3-4 = 0 -1-2+3-4 = -4 -1+2-3-4 = -6 -1-2-3-4 = -10¡Yo también, yo también!
Mantenga una matriz con bool negative[3 + 1] = {0}; . Calcule la suma de array[i] * (negative[i]?-1:1) en cada paso. Cada paso incrementa el siguiente valor en negativo como si fuera un número binario. El ciclo termina cuando el elemento más alto negative[3] es verdadero, por lo que queremos todas las posibilidades.
#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #include <assert.h> int calc_sum(size_t len, const int vals[len], const bool negative[len]) { int sum = 0; for (size_t i = 0; i < len; ++i) { sum += vals[i] * (negative[i] ? -1 : 1); } return sum; } bool *sequence_init(size_t len) { // error checking omitted return calloc(len + 1, sizeof(bool)); } bool sequence_continue(size_t len, bool t[len + 1]) { assert(t); const bool go_on = !t[len]; if (!go_on) { // automatically free on loop end free(t); } return go_on; } void sequence_next(size_t len, bool t[len + 1]) { assert(t); for (size_t i = 0; i < len + 1; ++i) { if (!t[i]) { t[i] = 1; break; } else { t[i] = 0; } } } int main() { const int vals[3] = { 30, 14, 2 }; const size_t len = 3; for( bool *sequence = sequence_init(len); sequence_continue(len, sequence); sequence_next(len, sequence) ) { for (size_t i = 0; i < len; ++i) { printf("%2d*%d %c ", sequence[i]?-1:1, vals[i], i + 1 != len ? '+' : '=' ); } const int sum = calc_sum(len, vals, sequence); printf("%d\n", sum); } }El código genera:
1*30 + 1*14 + 1*2 = 46 -1*30 + 1*14 + 1*2 = -14 1*30 + -1*14 + 1*2 = 18 -1*30 + -1*14 + 1*2 = -42 1*30 + 1*14 + -1*2 = 42 -1*30 + 1*14 + -1*2 = -18 1*30 + -1*14 + -1*2 = 14 -1*30 + -1*14 + -1*2 = -46