4.5 Problemas de práctica

Problema 1: Búsqueda Binaria (Divide y Conquista)

Dada una lista ordenada de n enteros y un entero objetivo x, escribe una función que encuentre la posición de x en la lista usando un algoritmo de búsqueda binaria. Recuerda, la búsqueda binaria opera dividiendo efectivamente el problema a la mitad con cada paso.

Solución:

def binary_search(list, x):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (high + low) // 2

        if list[mid] < x:
            low = mid + 1
        elif list[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

Problema 2: Cambio de Monedas (Algoritmo Voraz)

Dada una lista de denominaciones de monedas y un valor n, escribe una función que calcule el número mínimo de monedas necesarias para hacer cambio por n. Utiliza un algoritmo voraz que siempre selecciona la denominación más grande menor o igual al monto restante a cambiar. Prueba tu función con varios conjuntos de monedas, como las denominaciones estándar de EE. UU. o euros.

Solución:

def coin_change(coins, n):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while n >= coin:
            n -= coin
            count += 1
        if n == 0:
            return count
    return count

Problema 3: Serie Fibonacci (Programación Dinámica)

Escribe una función para calcular el enésimo número de Fibonacci. La serie de Fibonacci se define como: F(0) = 0, F(1) = 1, y F(n) = F(n-1) + F(n-2) para n > 1. Primero, implementa esto usando recursión simple, luego optimiza tu función usando programación dinámica para almacenar y reutilizar valores calculados.

Solución:

def fibonacci(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fibonacci(n - 1, computed) + fibonacci(n - 2, computed)
    return computed[n]

Problema 4: Suma de Números Naturales (Algoritmo Recursivo)

Escribe una función que calcule la suma de todos los números naturales desde 1 hasta n usando un algoritmo recursivo. Compara la solución recursiva con una solución iterativa y discute las diferencias.

Solución:

def recursive_sum(n):
    if n <= 1:
        return n
    else:
        return n + recursive_sum(n - 1)

def iterative_sum(n):
    return n * (n + 1) // 2

Problema 5: QuickSort (Divide y Conquista)

Implementa el algoritmo QuickSort que ordena una matriz de enteros. QuickSort es un algoritmo de Divide y Conquista. Elige un elemento como pivote y particiona la matriz dada alrededor del pivote seleccionado.

Solución:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Problema 6: Implementación de una Pila usando Recursión (Algoritmo Recursivo)

Implementa una estructura de datos de pila utilizando recursión. Tu pila debería tener funciones push, pop, y peek.

Solución:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

    def peek(self):
        if self.stack:
            return self.stack[-1]
        return None

Recuerda, el objetivo de estos problemas prácticos es obtener una comprensión práctica de los diferentes tipos de algoritmos, cómo funcionan y dónde se pueden aplicar. Intenta resolver todos los problemas y compara las soluciones para ver la diferencia entre estos tipos de algoritmos. ¡Buena suerte!

En el próximo capítulo, exploraremos tipos de algoritmos más avanzados y sus aplicaciones en la resolución de problemas del mundo real. ¡Mantente atento!