|Portada|Blog|Space|
[Índice] > Calculadora para celulares - 2da parte
Como sabrán yo soy un aficionado al midp-calc, una calculadora hecha en
java para celulares medianamente modestos (funciona por ejemplo en mi
j300).
Y como necesitaba calcular el máximo común divisor entre un par de
números al no encontrar una función para tal tarea me implementé un mini
programa en esta calculadora que halla justamente eso.
Para ingresar esta funcionalidad en un midp-calc hay que ir por el menú
a: mode->prog->new y seleccionar algún casillero vacío, están vacíos los
que dicen < >, se deberá después escribir el nombre que nos permitirá
recordar la función, llamarle mcd o gcd pueden ser dos formas prácticas.
El programa que a continuación voy a listar se ingresa usando
normalmente las funciones como si se estuviera calculando a mano.
1: prog/flow/x>y?
2: stack/x<->y
3: prog/flow/LBL 0
4: ENTER
5: stack/rolldn
6: math/mod
7: prog/flow/x=0?
8: prog/flow/GTO 1
9: stack/rollup
10: stack/x<->y
11: prog/flow/GTO 0
12: prog/flow/LBL 1
13: clear
14: stack/rollup
15: [prg end]
En esta función el cálculo del máximo común divisor se realiza por medio
del algoritmo de euclides. Recomiendo conocer el algoritmo
detalladamente antes de leer la explicación del código.
Es importante recordar que el midp-calc es una calculadora RPN y por
tanto se trabaja siempre sobre una pila. Los elementos se agregan en la
pila del lado de abajo y van subiendo a medida que se agregan,
análogamente bajan cuando son consumidos.
Los 4 elementos del fondo de la pila (o sea, los últimos en entrar, los
primeros en salir) reciben el nombre de x, y, z, t. El de más abajo es
siempre x.
Regresando a la descripción de la función, las líneas 1 y 2 garantizan
que x sea menor o igual a y. Traduciendo a pseudocódigo las dos primeras
líneas quedaría algo así como:
1: Si x>y entonces ejecutar 2, sino saltear 2 y obviamente seguir con 3.
2: Intercambiar los valores de x e y.
de esta forma, si en la pila de nuestra calculadora tenemos algo así
como:
....
y= 24
x= 50
estas dos líneas se encargarán de dejar la pila así:
....
y= 50
x= 24
De esta forma podemos aplicar sistemáticamente el algoritmo de Euclides.
En la línea 3 nos definimos una etiqueta. Las etiquetas facilitan la
construcción de iteraciones, en este caso se define la etiqueta Nº0 que
se usará para indicar donde comienza la parte repetitiva del algoritmo.
Desde el punto de vista, muy lejano por cierto, de la programación
estructurada esta construcción es similar a la del do{ ... }while();
En la línea 4 ingresamos la orden ENTER, que como se podrá apreciar con
un poco de práctica en la calculadora se encarga de copiar el valor de x
y volver a insertarlo, de esta forma si nuestra pila tenía:
....
y= 50
x= 24
pasará a tener:
....
z= 50
y= 24
x= 24
Esto junto a la línea 5, con la orden stack/rolldn, nos permite sacar de
la pila a un elemento y colocarlo en la parte superior de la misma. De
esta forma nuestras pilas pasarían por los siguientes estados:
.... = 24
.... => aplico => z= 50 => aplico => ....
y= 50 => 4: => y= 24 => 5: => y= 50
x= 24 x= 24 x= 24
El sentido que tiene dejar un elemento en la parte superior de la pila
es el de poder seguir realizando operaciones consumiendo a x e y sin
perder el valor de x, necesario para poder realizar el algoritmo de
euclides.
Sigue entonces el programa en la línea 6 aplicando la operación math/mod
que se encarga de consumir a x e y y dejar el resto de la división y/x.
Para hallar el máximo común divisor no importa el cociente.
Nuestra pila seguiría así:
= 24
....
x= 2
Recordar que 50 = 2*24 + 2.
Ahora bien, si el resto fuera 0 sabríamos que el algoritmo de Euclides
habría terminado, por eso es que en la línea 7 nos fijamos si x=0 y en
caso efectivo se aplica la línea 8 que sería ni más ni menos que un
salto a la parte del programa que se encarga de ordenar un poco las
cosas antes de terminar.
En caso de que x sea distinto de 0 se debería seguir el algoritmo de
euclides, y procedería a ejecutarse las líneas 9 y 10 que acomodan la
pila para que pueda volver a ejecutarse el procedimiento.
Así se vería la pila antes y después de las líneas 9 y 10 en nuestro
ejemplo:
= 24 .... ....
.... => aplico => y= 2 => aplico => y= 24
x= 2 => 9: => x= 24 => 10: => x= 2
Es en la línea 11 que se hace un salto a la línea 3 en donde se definió
la etiqueta 0. De esta forma se logra el bucle. Nótese que el bucle no
es infinito porque es justamente en la línea 8 que se hace un salto a la
línea 12 si x fuera 0.
En la línea 12 se define la etiqueta Nº1. Se llega a este lugar
solamente desde la instrucción de la línea 8 que es un GOTO a la
etiqueta 1.
En las líneas 13 se acomoda un poco la cosa borrando el resto de la
división (que es siempre 0 y no nos interesa) y se obtiene como máximo
común divisor el número que había quedado en la parte de arriba de la
pila. Esto se debe a que mcd(r_n, 0) = r_n siendo r_n el penúltimo
resto, o sea, el resto anterior al que dio 0, el máximo común divisor.
¡Fin!
Como comentario final quiero solamente dejar una referencia al código
recién escrito para que cada uno de ustedes quede asombrado ante las
maravillosas posibilidades que nos permite esta gran calculadora.
Este programa para hallar el máximo común divisor lo dejo en dominio
público porque es muy básico como para gastarme en andar reclamando
los derechos de copia.
Para el que no estaba enterado, le aviso que midp-calc está licenciado
bajo la GPL :)
http://midp-calc.sourceforge.net/Calc.html
---------
Los documentos en este sitio se encuentran licenciados bajo la GFDL.
Ver comentarios: [Hay i comentarios]
Para agregar un comentario: agregue a la URL: ?do=show_comment_form (explicación)