Implementación de Algoritmos Fundamentales en Python: Hanoi, Fibonacci y Métodos de Ordenamiento

Algoritmos Recursivos Clásicos

Torres de Hanoi

Implementación recursiva para resolver el problema clásico de las Torres de Hanoi.

def hanoi(n, inicial, final, libre):
    if n == 1:
        print('mover disco superior de aguja', inicial, 'a', final)
    else:
        hanoi(n - 1, inicial, libre, final)
        print('mover disco superior de aguja', inicial, 'a', final)
        hanoi(n - 1, libre, final, inicial)

Complejidad Temporal

El número de movimientos requeridos es (2ⁿ) - 1 iteraciones.

Sucesión de Fibonacci

Diferentes métodos para calcular el n-ésimo término de la secuencia de Fibonacci.

Implementación Recursiva (fiboR)

def fiboR(n):
    if n == 1 or n == 2:
        return 1
    return fiboR(n - 1) + fiboR(n - 2)

Implementación Iterativa (fiboI)

def fiboI(n):
    a, b = 1, 1
    for i in range(3, n + 1):
        a, b = b, a + b
    return b

Implementación por Fórmula de Binet (fiboFormula)

def fiboFormula(n):
    from math import sqrt
    z = 1 / sqrt(5) * (((1 + sqrt(5)) / 2) ** n - ((1 - sqrt(5)) / 2) ** n)
    return int(z)

Estructuras de Datos y Lógica Binaria

Rastreo de Ascendencia Binaria

Este segmento de código utiliza la representación binaria de un número para simular un rastreo de ascendencia (Padre/Madre).

a = int(input('Numero de apellido:'))
lista = list(bin(a - 1)[2:])

for dato in lista:
    if dato == '0':
        print('PADRE', end=' ')
    else:
        print('MADRE', end=' ')

Algoritmos de Ordenamiento (Sorting)

Ordenamiento por Burbuja (Bubble Sort)

def ordenar_bur(l):
    for P in range(len(l) - 1):
        for i in range(len(l) - 1 - P):
            if(l[i] > l[i + 1]):
                aux = l[i]
                l[i] = l[i + 1]
                l[i + 1] = aux
    return l

Ordenamiento por Inserción (Insertion Sort)

def ord_insertando(l):
    for j in range(1, len(l)):
        i = j - 1
        temp = l[j]
        while(i > -1 and l[i] > temp):
            l[i + 1] = l[i]
            i = i - 1
        l[i + 1] = temp
    return l

Ordenamiento por Mezcla (Merge Sort)

Función de Mezcla (Merging)

def mezclando(izq, der):
    lord = []
    i = 0
    j = 0
    while i < len(izq) and j < len(der):
        if izq[i] < der[j]:
            lord.append(izq[i])
            i = i + 1
        else:
            lord.append(der[j])
            j = j + 1
    lord = lord + izq[i:]
    lord = lord + der[j:]
    return lord

Función Principal de Merge Sort (Recursiva)

def ord_mezclando(l):
    if len(l) < 2:
        return l
    else:
        mitad = len(l) // 2
        izq = ord_mezclando(l[:mitad])
        der = ord_mezclando(l[mitad:])
        return mezclando(izq, der)

Generación de Combinaciones

Permutaciones de Paréntesis

Generación de secuencias de paréntesis (aunque la implementación puede no garantizar todas las combinaciones balanceadas).

def perm(n):
    a = ['()']
    for i in range(n - 1):
        b = a[:]
        a = []
        for x in b:
            a.append('(' + x + ')')
            a.append('()' + x)
    return a

Procesamiento de Datos y Utilidades de Fecha

Cálculo de Edad a partir de Fechas

Función que calcula la edad de una persona dada su fecha de nacimiento (cadena_cumple) y la fecha actual (asumida como variable global FECHA).

def edad(cadena_cumple):
    lc1 = cadena_cumple.split('-')
    lc2 = FECHA.split('-')
    a1 = int(lc1[2])
    a2 = int(lc2[2])
    m1 = int(lc1[1])
    m2 = int(lc2[1])
    d1 = int(lc1[0])
    d2 = int(lc2[0])
    
    # Comprueba si ya ha cumplido años este año
    if(m1 < m2 or (m1 == m2 and d1 <= d2)):
        return a2 - a1
    else:
        return a2 - a1 - 1

Ejemplo de Procesamiento de Archivo de Datos

El siguiente código lee datos estructurados de skype_datos.txt (asumiendo un formato de etiqueta/valor alternado) y calcula la edad de los registros, escribiendo los resultados en solucion_ej_4.txt.

i = 1
l = []
l2 = ['', '', '']
f = open('skype_datos.txt', 'r')

for linea in f:
    if i % 2 != 0:
        etiq = linea.strip()
    else:
        if etiq == 'USUARIO':
            l2[0] = linea.strip()
        elif etiq == 'LUGAR':
            l2[1] = linea.strip()
        else: # Asumiendo que es el campo de fecha de nacimiento
            l2[2] = linea.strip()
    
    if i % 6 == 0:
        l.append(l2)
        l2 = ['', '', '']
    i += 1
f.close()
print(l)

FECHA = input('dame fecha de hoy DD-MM-AAAA')

f2 = open('solucion_ej_4.txt', 'w')
for subl in l:
    n = edad(subl[2])
    f2.write(str(n) + '\n')
f2.close()