Subcategorías

• Dynamic Programming (DP)
  0
  Temas
  0
  Mensajes
  No hay mensajes nuevos.
• Computational Geometry
  0
  Temas
  0
  Mensajes
  No hay mensajes nuevos.
• Math
  0
  Temas
  0
  Mensajes
  No hay mensajes nuevos.
• Paradigmas/Tecnicas/Estrategias
  4
  Temas
  4
  Mensajes

  

  Ahora que ya vimos en acción este método, surge la pregunta, es posible obtener una matriz de recurrencia para cualquier formula encontrada ? La respuesta es si, dada una recurrencia que se pueda resolver utilizando programación dinámica es casi seguro que se puede implementar una solución con este método. Ahora veremos algunas recurrencias transformadas en matrices para el uso de este metodo. Problemas Tipo 2: Dado el problema hallamos la siguiente función de recurrencia $f(n) = a * f(n-1) + b * f(n-2)$ donde a y b son constantes. Como en el anterior caso construiremos las matrices. $$ {\begin{bmatrix} ? & ?\\ ? & ? \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2) \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ f(n-1) \end{bmatrix}\atop B} $$ Ahora necesitamos incluir en la matriz $M$ los valores $[a, b]$, en el anterior ejemplo pusimos [1, 1] pero ahora necesitamos $a$ veces $f(n-1)$ y $b$ veces $f(n-2)$ entonces agregando esto obtenemos: $$ {\begin{bmatrix} a & b\\ 1 & 0 \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2) \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ f(n-1) \end{bmatrix}\atop B} $$ Problemas Tipo 3: Dado el problema hallamos la siguiente función de recurrencia $f(n) = a * f(n-1) + b * f(n-3)$ donde a y b son constantes. Como en el anterior caso construiremos las matrices, pero esta vez tenemos 3 valores que guardar ya que algun momento necesitaremos usar el valor de $f(n-2)$ aunque no este incluido en la formula. $$ {\begin{bmatrix} ? & ? & ?\\ ? & ? & ?\\ ? & ? & ? \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2)\\ f(n-3) \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ f(n-1)\\ f(n-2) \end{bmatrix}\atop B} $$ Ahora necesitamos incluir en la matriz $M$ los valores $[a, 0, c]$, esto multiplicado con el array A nos dará el correcto valor que buscamos para $f(n)$. $$ {\begin{bmatrix} a & 0 & c\\ . & . & .\\ . & . & . \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2)\\ f(n-3) \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ .\\ . \end{bmatrix}\atop B} $$ Para ver mejor el panorama completo de la multiplicacion podemos ver de la siguiente forma: $$ {\begin{bmatrix} a & 0 & c\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2)\\ f(n-3) \end{bmatrix}\atop A} = {\begin{bmatrix} a * f(n-1) + 0 * f(n-2) + c * f(n-3)\\ 1 * f(n-1) + 0 * f(n-2) + 0 * f(n-3)\\ 0 * f(n-1) + 1 * f(n-2) + 0 * f(n-3) \end{bmatrix}\atop B} $$ Como se puede ver la multiplicación nos da como resultado el valor que buscamos y como en los anteriores casos si estamos buscando el $n-esimo$ valor, solo necesitamos hallar la matriz $M^{n-3}$. Problemas Tipo 4: Para este tipo vemos un elemento extra $f(n) = f(n-1) + f(n-2) + c$ una constante en la formula!!. Como en los otros casos primero creamos las matrices A y B. $$ {\begin{bmatrix} ? & ? & ?\\ ? & ? & ?\\ ? & ? & ? \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2)\\ c \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ f(n-1)\\ c \end{bmatrix}\atop B} $$ Como se puede apreciar no estamos alterando la constante $c$, para eso necesitamos que su valor en la Matriz M sea de 1. $$ {\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{bmatrix}\atop M} \times {\begin{bmatrix} f(n-1)\\ f(n-2)\\ c \end{bmatrix}\atop A} = {\begin{bmatrix} f(n)\\ f(n-1)\\ c \end{bmatrix}\atop B} $$ Podrás apreciar que no importa que valor tome la matriz $M^{n}$ siempre la constante $c$ multiplicada por la matriz se mantendrá en su valor inicial. Conclusion Este método nos ayuda a obtener rápidamente posiciones en una secuencia con ayuda de los valores iniciales.
