Comunidad PHPeros

Lenguajes => C / C++ => Mensaje iniciado por: good en 26 de Agosto de 2011, 00:03:41 am

Título: backtracking
Publicado por: good en 26 de Agosto de 2011, 00:03:41 am
la idea del backtracking es "llegar hasta el fondo" y si no es correcto, retroceder.
Un ejemplo de aplicación es la solución de un laberinto.

pero voy a poner algo más sencillo, un programa que genera todas las combinaciones de 0 y 1 de longitud n

#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<bool> VB;
 
void combinaciones (VB& v, int count) {
     if (count == int(v.size())) {
          // imprimir el vector
          for (int i = 0; i < int(v.size()); ++i) cout << v;
          cout << endl;
          return;
     }
     v[count] = true;
     combinaciones(v, count+1);
 
     v[count] = false;
     combinaciones(v, count+1);
}
 
int main () {
     int n;
     cin>>n;
     VB v(n);
 
     combinaciones(v, 0);
}
Título: Re:backtracking
Publicado por: Physlet en 26 de Agosto de 2011, 01:14:32 am
La mejor forma para que los usuarios comprendan esta técnica, es que conozcan los grafos.
En mi caso, como no tengo tiempo para hacer estudios independientes por trabajo y demás, voy a esperarme a unas semanas en lo que entramos a dar el tema de grafos en la asignatura de Estructura de Datos.
Título: Re:backtracking
Publicado por: good en 26 de Agosto de 2011, 01:25:12 am
La mejor forma para que los usuarios comprendan esta técnica, es que conozcan los grafos.
En mi caso, como no tengo tiempo para hacer estudios independientes por trabajo y demás, voy a esperarme a unas semanas en lo que entramos a dar el tema de grafos en la asignatura de Estructura de Datos.

si pongo un reto de búsqueda en grafos lo harás? xD
Título: Re:backtracking
Publicado por: Physlet en 26 de Agosto de 2011, 02:34:45 am
si pongo un reto de búsqueda en grafos lo harás? xD
Cuando comprenda grafos, sí. Esperaré a que toquen el tema en la u.
Título: Re:backtracking
Publicado por: good en 26 de Agosto de 2011, 12:32:31 pm
Cuando comprenda grafos, sí. Esperaré a que toquen el tema en la u.

lo peor es la programación dinámica, dinámicas everywhere, contar cosas everywhere. Los grafos son mas guapos xDD
Título: Re:backtracking
Publicado por: Physlet en 26 de Agosto de 2011, 17:09:34 pm
lo peor es la programación dinámica, dinámicas everywhere, contar cosas everywhere. Los grafos son mas guapos xDD
Cada estructura tiene un fin, la idea no es mezclar conceptos. Por eso no te puedo decir si son más guapos o más prácticos porque aún no toco el tema.

Ya pasé por las primitivas, arreglos, listas enlazadas, pilas, colas, registros y voy ahora mismo en árboles.
Título: Re:backtracking
Publicado por: madbeto en 26 de Marzo de 2012, 04:33:22 am
Buenas.. me aparece un error en tu codigo.. lo arregle poniendo esto en donde imprimes el vector

asi quedo:
for (int i = 0; i < int(v.size()); ++i) cout << v;

Muy buen codigo, muchas gracias