You've learned this already. ✅
Click here to view the next lesson.
Capítulo 7: Dominando Técnicas Algorítmicas
Ejercicios Prácticos para el Capítulo 7
Aquí hay algunos ejercicios prácticos centrados en el enfoque Greedy y el Backtracking, completos con sus soluciones.
Estos ejercicios tienen como objetivo ofrecerte experiencia directa tanto con el método Greedy como con el Backtracking. Están diseñados para profundizar tu comprensión de estas estrategias algorítmicas influyentes. A medida que abordes estos ejercicios, adquirirás habilidades prácticas en el uso de estas técnicas para abordar desafíos complejos.
Ejercicio 1: Implementar un Algoritmo Greedy para el Problema del Cambio de Monedas
- Dadas un conjunto de denominaciones de monedas y una cantidad total, escribe una función para calcular el número mínimo de monedas necesarias para alcanzar esa cantidad.
- Ejemplo de denominaciones:
[1, 5, 10, 25]y cantidad:63.
Solución:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Ejercicio 2: Implementar Backtracking para el Problema de las N-Reinas
- Escribe una función para resolver el rompecabezas de las N-Reinas para un valor dado de N.
- Ejemplo de N:
4.
Solución:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Ejercicio 3: Algoritmo Voraz para el Problema de Selección de Actividades
- Dada una lista de actividades con sus tiempos de inicio y finalización, implementa un algoritmo voraz para seleccionar el máximo número de actividades que no se superponen.
- Ejemplo de actividades:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solución:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Ejercicios Prácticos para el Capítulo 7
Aquí hay algunos ejercicios prácticos centrados en el enfoque Greedy y el Backtracking, completos con sus soluciones.
Estos ejercicios tienen como objetivo ofrecerte experiencia directa tanto con el método Greedy como con el Backtracking. Están diseñados para profundizar tu comprensión de estas estrategias algorítmicas influyentes. A medida que abordes estos ejercicios, adquirirás habilidades prácticas en el uso de estas técnicas para abordar desafíos complejos.
Ejercicio 1: Implementar un Algoritmo Greedy para el Problema del Cambio de Monedas
- Dadas un conjunto de denominaciones de monedas y una cantidad total, escribe una función para calcular el número mínimo de monedas necesarias para alcanzar esa cantidad.
- Ejemplo de denominaciones:
[1, 5, 10, 25]y cantidad:63.
Solución:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Ejercicio 2: Implementar Backtracking para el Problema de las N-Reinas
- Escribe una función para resolver el rompecabezas de las N-Reinas para un valor dado de N.
- Ejemplo de N:
4.
Solución:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Ejercicio 3: Algoritmo Voraz para el Problema de Selección de Actividades
- Dada una lista de actividades con sus tiempos de inicio y finalización, implementa un algoritmo voraz para seleccionar el máximo número de actividades que no se superponen.
- Ejemplo de actividades:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solución:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Ejercicios Prácticos para el Capítulo 7
Aquí hay algunos ejercicios prácticos centrados en el enfoque Greedy y el Backtracking, completos con sus soluciones.
Estos ejercicios tienen como objetivo ofrecerte experiencia directa tanto con el método Greedy como con el Backtracking. Están diseñados para profundizar tu comprensión de estas estrategias algorítmicas influyentes. A medida que abordes estos ejercicios, adquirirás habilidades prácticas en el uso de estas técnicas para abordar desafíos complejos.
Ejercicio 1: Implementar un Algoritmo Greedy para el Problema del Cambio de Monedas
- Dadas un conjunto de denominaciones de monedas y una cantidad total, escribe una función para calcular el número mínimo de monedas necesarias para alcanzar esa cantidad.
- Ejemplo de denominaciones:
[1, 5, 10, 25]y cantidad:63.
Solución:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Ejercicio 2: Implementar Backtracking para el Problema de las N-Reinas
- Escribe una función para resolver el rompecabezas de las N-Reinas para un valor dado de N.
- Ejemplo de N:
4.
Solución:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Ejercicio 3: Algoritmo Voraz para el Problema de Selección de Actividades
- Dada una lista de actividades con sus tiempos de inicio y finalización, implementa un algoritmo voraz para seleccionar el máximo número de actividades que no se superponen.
- Ejemplo de actividades:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solución:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Ejercicios Prácticos para el Capítulo 7
Aquí hay algunos ejercicios prácticos centrados en el enfoque Greedy y el Backtracking, completos con sus soluciones.
Estos ejercicios tienen como objetivo ofrecerte experiencia directa tanto con el método Greedy como con el Backtracking. Están diseñados para profundizar tu comprensión de estas estrategias algorítmicas influyentes. A medida que abordes estos ejercicios, adquirirás habilidades prácticas en el uso de estas técnicas para abordar desafíos complejos.
Ejercicio 1: Implementar un Algoritmo Greedy para el Problema del Cambio de Monedas
- Dadas un conjunto de denominaciones de monedas y una cantidad total, escribe una función para calcular el número mínimo de monedas necesarias para alcanzar esa cantidad.
- Ejemplo de denominaciones:
[1, 5, 10, 25]y cantidad:63.
Solución:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Ejercicio 2: Implementar Backtracking para el Problema de las N-Reinas
- Escribe una función para resolver el rompecabezas de las N-Reinas para un valor dado de N.
- Ejemplo de N:
4.
Solución:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Ejercicio 3: Algoritmo Voraz para el Problema de Selección de Actividades
- Dada una lista de actividades con sus tiempos de inicio y finalización, implementa un algoritmo voraz para seleccionar el máximo número de actividades que no se superponen.
- Ejemplo de actividades:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solución:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]