Herramientas Informaticas

Categoría: Tecnicas para programar mejor Página 4 de 5

B.2. Suma de fracciones Python

La suma es mas complicada que la multiplicación, pero aun es llevadera. La suma de a=b y c=d es la fracción (a*d+c*b)/b*d.
Usando como modelo el código de la multiplicación, podemos escribir __add__ y __radd__:

class Fracción:
...
    def __add__(self, otro):
        if type(otro) == type(5):
        otro = Fracción(otro)
    return Fracción(self.numerador * otro.denominador +
    self.denominador * otro.numerador,
    self.denominador * otro.denominador)
    __radd__ = __add__

Podemos probar estos métodos con Fracciones y enteros.

>;>> print Fracción(5,6) + Fracción(5,6)
60/36
>;>> print Fracción(5,6) + 3
23/6
>;>> print 2 + Fracción(5,6)
17/6

Los dos primeros ejemplos llaman a __add__ ; el ultimo llama a __radd__ .

B.3. Algoritmo de Euclides Python

En el ejemplo anterior, computamos la suma de 5=6 + 5=6 y obtuvimos 60=36.
Es correcto, pero no es la mejor forma de representar la respuesta. Para reducir la fracción a su expresión mas simple, hemos de dividir el numerador y el denominador por el máximo común divisor (MCD) de ambos, que es 12.
El resultado sería 5=3.
En general, siempre que creamos un nuevo objeto Fracción, deber³amos reducirlo dividiendo el numerador y el denominador por el MCD de ambos. Si la fracción ya esta reducida, el MCD es 1.
Euclides de Alejandr³a (aprox. 325{265 a. C.) presento un algoritmo para encontrar el MCD de dos números enfermos m y n:
Si n divide a m sin resto, entonces n es el MCD. De lo contrario, el MCD es el MCD de n y el resto de dividir m entre n. Esta definición recursiva puede expresarse concisamente como una función:
   1: def mcd (m, n):
   2:     if m % n == 0:
   3:         return n
   4:     else:
   5:         return mcd(n, m%n)

En la primera l³nea del cuerpo, usamos el operador de modulo para comprobar la divisibilidad. En la ultima l³nea, lo usamos para calcular el resto de la división.

Dado que todas las operaciones que hemos escrito creaban un nuevo objeto Fracción para devolver el resultado, podemos reducir todos los resultados modificando el método de inicialización.

   1: class Fracción:
   2:     def __init__(self, numerador, denominador=1):
   3:         m = mcd (numerador, denominador)
   4:         self.numerador = numerador / m
   5:         self.denominador = denominador / m

Ahora siempre que creemos una Fracción quedara reducida a su forma canoníca:

>;>> Fracción(100,-36)
-25/9

Una característica estupenda de mcd es que si la fracción es negativa, el signo menos siempre se trasladara al numerador.

B.4. Comparar fracciones Python

Supongamos que tenemos dos objetos Fracción, a y b, y evaluamos a == b. La implementación por defecto de == comprueba la igualdad super¯cial, por lo que solo devuelve true si a y b son el mismo objeto.
Queremos mas bien devolver verdadero si a y b tienen el mismo valor |eso es,igualdad en profundidad.
Hemos de enseñar a las fracciones como compararse entre si. Como vimos en la Sección 15.4, podemos sobrecargar todos los operadores de comparación de una vez proporcionando un método cmp .
Por convenio, el método cmp devuelve un numero negativo si self es menor que otro, zero si son lo mismo, y un numero positivo si self es mayor que otro.
La forma mas simple de comparar dos fracciones es la multiplicación cruzada.
Si a=b > c=d, entonces ad > bc. Con esto en mente, aquí esta el código para cmp :
   1: class Fraccion:
   2: ...
   3:     def __cmp__(self, otro):
   4:         dif = (self.numerador * otro.denominador -
   5:             otro.numerador * self.denominador)
   6:         return dif

Si self es mayor que otro, entonces dif sera positivo. Si otro es mayor, entonces dif sera negativo. Si son iguales, dif es cero.

B.5. Forzando la máquina

Por supuesto, aun no hemos terminado. Todavía hemos de implementar la resta sobrecargando sub y la división sobrecargando div .
Una manera de manejar estas operaciones es implementar la negación sobrecargando negó y la inversión sobrecargando invert . Entonces podemos restar negando el segundo operando y sumando, y podemos dividir invirtiendo el segundo operando y multiplicando.
Luego, hemos de suministrar los métodos rsub y rdiv . Desgraciadamente, no podemos usar el mismo truco que usamos para la suma y la multiplicación, porque la resta y la división no son conmutativas. No podemos igualar rsub
y rdiv a sub y div . En estas operaciones, el orden de los operandos tiene importancia.
Para manejar la negación unitaria, que es el uso del signo menos con un único operando, sobrecargamos el método neg .
Podemos computar potencias sobrecargando pow , pero la implementación tiene truco. Si el exponente no es un numero entero podría no ser posible representar el resultado como una Fracción. Por ejemplo, Fracción(2) ** Fracción(1,2) es la raíz cuadrada de 2, que es un numero irracional (no se puede representar como una fracción). Por lo tanto, no es fácil escribir la versión mas general de pow .
Existe otra extensión a la clase Fracción que cabr³a considerar. Hasta ahora, hemos asumido que el numerador y el denominador son enteros. Podríamos considerar la posibilidad de perimirles que sean enteros largos.
Como ejercicio, termine la implementación de la clase Fracción de forma que pueda manejar resta, división, exponenciación y enteros largos como numerador y denominador.

B.6. Glosario

Máximo común divisor (MCD): El mayor entero positivo que divide al numerador y al denominador de una fracción sin que quede un resto.
Reducir: Cambiar la fracción a su forma equivalente con un MCD igual a 1.
Negación unitaria: Operación que computa el elemento simétrico aditivo, normalmente denotada con un signo menos delante. Se denomina unitaria” en contraste con la operación binaria menos, que es la resta.

C.1. Clase Punto Python

   1: class Punto:
   2:     def __init__(self, x=0, y=0):
   3:         self.x = x
   4:         self.y = y
   5:         def __str__(self):
   6:         return '(' + str(self.x) + ', ' + str(self.y) + ')'
   7:     def __add__(self, otro):
   8:         return Punto(self.x + otro.x, self.y + otro.y)
   9:     def __sub__(self, otro):
  10:         return Punto(self.x - otro.x, self.y - otro.y)
  11:     def __mul__(self, otro):
  12:         return self.x * otro.x + self.y * otro.y
  13:     def __rmul__(self, otro):
  14:         return Punto(otro * self.x, otro * self.y)
  15:     def reverse(self):
  16:         self.x, self.y = self.y, self.x
  17:     def delDerechoYDelReves(derecho):
  18:         from copy import copy
  19:         reves = copy(derecho)
  20:         reves.reverse()
  21:         print str(derecho) + str(reves)

DESCARGAR CODIGO FUENTE

C.2. Clase Hora Python

   1: class Hora:
   2:     def __init__(self, horas=0, minutos=0, segundos=0):
   3:         self.horas = horas
   4:         self.minutos = minutos
   5:         self.segundos = segundos
   6:     def __str__(self):
   7:         return str(self.horas) + ":" + str(self.minutos) 
   8:         + ":" + str(self.segundos)
   9:     def convierteASegundos(self):
  10:         minutos = self.horas * 60 + self.minutos
  11:         segundos = self.minutos * 60 + self.segundos
  12:         return segundos
  13:     def incrementa(self, segs):
  14:         segs = segs + self.segundos
  15:         self.horas = self.horas + segs/3600
  16:         segs = segs % 3600
  17:         self.minutos = self.minutos + segs/60
  18:         segs = segs % 60
  19:         self.segundos = segs
  20:     def haceHora(segs):
  21:         hora = Hora()
  22:         hora.horas = segs/3600
  23:         segs = segs - hora.horas * 3600
  24:         hora.minutos = segs/60
  25:         segs = segs - hora.minutos * 60
  26:         hora.segundos = segs
  27:         return hora

DESCARGAR CODIGO FUENTE

C.3. Cartas, mazos y juegos Python

   1: import random
   2: class Carta:
   3:     listaDePalos = ["Tr¶eboles", "Diamantes", "Corazones",
   4:     "Picas"]
   5:     listaDeValores = ["nada", "As", "2", "3", "4", "5", "6", "7",
   6:     "8", "9", "10", "Sota", "Reina", "Rey"]
   7:     
   8:     def __init__(self, palo=0, valor=0):
   9:         self.palo = palo
  10:         self.valor = valor
  11:     def __str__(self):
  12:         return (self.listaDeValores[self.valor] + " de " +
  13:         self.listaDePalos[self.palo])
  14:     def __cmp__(self, otro):
  15:         # controlar el palo
  16:         if self.palo > otro.palo: return 1
  17:         if self.palo < otro.palo: return -1
  18:         # si son del mismo palo, controlar el valor
  19:         if self.valor > otro.valor: return 1
  20:         if self.valor < otro.valor: return -1
  21:         # los valores son iguales, es un empate
  22:         return 0
  23:  
  24: class Mazo:
  25:     def __init__(self):
  26:         self.cartas = []
  27:         for palo in range(4):
  28:             for valor in range(1, 14):
  29:                 self.cartas.append(Carta(palo, valor))
  30:  
  31:     def muestraMazo(self):
  32:         for carta in self.cartas:
  33:             print carta
  34:     def __str__(self):
  35:         s = ""
  36:         for i in range(len(self.cartas)):
  37:             s = s + " "*i + str(self.cartas[i]) + "n"
  38:             return s
  39:     def mezclar(self):
  40:         import random
  41:         nCartas = len(self.cartas)
  42:         for i in range(nCartas):
  43:         j = random.randrange(i, nCartas)
  44:         self.cartas[i], self.cartas[j] =
  45:         self.cartas[j], self.cartas[i]
  46:     def eliminaCarta(self, carta):
  47:         if carta in self.cartas:
  48:             self.cartas.remove(carta)
  49:             return 1
  50:         else: return 0
  51:     def darCarta(self):
  52:         return self.cartas.pop()
  53:     def estaVacio(self):
  54:         return (len(self.cartas) == 0)
  55:     def repartir(self, manos, nCartas=999):
  56:         nManos = len(manos)
  57:         for i in range(nCartas):
  58:         if self.estaVacio(): break # fin si se acaban las cartas
  59:             carta = self.darCarta() # da la carta superior
  60:             mano = manos[i % nManos] # a qui¶en le toca?
  61:             mano.agregaCarta(carta) # agrega la carta a la mano
  62:  
  63: class Mano(Mazo):
  64:     def __init__(self, nombre=""):
  65:         self.cartas = []
  66:         self.nombre = nombre
  67:     def agregaCarta(self,carta) :
  68:         self.cartas.append(carta)
  69:     def __str__(self):
  70:         s = "La mano de " + self.nombre
  71:         if self.estaVacio():
  72:             s = s + " est¶a vac¶³an"
  73:         else:
  74:             s = s + " contienen"
  75:     return s + Mazo.__str__(self)
  76:  
  77: class JuegoDeCartas:
  78:     def __init__(self):
  79:         self.mazo = Mazo()
  80:         self.mazo.mezclar()
  81:  
  82: class ManoDeLaMona(Mano):
  83:     def eliminaCoincidencias(self):
  84:         cant = 0
  85:         cartasOriginales = self.cartas[:]
  86:         for carta in cartasOriginales:
  87:             empareja = Carta(3 - carta.palo, carta.valor)
  88:             if empareja in self.cartas:
  89:             self.cartas.remove(carta)
  90:             self.cartas.remove(empareja)
  91:             print "Mano %s: %s con %s" % (self.nombre,carta,empareja)
  92:             cant = cant + 1
  93:             return cant
  94:  
  95: class JuegoDeLaMona(JuegoDeCartas):
  96:     def jugar(self, nombres):
  97:     # quitamos la Reina de Tr¶eboles
  98:     self.mazo.eliminaCarta(Carta(0,12))
  99:         # construimos una mano para cada jugador
 100:     self.manos = []
 101:     for nombre in nombres :
 102:         self.manos.append(ManoDeLaMona(nombre))
 103:         # repartimos los naipes
 104:         self.mazo.repartir(self.manos)
 105:         print "----- Se han repartido las cartas."
 106:         self.muestraManos()
 107:         # eliminamos las coincidencias iniciales
 108:         emparejadas = self.eliminaTodasLasCoincidencias()
 109:         print "----- Coincidencias eliminadas, el juego comienza."
 110:         self.muestraManos()
 111:         # se juega hasta que se han descartado las 50 cartas
 112:         turno = 0
 113:         cantManos = len(self.manos)
 114:         while emparejadas < 25:
 115:         emparejadas = emparejadas + self.jugarUnTurno(turno)
 116:             turno = (turno + 1) % cantManos
 117:             print "----- El juego termin¶o."
 118:             self.muestraManos()
 119:     def eliminaTodasLasCoincidencias(self):
 120:     cant = 0
 121:     for mano in self.manos:
 122:         cant = cant + mano.eliminaCoincidencias()
 123:         return cant
 124:     def jugarUnTurno(self, i):
 125:     if self.manos[i].estaVacio():
 126:         return 0
 127:         vecino = self.encuentraVecino(i)
 128:     cartaElegida = self.manos[vecino].darCarta()
 129:     self.manos[i].agregaCarta(cartaElegida)
 130:     print "Mano", self.manos[i].nombre, "eligi¶o", cartaElegida
 131:     cant = self.manos[i].eliminaCoincidencias()
 132:     self.manos[i].mezclar()
 133:     return cant
 134:  
 135:     def encuentraVecino(self, i):
 136:     cantManos = len(self.manos)
 137:     for proximo in range(1,cantManos):
 138:         vecino = (i + proximo) % cantManos
 139:         if not self.manos[vecino].estaVacio():
 140:             return vecino
 141:     def muestraManos(self) :
 142:     for mano in self.manos :
 143:         print mano

DESCARGAR CODIGO FUENTE

C.4. Listas Enlazadas Python

   1: def imprimeLista(nodo):
   2:     while nodo:
   3:         print nodo,
   4:         nodo = nodo.siguiente
   5:         print
   6: def imprimeAlReves(lista):
   7:     if lista == None: return
   8:     cabeza = lista
   9:     cola = lista.siguiente
  10:     imprimeAlReves(cola)
  11:     print cabeza,
  12: def imprimeAlRevesBonito(lista) :
  13:     print "[",
  14:     if lista != None :
  15:         cabeza = lista
  16:         cola = lista.siguiente
  17:  
  18: imprimeAlReves(cola)
  19: print cabeza,
  20: print "]",
  21:  
  22: def eliminaSegundo(lista):
  23:     if lista == None: return
  24:         primero = lista
  25:         segundo = lista.siguiente
  26:         primero.siguiente = segundo.siguiente
  27:         segundo.siguiente = None
  28:         return segundo
  29:  
  30: class Nodo:
  31:     def __init__(self, carga=None, siguiente=None):
  32:         self.carga = carga
  33:         self.siguiente = siguiente
  34:  
  35:     def __str__(self):
  36:         return str(self.carga)
  37:  
  38:     def imprimeAlReves(self):
  39:         if self.siguiente != None:
  40:             cola = self.siguiente
  41:             cola.imprimeAlReves()
  42:             print self.carga,
  43:  
  44: class ListaEnlazada :
  45:     def __init__(self) :
  46:         self.longitud = 0
  47:         self.cabeza = None
  48:     def imprimeAlReves(self):
  49:         print "[",
  50:         if self.cabeza != None:
  51:         self.cabeza.imprimeAlReves()
  52:         print "]",
  53:     def agregaPrimero(self, carga):
  54:         nodo = Nodo(carga)
  55:         nodo.siguiente = self.cabeza
  56:         self.cabeza = nodo
  57:         self.longitud = self.longitud + 1 

C.5. Clase Pila Python

   1: class Pila : # implem. con listas de Python
   2:     def __init__(self) :
   3:         self.elementos = []
   4:     def push(self, elemento) :
   5:         self.elementos.append(elemento)
   6:     def pop(self) :
   7:         return self.elementos.pop()
   8:     def isEmpty(self) :
   9:         return (self.elementos == [])
  10:     def evalPostfijo(expr):
  11:         import re
  12:         listaTokens = re.split("([^0-9])", expr)
  13:         pila = Pila()
  14:         for token in listaTokens:
  15:         if token == '' or token == ' ':
  16:             continue
  17:         if token == '+':
  18:             suma = pila.pop() + pila.pop()
  19:             pila.push(suma)
  20:             elif token == '*':
  21:             producto = pila.pop() * pila.pop()
  22:             pila.push(producto)
  23:         else:
  24:             pila.push(int(token))
  25:         return pila.pop()

Página 4 de 5

Creado con WordPress & Tema de Anders Norén