ejemplo de algoritmo (Suma de dos números)
Algoritmo para calcular la suma de dos números enteros
un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema y se representan por diagramas de flujo. Un ejemplo clasico de un Algoritmo es una receta de cocina, te dice que tienes que hacer detalladamente y paso por paso. Este problema es de lógica, mi algoritmo es:
1: Inicio
2: declarar variables(x, y, z)
3: darle valor a las variables(x= 2, y=3)
4: sumar variables(x+y=z, z= 2+3)
5: Imprimir resultado(z=5)
6: Fin
Este algoritmo está mas orientado hacia la Programación.
1: Inicio
2: declarar variables(x, y, z)
3: darle valor a las variables(x= 2, y=3)
4: sumar variables(x+y=z, z= 2+3)
5: Imprimir resultado(z=5)
6: Fin
Este algoritmo está mas orientado hacia la Programación.
Algoritmo para calcular el máximo común divisor
dados dos números, obtener el máximo número que divida a ambos.
Para ello, lo primero que había que hacer era descomponer cada número en factores primos. Por ejemplo, para calcular el mcd (máximo común divisor) de 756 y 1617:
756 = 7 * 3^3 * 2^2
1617 = 11 * 7^2 * 3
A continuación tomamos los factores comunes elevemos al menos exponente y ese es el mcd; en nuestro ejemplo:
mcd(756,1617) = 7 * 3 = 21
Hacer esto es relativamente sencillo, ahora bien, programarlo ya es otra cosa bien distinta. Lo más complicado sería implementar una función que descomponga un número en sus factores primos.
Se podría hacer, si bien existe un método bastante más sencillo: utilizando el algoritmo de Euclides. ¿En qué consiste? De forma resumida, el pseudocódigo para la función que calcula el mcd quedaría:
function mcd(a, b) {
if (a > b) {
return mcd(a-b, b);
} else if (b > a) {
return mcd(a, b-a);
} else { // a == b
return a;
}
}
Aplicándolo a nuestro ejemplo:
mcd(756,1617) = mcd(756,861) = mcd(756,105) = mcd(651,105) = mcd(546,105) = mcd(441,105) = mcd(336,105) = mcd(231,105) = mcd(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21
Por supuesto, este algoritmo es susceptible de ciertas mejoras. Por ejemplo, multiplicar y dividir por 2 es algo sencillo utilizando las operaciones de bits: al desplazar un bit a la izquierda estamos multiplicando por 2 y al desplazarlo a la derecha estamos dividiendo por 2. De esta forma, podríamos ahorrarnos algunos pasos en el ejemplo anterior:
function mcd_mejorado(x, y) {
var mayor = max(x,y);
var menor = min(x,y);
if (mayor > (menor << 1)) {
return mcd_mejorado(mayor - (menor << 1), menor);
} else {
return mcd(mayor,menor); //llamada a la funcion anterior
}
}
Volviendo a nuestro ejemplo:
mcd_mejorado(1617,756) = mcd_mejorado(756,105) = mcd_mejorado(546,105) = mcd_mejorado(336,105) = mcd_mejorado(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21
Para ello, lo primero que había que hacer era descomponer cada número en factores primos. Por ejemplo, para calcular el mcd (máximo común divisor) de 756 y 1617:
756 = 7 * 3^3 * 2^2
1617 = 11 * 7^2 * 3
A continuación tomamos los factores comunes elevemos al menos exponente y ese es el mcd; en nuestro ejemplo:
mcd(756,1617) = 7 * 3 = 21
Hacer esto es relativamente sencillo, ahora bien, programarlo ya es otra cosa bien distinta. Lo más complicado sería implementar una función que descomponga un número en sus factores primos.
Se podría hacer, si bien existe un método bastante más sencillo: utilizando el algoritmo de Euclides. ¿En qué consiste? De forma resumida, el pseudocódigo para la función que calcula el mcd quedaría:
function mcd(a, b) {
if (a > b) {
return mcd(a-b, b);
} else if (b > a) {
return mcd(a, b-a);
} else { // a == b
return a;
}
}
Aplicándolo a nuestro ejemplo:
mcd(756,1617) = mcd(756,861) = mcd(756,105) = mcd(651,105) = mcd(546,105) = mcd(441,105) = mcd(336,105) = mcd(231,105) = mcd(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21
Por supuesto, este algoritmo es susceptible de ciertas mejoras. Por ejemplo, multiplicar y dividir por 2 es algo sencillo utilizando las operaciones de bits: al desplazar un bit a la izquierda estamos multiplicando por 2 y al desplazarlo a la derecha estamos dividiendo por 2. De esta forma, podríamos ahorrarnos algunos pasos en el ejemplo anterior:
function mcd_mejorado(x, y) {
var mayor = max(x,y);
var menor = min(x,y);
if (mayor > (menor << 1)) {
return mcd_mejorado(mayor - (menor << 1), menor);
} else {
return mcd(mayor,menor); //llamada a la funcion anterior
}
}
Volviendo a nuestro ejemplo:
mcd_mejorado(1617,756) = mcd_mejorado(756,105) = mcd_mejorado(546,105) = mcd_mejorado(336,105) = mcd_mejorado(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21
Algoritmo para calcular números primos
Por qué cambiar de algoritmo para calcular los números primos? Pues porque el que hay ahora 2 E NP -1 (2 elevado a un numero primo, al resultado se le resta 1) el resultado que da no se sabe si es primo y hay que comprobarlo, con mi algoritmo no hay que preocuparse de si es o no primo porque (al menos teoricamente) ya he probado que siempre da números primos.
La lista tendrá este formato:
No hay comentarios:
Publicar un comentario