Requisitos previos : recursividad Análisis de Complejidad retrocediendoes una técnica algorítmica para resolver problemas recursivamente al tratar de construir una solución de forma incremental, una pieza a la vez, eliminando aquellas soluciones que no satisfacen las restricciones del problema en cualquier punto en el tiempo (por tiempo, aquí, se hace referencia al tiempo transcurrido hasta … Continue reading «Retrocediendo | Introducción»
Dado un grafo no dirigido , un vértice de origen ‘s’ y un vértice de destino ‘d’ , la tarea es contar los caminos totales desde el ‘s’ dado hasta la ‘d’ . Ejemplos Entrada: s = 1, d = 4 Salida: 2 Explicación: A continuación se muestran los 2 caminos del 1 al 4 … Continue reading «Cuente las formas totales de llegar al destino desde la fuente en un gráfico no dirigido»
Backtracking es un paradigma algorítmico que prueba diferentes soluciones hasta encontrar una solución que “funciona”. Los problemas que normalmente se resuelven utilizando la técnica de retroceso tienen la siguiente propiedad en común. Estos problemas solo se pueden resolver probando todas las configuraciones posibles y cada configuración se intenta solo una vez. Una solución ingenua para … Continue reading «El problema de la gira del Caballero | Retrocediendo-1»
Dada una array de enteros de N elementos, la tarea es dividir esta array en K subconjuntos no vacíos de modo que la suma de los elementos en cada subconjunto sea la misma. Todos los elementos de esta array deben ser parte de exactamente una partición. Ejemplos: Input : arr = [2, 1, 4, 5, 6], … Continue reading «Partición de un conjunto en K subconjuntos con igual suma»
Dado un laberinto cuadrado que contiene números positivos, encuentre todos los caminos desde una celda de la esquina (cualquiera de las cuatro esquinas extremas) hasta la celda del medio. Podemos movernos exactamente n pasos desde una celda en 4 direcciones, es decir, norte, este, oeste y sur, donde n es el valor de la celda … Continue reading «Encuentre caminos desde la celda de la esquina hasta la celda del medio en el laberinto»
Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma de todos los subconjuntos de una array , cuya suma es un Número perfecto . Ejemplos: Entrada: arr[] = {5, 4, 6} Salida: 6 Explicación: Todos los subconjuntos posibles de la array arr[] son: {5} → Sum = 5 {4} … Continue reading «Suma de todos los subconjuntos cuya suma es un número perfecto de una array dada»
Dado un grafo no dirigido definido por el número de vértices V y las aristas E[ ] , la tarea es encontrar el conjunto máximo de vértices independientes en un grafo no dirigido. Conjunto independiente: Un conjunto independiente en un gráfico es un conjunto de vértices que no están conectados directamente entre sí. Nota: Es … Continue reading «Conjunto independiente máximo en un gráfico no dirigido»
Dada una array de enteros y un número K. La tarea es encontrar la suma máxima que es divisible por K de la array dada. Ejemplos: Entrada: arr[] = {3, 6, 5, 1, 8}, k = 3 Salida: 18 Explicación: 18 está formado por los elementos 3, 6, 1, 8. Entrada: arr = { 43, … Continue reading «Suma máxima de elementos divisibles por K de la array dada»
Dada una array arr[] de N enteros y un entero K , la tarea es verificar si la expresión formada para cualquier permutación de la array dada después de asignar operadores aritméticos ( +, -, /, * ) da el valor K o no. Si es cierto, imprima el orden de las operaciones realizadas. De … Continue reading «Compruebe si se puede obtener K realizando operaciones aritméticas en cualquier permutación de un Array»
Dado un número entero N , la tarea de dos jugadores A y B es hacer que el valor de X ( inicializado con 1 ) sea al menos N multiplicando X con cualquier número del rango [2, 9] en turnos alternos. Suponiendo que ambos jugadores jueguen de manera óptima. la tarea es encontrar el … Continue reading «Encuentre el jugador que alcance al menos N multiplicando con cualquier valor del rango dado»