Hola, éste es el enunciado del problema: Decir cuántos números distintos se pueden formar como resultado del producto de uno, dos, o más de los siguientes números, sin repetir: 5, 22, 91, 455, 2002, 19945, 87758, 438790, 48266900.
Por ejemplo: 5 (5), 2002 (22·91), 45374875 (5·455·19945), etc.
La verdad que no encontré posible solución en C, y lo hice hasta python (sólo hasta los productos de 5 números, pero bueno la idea se ve) :
#!/usr/bin/python lista = (5, 22, 91, 455, 2002, 19945, 87758, 438790, 48266900) lista1 = [] #un numero for w in lista: lista1.append(w) #dos numeros for a in range(9): for b in range(a+1,9): lista1.append(lista[a] * lista[b]) #tres numeros for d in range(9): for e in range(d+1,9): for f in range(e+1,9): lista1.append(lista[d] * lista[e] * lista[f]) #cuatro numeros for h in range(9): for i in range(h+1,9): for j in range(i+1,9): for k in range(j+1,9): lista1.append(lista[h] * lista[i] * lista[j] * lista[k]) #cinco numeros for m in range(9): for n in range(m+1,9): for o in range(n+1,9): for p in range(o+1,9): for q in range(p+1,9): lista1.append(lista[m] * lista[n] * lista[o] * lista[p] * lista[q]) contador = 0 for z in lista1: if lista1.count(z) == 1: contador += 1 print contador
En un grupo de facebook de programación en el cual participo, un señor lo hizo así:
/* Programacion Recreativa - Facebook * ================================== * Decir cuántos números distintos se pueden formar * como resultado del producto de uno, dos, o más * de los siguientes números, sin repetir: * 5, 22, 91, 455, 2002, 19945, 87758, 438790, 48266900. * ================================== * * Breve explicacion: * * Más allá del inconveniente de C para manejar datos * enteros de más de 20 bits, el problema que encontré * es encontrar un algoritmo que genere todas las * combinaciones sin repeticiones del conjunto de * números dados. * * La solución que hallé es usar números binarios para * generar todas las combinaciones. Para un conjunto * dado de n elementos, la cantidad de combinaciones sin * repetición se calcula como: * 2^n - 1 * * Por ejemplo, para el conjunto ABCD, la cantidad de * combinaciones posibles es 15. La generación de * subconjuntos usando números binarios es la siguiente: * * Numero Binario Combinacion * -------------------------------------------------- * ABCD * ------ * 1 00000001 D D * 2 00000010 C C * 3 00000011 CD CD * 4 00000100 B B * 5 00000101 B D BD * 6 00000110 BC BC * 7 00000111 ABC ABC * 8 00001000 A A * 9 00001001 A D AD * 10 00001010 A C AC * 11 00001011 A CD ACD * 12 00001100 AB AB * 13 00001101 AB D ABD * 14 00001110 ABC ABC * 15 00001111 ABCD ABCD * * =============================================== * * Biblioteca usada: GMP (http://gmplib.org/) * * Compilacion: * gcc -g -lgmp -Wall -o combinatoria combinatoria.c * */ #include <stdio.h> #include <gmp.h> int main() { /* Para nuestro caso, el conjunto de * 9 números admite un total de: * 2^9 - 1 = 511 subconjuntos */ long n[9] = {5, 22, 91, 455, 2002, 19945, 87758, 438790, 48266900}; mpz_t r[512]; mpz_t ac; int i, j, k, m; mpz_init(ac); /* Acumulador */ mpz_array_init(r[0], 512, 128); for (i=1, k=1; i<512; i++, k=1) { mpz_set_ui(ac, 1); /* Generacion de la combinacion */ for (j=0; j<9; j++, k<<=1) { if ( i&k ) mpz_mul_ui(ac, ac, n[j]); } /* Control de duplicado */ for (m=0; mpz_cmp_ui(r[m], 0); m++) if (!mpz_cmp(ac,r[m])) break; /* Si el valor no está en el arreglo hay que agregarlo */ if (!mpz_cmp_ui(r[m], 0)) mpz_set(r[m], ac); } /* Mostrar los valores finales */ for (i=0; i<=m; i++) gmp_printf("%Zd\n", r[i]); mpz_clear(ac); return 0; }
Pero como se puede apreciar, utilizó una librería especial, y además bitwise; ¿es la única solución posible? ¿Es necesario saber bien bitwise para la competencia?