En esta sección iré presentando pequeños programas y algoritmos para automatizar tareas simples.

Programa para calcular el máximo común divisor de dos números.

(utiliza el algoritmo de Euclides simplificado mediante congruencias)

Descripción

Sean n1 y n2 los números para calcularles el mcd

Mediante la sentencia Input se pide al usuario que los introduzca en la Classpad

Establecemos un bucle que se va a repetir mientras n1≠n2 con While n1≠n2

Si n1>n2 entonces introducimos en n1 la diferencia n1-n2

y al contrario si n2>n1

El bucle termina cuando n1=n2

Al final con la orden PrintNatural sacamos en pantalla el resultado que será n1 (o bien n2)

Justificación matemática

Llamemos mcd al máximo común divisor de n1 y n2

n1= mcd . p (1)

n2= mcd . q (2)

Es decir n1 Ξ n2 (mod. mcd)

 Se lee n1 y n2 son congruentes módulo mcd y significa que

dan el mismo resto al dividirlos por mcd, en este caso 0.

----

 Hacemos (1) - (2)

n1 - n2= mcd (p-q)

Con lo cual la diferencia de n1 con n2 será también un múltiplo de mcd.

Ahora nos quedamos con esta diferencia y con el menor de los dos números iniciales n1 y n2

(asignamos de nuevo esa diferencia al mayor de n1 y n2)

Así vamos obteniendo dos números n1 y n2 que son múltiplos de mcd.

Continuamos el proceso hasta que ambos números sean iguales

que será el caso en que ambos sean igual al mcd multiplicado por 1,

con lo cual cualquiera de ellos es igual al mcd de ambos.

(es lógico, puesto que el mcd de un nº es él mismo)

Si queremos hallar el mcd de varios números, por ejemplo n1,n2 y n3

hacemos primero el mcd de n1 y n2

y luego el de n3 con el resultado anterior.

Programa para calcular el mínimo común múltiplo de dos números.

(es una modificación del anterior en el que se aplica la relación

entre el mcd y el mcm con el producto de dos números)

Sean a y b dos números,

su mcm (a,b) = a . b / mcd (a,b)

La función pisa(n) para obtener cualquier nº de Fibonacci