Home Documentales Experimentos Música Trabajos Feed

miércoles, 6 de agosto de 2008

Algoritmo de Euclides con Hojas de cálculo

El algoritmo de Euclides
Este algoritmo sirve para encontrar el máximo común divisor (MCD) entre dos números a y b, con a>b. Para ello se repiten iterativamente los dos siguientes pasos:

1. Se realiza la división a/b, r será el resto de esta división.

2. Reemplazar a por b y b por r, siempre se va a cumplir que b>r

El MCD será el último resto no nulo.


Ejemplo: Calcula el MCD de 50 y 30


1. Divido 50 (a) entre 30 (b), sale de cociente 1 y de resto 20 (r)


2. Ahora divido 30 (divisor anterior) entre 20 (resto anterior) y nos sale de cociente 1 y de resto 10.


3. Se sigue igual: 20 (divisor anterior) entre 10 (resto anterior) y sale de cociente 2 y resto 0.


4. Como nos ha salido ya el resto cero me voy al último resto no nulo, lo miro, es 10.


MCD (50,30)=10





Algoritmo de Euclides con Hojas de cálculo
Al tratarse de un algoritmo se puede dar la orden a cualquier lenguaje de programación de que realice el paso tantas veces como sea necesario. El problema de una Hoja de Cálculo, como se ha dicho arriba, es que no permite este tipo de operaciones. Pero si se puede "programar" un número finito de operaciones que sea lo suficientemente grande. En el ejemplo que he colgado he repetido la operación 30 veces, es más que suficiente para calcular el MCD de bastantes parejas de números. La hoja de cálculo que he colgado tiene un calculador y un generador (como las herramientas del Proyecto Pascal-GCE). En el calculador se puden introducir las parejas de números que uno desee y en el generador se generan automáticamente parejas de números. En ambos casos se calcula el MCD de manera instantánea (siempre que sean menos de 31 iteraciones las necesarias).
No te vendría mal realizar algún MCD mentalmente, para no llegar en septiembre con la mente oxidada.


Nota: He encontrado una aplicación java muy interesante que aplica el algoritmo de Euclides.

--------------------------------------------------------------
Este post se puede complementar algo leyendo El algoritmo de Euclides con Hojas de cálculo, en Ciencia en el XXI.

6 comentarios:

Davidmh dijo...

Para este tipo de cosas Python es muy util. Entre otras cosas, permite manejar con sencillez todos los posibles casos (ya se sabe, cuando se requiere algo del usuario, esta potencialmente mal, y de cualquiera de las maneras posibles).

A ver si cuando vuelva a casa me acuerdo y lo escribo.

Aunque, de todas formas, puedes emplear celdas auxiliares para estas cosas. Es decir, que si los dos son numeros, los copias en las celdas "a" y "b"; si estan en el orden correcto, las vuelves a copiar a "c" y "d" y operas con ellas. Y si "c" o "d" estan vacias, pero la casilla del usuario no, puedes hacer aparecer un mensaje de error.

Eugenio Manuel Fernández Aguilar dijo...

No lo he utilizado nunca, a ver si nos enseñas algo. Te propongo que nos regales una entrada para colgarla. Una vez ya empezado el curso.

Como digo a los padres, el usar hojas de cálculo es porque todo el mundo (o casi todo el mundo) tiene una instalada.

Davidmh dijo...

¡Sus órdenes!

La versión 0.1 ya está lista. Estoy documentando todo el historial de versiones, por si a alguien le interesa.

Para ejecutarlo en Windows hay que instalar el intérprete (python.org ->downloads); en la mayoría de distros de Linux viene integrado.

Davidmh dijo...

Tras varias pruebas creo que puedo decir que la beta funciona bien. ¡Fuera la letra griega!

Eugenio Manuel dijo...

¿mande?, dónde está?

Davidmh dijo...

Si me das un correo te lo mando.