• Data Structures
  2
  Temas
  2
  Mensajes

  

  Las listas son una de las estructuras básicas para resolver problemas implementando algoritmos. A continuación un ejemplo del uso basico de una lista. #include <iostream> #include <list> int main () { int arrayInts[] = { 75, 23, 65, 42, 13 }; // crea una lista a partir del array std::list<int> milista (arrayInts, arrayInts + 5); milista.push_back(10); // aumenta el numero 10 a la milista. std::cout << "milista contiene:"; // crea un iterador para recorrer milista. std::list<int>::iterator it; // milista.begin() retorna un iterador apuntando al inicio de milista. // milista.end() retorna un iterador apuntando al final de milista. for (it = milista.begin(); it != milista.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; } El anterior código imprime como resultado en consola: milista contiene: 75 23 65 42 13 10 Por el momento no vimos ninguna diferencia entre una lista y un vector o array, pero las listas tienen una gran ventaja a la hora de insertar nuevos números en medio de la lista y también a hora de eliminar números en la lista. La complejidad para insertar un número es de $O(1)$ pero es necesario tener un iterador en el lugar donde necesitas insertar el número entonces si necesitas llegar desde el inicio de la lista buscando un numero en especial necesitarás $O(p)$ pasos utilizando un it++ para ir avanzando. Al igual que insertar para eliminar un valor es necesario un iterador ya que una lista no tiene índices al igual que un array pero si ya estas apuntando al nodo que necesitas eliminar entonces la complejidad será $O(1)$ #include <iostream> #include <list> #include <vector> int main () { std::list<int> mylist; std::list<int>::iterator it; // aca añadimos los valores iniciales for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5 // begin() retorna un puntero al primer valor ^ it = mylist.begin(); ++it; // "it" apunta al numero 2 ^ mylist.insert (it, 10); // 1 10 2 3 4 5 // "it" aun apunta al numero 2 ^ mylist.insert (it, 2, 20); // 1 10 20 20 2 3 4 5 --it; // "it" ahora apunta al segundo 20 ^ std::vector<int> myvector (2, 30); mylist.insert (it,myvector.begin(), myvector.end()); // 1 10 20 30 30 20 2 3 4 5 // ^ std::cout << "mylist contiene:"; for (it=mylist.begin(); it!=mylist.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } El anterior código imprime lo siguiente en la consola: mylist contiene: 1 10 20 30 30 20 2 3 4 5 Cuando utilizo C++ y no recuerdo o necesito buscar algunas estructuras o funciones utilizó cplusplus.com y en este caso los ejemplos fueron una traducción de esta página. referencias: cplusplus list
• Ad-Hoc
  0
  Temas
  0
  Mensajes
  No hay mensajes nuevos.
