El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios de Diseño de Algoritmos

Siguiente ►
►

En esta sección, pondremos en práctica las estrategias de diseño de algoritmos que hemos aprendido en los módulos anteriores. Nos enfocaremos en ejercicios que abarcan las técnicas de "Divide y Vencerás", "Algoritmos Greedy", "Programación Dinámica" y "Backtracking". Cada ejercicio incluirá una descripción del problema, una solución detallada y explicaciones paso a paso.

Ejercicio 1: Divide y Vencerás

Problema: Suma Máxima de Subarreglo

Dado un arreglo de números enteros, encuentra el subarreglo (contiguo) que tiene la suma máxima y devuelve su suma.

Ejemplo:

Entrada: [-2,1,-3,4,-1,2,1,-5,4]
Salida: 6
Explicación: El subarreglo [4,-1,2,1] tiene la suma máxima de 6.

Solución:

Usaremos la técnica de "Divide y Vencerás" para resolver este problema.

Paso 1: Dividir

Dividimos el arreglo en dos mitades.

Paso 2: Conquistar

Recursivamente encontramos la suma máxima de subarreglo en las dos mitades.

Paso 3: Combinar

Encontramos la suma máxima de subarreglo que cruza la mitad y combinamos los resultados.

Código:

def max_crossing_sum(arr, left, mid, right):
    # Incluye elementos en la suma desde el medio hacia la izquierda
    left_sum = float('-inf')
    total = 0
    for i in range(mid, left-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total
    
    # Incluye elementos en la suma desde el medio hacia la derecha
    right_sum = float('-inf')
    total = 0
    for i in range(mid + 1, right + 1):
        total += arr[i]
        if total > right_sum:
            right_sum = total
    
    # Devuelve la suma máxima que cruza el medio
    return left_sum + right_sum

def max_subarray_sum(arr, left, right):
    # Caso base: solo un elemento
    if left == right:
        return arr[left]
    
    # Encuentra el punto medio
    mid = (left + right) // 2
    
    # Devuelve el máximo de las tres posibles sumas
    return max(max_subarray_sum(arr, left, mid),
               max_subarray_sum(arr, mid+1, right),
               max_crossing_sum(arr, left, mid, right))

# Ejemplo de uso
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr, 0, len(arr) - 1)
print("La suma máxima de subarreglo es:", result)

Explicación:

  1. max_crossing_sum: Calcula la suma máxima de un subarreglo que cruza el punto medio.
  2. max_subarray_sum: Utiliza recursión para dividir el arreglo y encontrar la suma máxima en cada mitad y la suma máxima cruzada.
  3. Caso base: Si el subarreglo tiene un solo elemento, devuelve ese elemento.
  4. Combinación: Devuelve el máximo de las tres posibles sumas.

Ejercicio 2: Algoritmos Greedy

Problema: Actividades Máximas

Dado un conjunto de actividades con tiempos de inicio y finalización, selecciona el máximo número de actividades que no se solapen.

Ejemplo:

Entrada: [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
Salida: [(1, 3), (4, 6), (6, 7)]

Solución:

Usaremos un enfoque greedy para resolver este problema.

Paso 1: Ordenar

Ordenamos las actividades por su tiempo de finalización.

Paso 2: Seleccionar

Seleccionamos la actividad que termina primero y luego seleccionamos la siguiente actividad que empieza después de que la actividad seleccionada haya terminado.

Código:

def max_activities(activities):
    # Ordena las actividades por su tiempo de finalización
    activities.sort(key=lambda x: x[1])
    
    # La primera actividad siempre se selecciona
    selected_activities = [activities[0]]
    last_end_time = activities[0][1]
    
    # Recorre las actividades restantes
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:
            selected_activities.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected_activities

# Ejemplo de uso
activities = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8)]
result = max_activities(activities)
print("Las actividades seleccionadas son:", result)

Explicación:

  1. Ordenar: Las actividades se ordenan por su tiempo de finalización.
  2. Seleccionar: Se selecciona la primera actividad y luego se seleccionan las siguientes actividades que no se solapen con las seleccionadas previamente.

Ejercicio 3: Programación Dinámica

Problema: Problema de la Mochila (0/1 Knapsack)

