 Autor
|
Tema: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C (Leído 8,394 veces)
|
maritere22
 Desconectado
Mensajes: 8
|
Buenas tardes.
Tengo que implementar en lenguaje C un programa que haga lo siguiente:
Dado un conjunto de N números enteros positivos ordenados de menor a mayor y un número S también entero positivo, dar el número de subconjuntos cuya suma sea S, usando la técnica de Vuelta Atrás (Backtracking).
Le estoy dando muchas vueltas y no consigo dar con la solución, también he buscado por internet y he encontrado muchas soluciones, pero están en C++, Pascal, etc. y no sé pasar de un lenguaje a otro.
Por favor, ¿alguien podría implementar este programa por mi y darme el código, de la forma más sencilla posible?
Se lo agradecería muchísimo...
|
|
|
|
|
En línea
|
|
|
|
0xDani
Desconectado
Mensajes: 1.077
|
Lo primero: hay un subforo específico dedicado a la programación en C/C++.
Lo segundo, te has informado sobre dicha técnica y/o has hecho algún intento antes de venir a pedir que te hagan el código?
Saludos.
|
|
|
|
|
En línea
|
I keep searching for something that I never seem to find, but maybe I won't, because I left it all behind!
I code for $$$
Hago trabajos en C/C++
Contactar por PM
|
|
|
maritere22
Desconectado
Mensajes: 8
|
Perdona, no sabía que había un subforo.
Lo de haber hecho pruebas ya lo he puesto en la explicación de mi problema. He estado haciendo pruebas y no lo he podido conseguir, por eso acudo al foro.
Saludos a ti también.
|
|
|
|
|
En línea
|
|
|
|
0xDani
Desconectado
Mensajes: 1.077
|
Pues pon códigos de intentos que hayas hecho, para que podamos ver los fallos y ayudarte a corregir, pero no lo pidas hecho. Si no pones nada de tu parte lo más probable es que nadie te ayude.
|
|
|
|
|
En línea
|
I keep searching for something that I never seem to find, but maybe I won't, because I left it all behind!
I code for $$$
Hago trabajos en C/C++
Contactar por PM
|
|
|
maritere22
Desconectado
Mensajes: 8
|
De acuerdo. Aquí está lo que he hecho hasta ahora. Obviamente, está mal, seguro que es una catástrofe. He ido añadiendo y quitando cosas y ya no sé por donde cogerlo. Como está tan mal, por eso pedía el código, no creo que el mío tenga arreglo fácil... #include <stdio.h>
#include <math.h>
#define length(x) (sizeof(x)/sizeof(x[0]))
static int V[]={1,2,3,4},aux[]={0,0,0,0},ex[]={}; //ex: vector que contiene al ultimo elemento expandido
//aux: deberia contener los elementos del subconjunto al que se le debe aplicar la funcion suma
int factorial(int M){
int num=M;
int factor = 1;
while (num > 0){
factor = num * factor;
num--;
}
return factor;
}
int suma(){
int sum=0,j=0;
while (j<length(aux)){
sum=sum+aux[j];
j++;
}
return sum;
}
int main() {
int S=5,i=0,T=0,cont=0,j,b=0,ncomb=0,k,v;
int nc[]={0,0,0,0}; //vector que contiene el numero de combinaciones para subconjuntos de 1,2,3 y 4 elementos
for (k=1;k<=length(V);k++){
ncomb=factorial(length(V))/(factorial(k)*factorial(length(V)-k));
printf("Numero de combinaciones con %d elementos: %d\n",k,ncomb);
nc[k-1]=ncomb;
}
do{
v=length(V);
if(T>v || suma()>S){ //Nodo fracaso
aux[i]=0;
i--;
T--;
nc[k]=nc[k-1];
}
else if(suma()==S){ // nodo solución
cont++;
aux[i]=0;
i--;
T--;
nc[k]=nc[k-1];
}
if(suma()<S) //nodo problema
{
T++;
i++;
}
if(i==1 && aux[0]==V[length(V)-1]){ //Nodo solucion
printf("Nº de soluciones %d\n",cont);
b=1;
exit(1);
}
ex[i]=V[i];
for(j=0;j<i;j++){
aux[j]=V[j];
aux[i-1]=ex[i+1]++;
}
}while(b==0);
}
El árbol que había pensado sería el siguiente, pero si se os ocurre otro más fácil agradezco todo lo que me digáis:  Es el árbol de ejemplo que me he hecho para aclararme, pero el programa debe valer para cualquier vector de n enteros positivos. Edito: No me he dado cuenta que falta la línea de 3 a 3,4 en el árbol. |
|
|
|
« Última modificación: 24 Mayo 2013, 18:06 pm por maritere22 »
|
En línea
|
|
|
|
maritere22
Desconectado
Mensajes: 8
|
Alguien me ayuda?
|
|
|
|
|
En línea
|
|
|
|
Kenkox
Desconectado
Mensajes: 12
|
Yo conozco una solución ... seria un simple while, un arreglo y dos apuntadores y es bastante simple de entender.... El punto de este algoritmo es posicionarte en la ultima posicion de tu arreglo, e ir probando todas las combinaciones posibles... osea, estando en el ultimo elemento, probar con todas las combinaciones con ese numero, cuando hayas terminado con ese numero ahora probaras todas las combinaciones con el elemento n-2... despues de que probaste todas esas, probar con todas las combinaciones con n-3 y asi sucesivamente hasta que tu apuntador i se haga menor a 0.... el apuntador j es el auxiliar para ir probando todas las posibilidades.... por ejemplo, supongamos sumatoria = arreglo(i) + arreglo(j) donde j != i... si sumatoria > S entonces sumatoria -= arreglo(j); j--; y entonces vuelve a entrar al ciclo......y denuevo sumatoria = arreglo(i) + arreglo(j)... y ahora supongamos que es menor... entonce j--; y volvemos a entrar... ahora supongamos que la sumatoria es igual a S.. entonces aumentamos contador de sumatorias, disminuimos i en una unidad y hacemos sumatoria = arreglo(i)... y volvemos a entrar
En resumen el apuntador i es el que te ayuda para saber el numero con el cual estas empezando, y j es con el que se va a ir sumando los numeros....
Suerte, ojalá y te sirva de algo... te daria el pseudoCodigo completo, pero el punto es que tambien pienses en terminar y programar la solucion.... y esta solucion la puedes programar ya sea en c++ o en c, o en java.. o en el lenguaje que sea... va a ser bastante similar ya que utilizas solamente herramientas basicas
|
|
|
|
« Última modificación: 31 Mayo 2013, 05:42 am por Kenkox »
|
En línea
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Recursividad y Backtracking!!!!
Java
|
bwsr
|
2
|
8,265
|
28 Junio 2007, 00:40 am
por bwsr
|
|
|
|
Backtracking - Laberinto
Programación C/C++
|
hadree
|
3
|
7,012
|
23 Noviembre 2010, 03:08 am
por do-while
|
|
|
|
[Reto] Backtracking - Laberinto
.NET (C#, VB.NET, ASP)
|
hadree
|
7
|
13,921
|
17 Diciembre 2010, 13:35 pm
por pisa2
|
|
|
|
Graficos de Conjuntos
Java
|
Choclito
|
1
|
4,215
|
26 Mayo 2011, 20:22 pm
por Maurice_Lupin
|
|
|
|
Los primeros que llegaron a Windows 10 ya no tienen vuelta atrás
Noticias
|
wolfbcn
|
0
|
1,214
|
1 Septiembre 2015, 14:25 pm
por wolfbcn
|
 |