• Grafos
  4
  Temas
  4
  Mensajes

  

  Existen dos algoritmos básicos para recorrer un grafo o buscar un nodo en particular, la búsqueda por anchura o BFS y la búsqueda por profundidad o DFS. En este artículo explicaremos la búsqueda por profundidad (DFS). El algoritmo de la búsqueda por profundidad se puede hacer modificando el anterior (Parte 3.1 BFS) en la parte que usa una cola y usar una pila. Otra forma de implementarla es usando recursividad, a continuación se muestran ambos enfoques así como la rutina para hacer la búsqueda en grafos que no están completamente conectados. A continuación se presenta el listado con la implementación de la búsqueda por profundidad o DFS. También se ha añadido en la versión recursiva un contador que marca el orden en el que fueron visitados los nodos del grafo, dicho orden es muy útil al implementar otros algoritmos de grafos. Implementación DFS (usando una pila) int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { //v es el nodo de inicio del recorrido list<int> pila; //pila de nodos adyacentes list<int>::iterator nodo_actual, aux, fin; visitado[v] = 1; //marcar como visitado el nodo de inicio pila.push_back(v); while (!pila.empty()) { //mientras no se vacie la pila de adyacentes nodo_actual = pila.back(); //aqui podriamos marcar el orden en que se visitaron pila.pop_back(); aux = grafo[nodo_actual].begin(); // posicionar iteradores para // lista adyacente fin = grafo[nodo_actual].end(); while (aux != fin) { //recorrer todos los adyacente al nodo actual if (!visitado[*aux]) { //añadir a la pila solo los no visitados visitado[*aux] = 1; pila.push_back(*aux); //aqui podemos añadir código para hacer algo mientras //realizamos el recorrido } aux++; //avanzar al siguiente adyacente del nodo actual } } } Implementacion DFS (recursiva) int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { list<int>::iterator aux, fin; //iteradores para lista de ady visitado[v] = 1; //marcar como visitado //aqui se podria marcar el orden en que fueron visitados aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { if (!visitado[*aux]) DFS(*aux); //no se necesita marcar porque *aux se convierte en v aux++; //avanzar al siguiente adyacente de v } } //esta es la version para grafos que no estan completamente conectados void DFS2() { int i; for (int i = 0; i < nvert; i++) //buscar un nuevo nodo de if (!visitado[i]) //inicio que no ha sido visitado DFS(i); } En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados al final, en este caso los números que se encuentran en la pila tienen como primer número al último que fue ingresado. Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0). 0. Inicio DFS(0) nodoActual = -1, pila = [0] 1. Sacamos el primer nodo de la pila nodoActual = 0, pila = [] 2. 0 visitara a DFS(1) y DFS(3) nodoActual = 0, pila = [1, 3] 3. Sacamos el primer nodo de la pila nodoActual = 3, pila = [1] 4. 3 visitara a DFS(2) y DFS(4) nodoActual = 3, pila = [1, 2, 4] 5. Sacamos el primer nodo de la pila nodoActual = 4, pila = [1, 2] 6. 4 no visita a ningun nodo nodoActual = 4, pila = [1, 2] 7. Sacamos el primer nodo de la pila nodoActual = 2, pila = [1] 8. 2 visitara a DFS(4) pero 4 ya fue visitado nodoActual = 2, pila = [1] 9. Sacamos el primer nodo de la pila nodoActual = 1, pila = [] 10. El algoritmo termina por la pila esta vacía En el caso de la implementación recursiva deberán hacerla correr con un ejemplo de grafo para poder analizar la pila, cuando las funciones se llaman recursivamente verán que no se llama a una sin que termine la última en ser llamada y a su vez esperará hasta que todas las funciones llamadas por la otra función sean terminadas. #include <iostream> #include <vector> #include <list> using namespace std; int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { list<int>::iterator aux, fin; //iteradores para lista de ady visitado[v] = 1; //marcar como visitado //aqui se podria marcar el orden en que fueron visitados cout << v << " fue visitado" << endl; aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { // este ciclo extra esta para imprimir los siguientes nodos cout << '\t' << (*aux) << " sera visitado por " << v << endl; aux++; //avanzar al siguiente adyacente de v } aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { if (!visitado[*aux]) DFS(*aux); //no se necesita marcar porque *aux se convierte en v aux++; //avanzar al siguiente adyacente de v } } int main() { // conectamos el grafo grafo[0].push_back(1); grafo[0].push_back(3); grafo[1].push_back(2); grafo[1].push_back(3); grafo[2].push_back(4); grafo[3].push_back(2); grafo[3].push_back(4); // llamamos a la funcion DFS DFS(0); } Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces: HackerEarth Problems - Depth First Search CP3 - Chapter 4. Graph - Depth First Search
• Cadenas/Strings
  1
  Temas
  1
  Mensajes

  

  Nota: si aun no sabes usar Arrays de Caracteres/Cadenas te invito a leer el siguiente enlace Arrays en C++ (basico) Problema: Super Reduced String (facil/easy) En este problema te dan una cadena a la cual tienes que ir eliminando todos los pares de caracteres que vayas encontrando, mientras aun tenga pares debes seguir reduciendo la cadena. Entrada: Una cadena s de caracteres en una linea. La cadena s solo contiene letras y la longitud es menor o igual que 100, $1 < |s| \leq 100$ Salida La cadena de caracteres sin ningún par de caracteres continuo. Ejemplo Si nos dan de entrada la siguiente cadena daacbbcdxyxy despues de ir eliminando los pares de caracteres seguidos como resultado tiene que imprimir xyxy. inicial: daacbbcdxyxy eliminacion 1: d(aa)c(bb)cdxyxy -> dccdxyxy eliminacion 2: d(cc)dxyxy -> ddxyxy eliminacion 3: (dd)xyxy -> xyxy resultado: xyxy Solucion En este problem lo único que necesitamos es recorrer la cadena e ir eliminando los caracteres continuos iguales. Para eliminar los caracteres simplemente iremos copiando la cadena antigua en una nueva pero saltandonos los caracteres iguales continuos. #include <cstdio> #include <iostream> #include <cstring> #include <fstream> using namespace std; char s[101]; char auxS[101]; int main() { gets(s); int n; bool hayMasCambios = true; while (hayMasCambios) { hayMasCambios = false; // si no existen cambios terminar ciclo n = strlen(s); // actual tamaño de s int itS = 0; for (int i = 0; i < n ; i++) { // recorrer s if (i + 1 < n) { if (s[i] == s[i + 1]) { i++; // saltar caracteres iguales continuos hayMasCambios = true; // aun es posible mas reduccion ? } else { auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada } } else { auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada } } auxS[itS] = '\0'; // aumentar 0 al final de la cadena limitando su tamaño strcpy(s, auxS); // copiar auxS -> s } if (n == 0) { cout << "Empty String\n"; } else { cout << s << "\n"; } return 0; } Enlace Original del problema: HackerRank - Super Reduced String (english)