Dado un conjunto de elementos, cada uno con un peso y un valor, determina el número de cada elemento que se puede incluir en una colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

Ejemplo:

Entrada: pesos = [1, 3, 4, 5], valores = [1, 4, 5, 7], capacidad = 7
Salida: 9
Explicación: Se seleccionan los elementos con pesos 3 y 4, que tienen un valor total de 9.

Solución:

Usaremos programación dinámica para resolver este problema.

Paso 1: Definir la DP

Definimos dp[i][w] como el valor máximo que se puede obtener usando los primeros i elementos con un peso máximo de w.

Paso 2: Recurrencia

Para cada elemento, tenemos dos opciones: incluirlo o no incluirlo.

Código:

def knapsack(valores, pesos, capacidad):
    n = len(valores)
    dp = [[0 for x in range(capacidad + 1)] for x in range(n + 1)]
    
    # Construye la tabla dp de abajo hacia arriba
    for i in range(n + 1):
        for w in range(capacidad + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif pesos[i-1] <= w:
                dp[i][w] = max(valores[i-1] + dp[i-1][w-pesos[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacidad]

# Ejemplo de uso
pesos = [1, 3, 4, 5]
valores = [1, 4, 5, 7]
capacidad = 7
result = knapsack(valores, pesos, capacidad)
print("El valor máximo que se puede obtener es:", result)

Explicación:

  1. Tabla DP: Se construye una tabla dp donde dp[i][w] representa el valor máximo que se puede obtener con los primeros i elementos y un peso máximo de w.
  2. Recurrencia: Para cada elemento, se decide si incluirlo o no, y se actualiza la tabla dp en consecuencia.

Ejercicio 4: Backtracking

Problema: N-Reinas

Coloca N reinas en un tablero de ajedrez NxN de manera que ninguna reina pueda atacar a otra.

Ejemplo:

Entrada: N = 4
Salida: 
[
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

Solución:

Usaremos backtracking para resolver este problema.

Paso 1: Colocar Reinas

Intentamos colocar una reina en cada fila y verificamos si la posición es segura.

Paso 2: Recursión

Si la posición es segura, colocamos la reina y procedemos a la siguiente fila.

Paso 3: Retroceder

Si no se puede colocar una reina en ninguna columna de la fila actual, retrocedemos y movemos la reina de la fila anterior.

Código:

def is_safe(board, row, col, N):
    # Verifica la columna
    for i in range(row):
        if board[i][col] == 'Q':
            return False
    
    # Verifica la diagonal superior izquierda
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 'Q':
            return False
    
    # Verifica la diagonal superior derecha
    for i, j in zip(range(row, -1, -1), range(col, N)):
        if board[i][j] == 'Q':
            return False
    
    return True

def solve_n_queens_util(board, row, N, solutions):
    if row >= N:
        solutions.append(["".join(row) for row in board])
        return
    
    for col in range(N):
        if is_safe(board, row, col, N):
            board[row][col] = 'Q'
            solve_n_queens_util(board, row + 1, N, solutions)
            board[row][col] = '.'

def solve_n_queens(N):
    board = [['.' for _ in range(N)] for _ in range(N)]
    solutions = []
    solve_n_queens_util(board, 0, N, solutions)
    return solutions

# Ejemplo de uso
N = 4
result = solve_n_queens(N)
print("Las soluciones para el problema de las N-Reinas son:")
for solution in result:
    for row in solution:
        print(row)
    print()

Explicación:

  1. is_safe: Verifica si es seguro colocar una reina en una posición dada.
  2. solve_n_queens_util: Utiliza backtracking para colocar reinas en el tablero.
  3. solve_n_queens: Inicializa el tablero y llama a la función recursiva para encontrar todas las soluciones.

Conclusión

En esta sección, hemos practicado diversas estrategias de diseño de algoritmos mediante ejercicios prácticos. Hemos cubierto técnicas de "Divide y Vencerás", "Algoritmos Greedy", "Programación Dinámica" y "Backtracking". Cada ejercicio ha sido acompañado de una solución detallada y explicaciones paso a paso para asegurar una comprensión profunda de los conceptos.

En el siguiente módulo, nos enfocaremos en la optimización de algoritmos, donde aprenderemos técnicas para mejorar el rendimiento y la eficiencia de nuestros códigos.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados