La importancia de los algoritmos (Parte 2)

En esta segunda parte de los algoritmos matemáticos te contaré por qué son importantes, si quieres conocer su origen y funciones te invito a visitar mi artículo anterior.

Geometría

Algunas veces encontramos problemas en los cuales necesitamos encontrar la intersección entre rectángulos. Existen diferentes maneras de representar un rectángulo. Para el plano cartesiano estándar, método común es almacenar las coordenadas de la esquina inferior izquierda y la esquina superior derecha.

Supongamos que tenemos dos rectángulos R1 y R2. La coordenada (x1, y1) es la ubicación de la esquina inferior izquierda de R1 y (x2, y2) su esquina superior derecha. Similarmente, (x3, y3) y (x4, y4) las respectivas esquinas para R2. La intersección entre R1 y R2 será un rectángulo R3, cuya esquina inferior izquierda es ( max(x1, x3), max(y1, y3)) y esquina superior derecha en (min(x2, x4), min(y2, y4)). Si max(x1, x3) > min(x2, x4) ó max(y1, y3) > min(y2, y4) entonces R3 no existe, por lo tanto R1 y R2 no se intersectan.

A menudo tenemos que trabajar con polígonos cuyos vértices tienen coordenadas enteras. Existe un metodo elegante mediante el cual podemos calcular el area de un poligono cuyos vertices conocidos sean de coordenadas enteras.

Supongamos que no conocemos la posición exacta de los vertices, sin embargo si conocemos dos valores:

• B = el número de puntos con coordenadas enteras que coinciden con el limite del poligono
• I = el número de puntos con coordenadas enteras que se están en el interior del area del polígono

Sorprendentemente, el area de este poligono está dado por:

La formula anterior representa el Teorema de Pick, desarrollado por Georg Alexander Pick (1859 – 1943). El Teorema de Pick es útil cuando necesitamos encontrar el numero de puntos con coordenadas enteras dentro de un polígono grande.

Otra formula que vale la pena recordar es la Formula de Euler para redes poligonales. Una red poligonal es un simple poligono dividido en poligonos mas pequeños. Estos poligonos mas pequeños son llamados caras, los lados de las caras son llamados aristas y los vertices de las caras son llamados de igual manera vertices. La Formula de Euler afirma:

Por ejemplo, consideremos un cuadrado con su dos diagonales dibujadas. Tenemos V=5, E=8 y F=5 (el exterior del cuadrado es también una cara) entonces tenemos V-E+F=2.

Bases numéricas

Un problema muy común que se presenta en concursos de programación es la conversión entre las representaciones binarias y decimales (entre otras) de números.

A continuación tenemos el código para la conversión de un número n base b (2<=b<=10) a número decimal:

Algunos estarán contentos de saber que en Java solo tienen que escribir:

Para convertir un número de decimal a binario es sencillo. Supongamos que queremos convertir el número 43 decimal a binario. En cada paso dividimos 43 entre 2 y recordamos el residuo. La lista final de residuos es la representación binaria que buscamos:

Entonces el número 43 decimal es 101011 en binario. Cambiando todas la ocurrencias de de con b en nuestro código anterior creamos una función que convierte un número decimal n a un número base b (2<=b<=10)

Si la base b es mayor que 10 entonces debemos usar caracteres no númericos para representar los digitos que tengan valor de 10 o mas. Usaremos la letra ‘A’ para representar el 10, ‘B’ para representar el 11 y demás. El siguiente código sirve para convertir un número decimal a cualquier base (hasta base 20):

En Java existen formas de hacer esto en una sola linea de código para pasar de decimal a otras comunes representaciones, como binario (base 2), octal (base 8), hexadecimal (base 16):

Fracciones

En diversos problemas podemos encontrar números fraccionarios. Posiblemente el aspecto mas dificil por el cual lidiar con las fracciones es encontrar la manera correcta de representarlos. También es posible crear una clase fraccion que contenga los atributos y metodos requeridos, por ahora es suficiente representar las fracciones como un arreglo de 2 elementos. La idea es tener guardado el numerado en el primer elemento y el denominador en el segundo elemento. Comenzaremos con la multiplicación de dos fracciones:

Sumar fracciones es un poco mas complicado, aunque fracciones con el mismo denominador son las mas sencillas. Primero que cualquier cosa, debemos encontrar el común denomiador de las dos fracciones y luego multiplicar para transformar las fracciones para que ambas tengas el común denominador. El común denominador es una número que puede dividir a ambos denomidores y es simplemente el mínimo común múltiplo (mcm) de los dos denominadores. Por ejemplo, hagamos la suma de 4/9 con 1/6. El mcm de 9 y 6 es 18. Entonces para transformar la primer fracción necesitamos multiplicarla por 2/2 y multiplicar el segundo por 3/3:

Una vez que las dos fraccciones tienen el mismo denominador, simplemente sumamos los numeradores para obtener el resultado final. La resta de fracciones es muy similar, solo que ahora se resta en el último paso:

Aquí el código de la suma de dos fracciones:

Finalmente, es muy útil saber como reducir una fracción a su simple forma. La forma más simple de una fracción es cuando el máximo común divisor (MCD) del numerador y el denominador es igual a 1. Hacemos:

Números Complejos

Similarmente, podemos representar otros números especiales, como los números complejos. En general, un número complejo es un número de la forma a + ib, donde a y b son números reales y i es la raiz cuadrada de -1. Por ejemplo, para sumar dos números complejos m = a + ib y n = c + id simplemente agrupamos los terminos:

Multiplicar dor números complejos es igual a multiplicar dos números reales, excepto que sabemos que i^2 = -1:

Guardando la parte real en el primer elemento y la parte compleja del segundo elemento de un arreglo escribimos el código que realiza la multiplicación.

Por Raúl Alberto Soto Cruz

Referencias:

TopCoder Tutorial Algorithms “Mathematics for TopCoders”
Algoritmos Matemáticos