elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C  (Leído 5,925 veces)
maritere22

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« en: 23 Mayo 2013, 21:25 pm »

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 Desconectado

Mensajes: 1.077



Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #1 en: 23 Mayo 2013, 21:40 pm »

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 Desconectado

Mensajes: 8


Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #2 en: 23 Mayo 2013, 22:01 pm »

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 Desconectado

Mensajes: 1.077



Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #3 en: 24 Mayo 2013, 16:11 pm »

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 Desconectado

Mensajes: 8


Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #4 en: 24 Mayo 2013, 18:00 pm »

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...

Código:
#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 Desconectado

Mensajes: 8


Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #5 en: 30 Mayo 2013, 15:13 pm »

Alguien me ayuda?
En línea

Kenkox

Desconectado Desconectado

Mensajes: 12



Ver Perfil
Re: Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
« Respuesta #6 en: 31 Mayo 2013, 05:39 am »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Recursividad y Backtracking!!!!
Java
bwsr 2 7,244 Último mensaje 28 Junio 2007, 00:40 am
por bwsr
Backtracking - Laberinto
Programación C/C++
hadree 3 4,704 Último mensaje 23 Noviembre 2010, 03:08 am
por do-while
[Reto] Backtracking - Laberinto
.NET (C#, VB.NET, ASP)
hadree 7 11,288 Último mensaje 17 Diciembre 2010, 13:35 pm
por pisa2
Graficos de Conjuntos
Java
Choclito 1 3,417 Último mensaje 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 594 Último mensaje 1 Septiembre 2015, 14:25 pm
por wolfbcn
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines