10 Ejercicios de Algoritmia en Python: Pilas, Colas, Recursividad y Matrices

Bienvenidos a una nueva entrega en larebelion.com. Si ya dominas la sintaxis básica y la Orientación a Objetos, es hora de enfrentarse al verdadero reto de la Ingeniería Informática: la Algoritmia.

En este post hemos recopilado 10 ejercicios de exámenes enfocados en estructuras de datos lineales (Pilas y Colas), matrices y recursividad avanzada. Dominar esto es la clave para superar asignaturas como Estructuras de Datos y Algoritmos.

---

31. Pilas (Stacks): Paréntesis Balanceados (UPM)

Enunciado: Implementa una función que use una Pila (Stack) para verificar si una cadena de texto tiene los paréntesis (), corchetes [] y llaves {} correctamente balanceados.

def esta_balanceado(cadena):
    pila = []
    pares = {')': '(', ']': '[', '}': '{'}
    for char in cadena:
        if char in pares.values():
            pila.append(char)
        elif char in pares.keys():
            if not pila or pila.pop() != pares[char]:
                return False
    return len(pila) == 0

32. Colas (Queues): Simulación de Impresora (UPC)

Enunciado: Usando collections.deque, simula una cola de impresión donde se añaden documentos y se imprimen (procesan) en orden FIFO (First In, First Out).

from collections import deque

class ColaImpresion:
    def __init__(self): self.cola = deque()

    def agregar_trabajo(self, documento):
        self.cola.append(documento)

    def imprimir(self):
        if self.cola:
            return self.cola.popleft()
        return "Sin trabajos"

33. Matrices: Suma de la Diagonal Principal (UGR)

Enunciado: Dada una matriz cuadrada (lista de listas), calcula la suma de los elementos de su diagonal principal.

def suma_diagonal(matriz):
    # Usando comprensión de listas para mayor elegancia
    return sum(matriz[i][i] for i in range(len(matriz)))

34. Matrices: Multiplicación de Matrices (UC3M)

Enunciado: Escribe un algoritmo de complejidad $O(n^3)$ que multiplique dos matrices A y B, devolviendo la matriz resultante.

def multiplicar_matrices(A, B):
    filas_A, cols_A = len(A), len(A[0])
    cols_B = len(B[0])
    C = [[0 for _ in range(cols_B)] for _ in range(filas_A)]
    for i in range(filas_A):
        for j in range(cols_B):
            for k in range(cols_A):
                C[i][j] += A[i][k] * B[k][j]
    return C

35. Recursividad: Torres de Hanoi (UCM)

Enunciado: Implementa el clásico problema de las Torres de Hanoi recursivamente, imprimiendo los movimientos necesarios para trasladar n discos.

def hanoi(n, origen, destino, auxiliar):
    if n == 1:
        print(f"Mover disco 1 de {origen} a {destino}")
        return
    hanoi(n-1, origen, auxiliar, destino)
    print(f"Mover disco {n} de {origen} a {destino}")
    hanoi(n-1, auxiliar, destino, origen)

36. Recursividad: Algoritmo de Euclides (USAL)

Enunciado: Calcula el Máximo Común Divisor (MCD) de dos números enteros utilizando la versión recursiva del algoritmo de Euclides.

def mcd_euclides(a, b):
    # Caso base: si el resto es 0, el MCD es 'a'
    if b == 0:
        return a
    # Llamada recursiva con b y el resto de a/b
    return mcd_euclides(b, a % b)

37. Recursividad: Suma de Dígitos (UNED)

Enunciado: Escribe una función recursiva que reciba un número entero positivo y devuelva la suma de todos sus dígitos.

def suma_digitos(n):
    if n == 0:
        return 0
    return (n % 10) + suma_digitos(n // 10)

38. Algoritmos de Ordenación: Bubble Sort (UV)

Enunciado: Implementa el algoritmo de Ordenación de Burbuja (Bubble Sort). Aunque es de complejidad $O(n^2)$, es un clásico que siempre cae en exámenes de primero.

def bubble_sort(lista):
    n = len(lista)
    for i in range(n):
        for j in range(0, n-i-1):
            if lista[j] > lista[j+1]:
                # Intercambio de variables
                lista[j], lista[j+1] = lista[j+1], lista[j]
    return lista

39. Algoritmos de Ordenación: Selection Sort (UAM)

Enunciado: Implementa la Ordenación por Selección (Selection Sort), buscando el elemento mínimo en cada iteración y colocándolo al principio.

def selection_sort(lista):
    for i in range(len(lista)):
        min_idx = i
        for j in range(i+1, len(lista)):
            if lista[j] < lista[min_idx]:
                min_idx = j
        lista[i], lista[min_idx] = lista[min_idx], lista[i]
    return lista

40. Algoritmos de Ordenación: Insertion Sort (US)

Enunciado: Implementa la Ordenación por Inserción (Insertion Sort), el algoritmo que simula cómo ordenaríamos una baraja de cartas en la mano.

def insertion_sort(lista):
    for i in range(1, len(lista)):
        clave = lista[i]
        j = i - 1
        while j >= 0 and clave < lista[j]:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = clave
    return lista