Capítulo 9: Técnicas de Diseño de Algoritmos
9.5 Problemas Prácticos
Estamos emocionados de ofrecerte algunos problemas prácticos que te permiten aplicar las técnicas que hemos discutido en este capítulo. Estos problemas te ayudarán a probar tu comprensión y aplicar el conocimiento que has adquirido.
1. Recursión: Serie Fibonacci
Escribe una función recursiva que genere el enésimo número en la serie Fibonacci. Recuerda, la secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, generalmente comenzando con 0 y 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Enfoque Iterativo: Factorial
Escribe una función iterativa que calcule el factorial de un número dado. El factorial de un entero no negativo n es el producto de todos los enteros positivos menores o iguales a n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: Problema de las N-Reinas
El rompecabezas de las N reinas es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N×N de manera que ninguna reina amenace a otra. Por lo tanto, una solución requiere que ninguna dos reinas compartan la misma fila, columna o diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Ramificación y Acotación: Problema del Viajante de Comercio
El problema del viajante de comercio (TSP) plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?"
TSP es un problema NP-duro en la optimización combinatoria, importante en la investigación de operaciones y la informática teórica. Aunque es difícil proporcionar una solución óptima para entradas grandes, es una buena práctica comprender el método de ramificación y acotación.
Nota: Escribir un código eficiente para TSP utilizando ramificación y acotación puede ser bastante complejo y puede no ser adecuado como un ejercicio inicial para aprender ramificación y acotación. Se recomienda revisar los aspectos teóricos de este problema e intentar comprender cómo la ramificación y acotación pueden ayudar a podar el espacio de búsqueda.
Estos problemas deberían brindarte una buena práctica para entender estas técnicas. Intenta resolverlos y, si encuentras algún problema, no dudes en buscar soluciones y explicaciones. El objetivo es aprender, y el aprendizaje lleva su propio tiempo y ritmo. No te apresures, disfruta del proceso de resolver estos problemas. ¡Feliz codificación!
9.5 Problemas Prácticos
Estamos emocionados de ofrecerte algunos problemas prácticos que te permiten aplicar las técnicas que hemos discutido en este capítulo. Estos problemas te ayudarán a probar tu comprensión y aplicar el conocimiento que has adquirido.
1. Recursión: Serie Fibonacci
Escribe una función recursiva que genere el enésimo número en la serie Fibonacci. Recuerda, la secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, generalmente comenzando con 0 y 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Enfoque Iterativo: Factorial
Escribe una función iterativa que calcule el factorial de un número dado. El factorial de un entero no negativo n es el producto de todos los enteros positivos menores o iguales a n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: Problema de las N-Reinas
El rompecabezas de las N reinas es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N×N de manera que ninguna reina amenace a otra. Por lo tanto, una solución requiere que ninguna dos reinas compartan la misma fila, columna o diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Ramificación y Acotación: Problema del Viajante de Comercio
El problema del viajante de comercio (TSP) plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?"
TSP es un problema NP-duro en la optimización combinatoria, importante en la investigación de operaciones y la informática teórica. Aunque es difícil proporcionar una solución óptima para entradas grandes, es una buena práctica comprender el método de ramificación y acotación.
Nota: Escribir un código eficiente para TSP utilizando ramificación y acotación puede ser bastante complejo y puede no ser adecuado como un ejercicio inicial para aprender ramificación y acotación. Se recomienda revisar los aspectos teóricos de este problema e intentar comprender cómo la ramificación y acotación pueden ayudar a podar el espacio de búsqueda.
Estos problemas deberían brindarte una buena práctica para entender estas técnicas. Intenta resolverlos y, si encuentras algún problema, no dudes en buscar soluciones y explicaciones. El objetivo es aprender, y el aprendizaje lleva su propio tiempo y ritmo. No te apresures, disfruta del proceso de resolver estos problemas. ¡Feliz codificación!
9.5 Problemas Prácticos
Estamos emocionados de ofrecerte algunos problemas prácticos que te permiten aplicar las técnicas que hemos discutido en este capítulo. Estos problemas te ayudarán a probar tu comprensión y aplicar el conocimiento que has adquirido.
1. Recursión: Serie Fibonacci
Escribe una función recursiva que genere el enésimo número en la serie Fibonacci. Recuerda, la secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, generalmente comenzando con 0 y 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Enfoque Iterativo: Factorial
Escribe una función iterativa que calcule el factorial de un número dado. El factorial de un entero no negativo n es el producto de todos los enteros positivos menores o iguales a n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: Problema de las N-Reinas
El rompecabezas de las N reinas es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N×N de manera que ninguna reina amenace a otra. Por lo tanto, una solución requiere que ninguna dos reinas compartan la misma fila, columna o diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Ramificación y Acotación: Problema del Viajante de Comercio
El problema del viajante de comercio (TSP) plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?"
TSP es un problema NP-duro en la optimización combinatoria, importante en la investigación de operaciones y la informática teórica. Aunque es difícil proporcionar una solución óptima para entradas grandes, es una buena práctica comprender el método de ramificación y acotación.
Nota: Escribir un código eficiente para TSP utilizando ramificación y acotación puede ser bastante complejo y puede no ser adecuado como un ejercicio inicial para aprender ramificación y acotación. Se recomienda revisar los aspectos teóricos de este problema e intentar comprender cómo la ramificación y acotación pueden ayudar a podar el espacio de búsqueda.
Estos problemas deberían brindarte una buena práctica para entender estas técnicas. Intenta resolverlos y, si encuentras algún problema, no dudes en buscar soluciones y explicaciones. El objetivo es aprender, y el aprendizaje lleva su propio tiempo y ritmo. No te apresures, disfruta del proceso de resolver estos problemas. ¡Feliz codificación!
9.5 Problemas Prácticos
Estamos emocionados de ofrecerte algunos problemas prácticos que te permiten aplicar las técnicas que hemos discutido en este capítulo. Estos problemas te ayudarán a probar tu comprensión y aplicar el conocimiento que has adquirido.
1. Recursión: Serie Fibonacci
Escribe una función recursiva que genere el enésimo número en la serie Fibonacci. Recuerda, la secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos anteriores, generalmente comenzando con 0 y 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Enfoque Iterativo: Factorial
Escribe una función iterativa que calcule el factorial de un número dado. El factorial de un entero no negativo n es el producto de todos los enteros positivos menores o iguales a n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: Problema de las N-Reinas
El rompecabezas de las N reinas es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N×N de manera que ninguna reina amenace a otra. Por lo tanto, una solución requiere que ninguna dos reinas compartan la misma fila, columna o diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Ramificación y Acotación: Problema del Viajante de Comercio
El problema del viajante de comercio (TSP) plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?"
TSP es un problema NP-duro en la optimización combinatoria, importante en la investigación de operaciones y la informática teórica. Aunque es difícil proporcionar una solución óptima para entradas grandes, es una buena práctica comprender el método de ramificación y acotación.
Nota: Escribir un código eficiente para TSP utilizando ramificación y acotación puede ser bastante complejo y puede no ser adecuado como un ejercicio inicial para aprender ramificación y acotación. Se recomienda revisar los aspectos teóricos de este problema e intentar comprender cómo la ramificación y acotación pueden ayudar a podar el espacio de búsqueda.
Estos problemas deberían brindarte una buena práctica para entender estas técnicas. Intenta resolverlos y, si encuentras algún problema, no dudes en buscar soluciones y explicaciones. El objetivo es aprender, y el aprendizaje lleva su propio tiempo y ritmo. No te apresures, disfruta del proceso de resolver estos problemas. ¡Feliz codificación!