domingo, 5 de julio de 2009

Descomponer un número en tres factores (2)

La búsqueda de todas las formas en que se puede descomponer un número entero positivo en tres factores la tratamos en la entrada anterior como propuesta de uso en el aula. Ahora presentamos un algoritmo de tipo “voraz” que se puede implementar en una hoja de cálculo.

Los algoritmos voraces buscan las soluciones localmente aunque para ello tengan que destruir algún dato previo del problema. En este caso, lo que se “destruye” es el número entero propuesto, aunque se procurará reconstruirlo de nuevo en cada paso. La idea es la siguiente:

(1) Elegimos sistemáticamente el primer factor: 2,3,4…y nos quedamos con el primero que sea divisor del número N propuesto. Una vez encontrado, dividimos N entre el mismo, y ese valor lo tomamos como base para buscar el segundo factor. Por ejemplo, para factorizar 450 encontramos como primera posibilidad el 2. Dividimos 450 entre 2 y nos queda 225.

(2) Para encontrar el segundo factor comenzamos con un valor igual al primero (para que los factores sean no decrecientes y así no existan duplicaciones). En el caso de 450 comenzaríamos con el 2, pero como no divide a 225, pasamos al 3, y nos queda 2*3. Dividimos 225 entre 3 y nos resultará 75, que automáticamente se convertirá en el tercer factor: 450=2*3*75.

(3) Aumentamos paso a paso el segundo factor encontrando divisores de 225, hasta que el tercero sea menor o igual que el segundo, y ahí paramos. Obtendríamos 2*5*45, 2*9*25, 2*15*15. Retrocedemos al primer factor 2 y lo avanzamos de igual manera con los siguientes divisores: 3*3*50, 3*5*30, 3*6*25, 3*10*15, 5*5*18, 5*6*15 y 5*9*10. Paramos ahí porque no existen más ternas no decrecientes.

Esta misma técnica sirve para descomponer N en M factores. Creamos un índice R que representa el número de orden del factor. Comenzamos con R=1 y buscamos factores crecientes, aumentando el valor de R hasta llegar a M, y dividiendo el número N entra cada factor. Cuando obtengamos una solución rebajamos R en una unidad, reconstruimos N parcialmente y buscamos nuevos factores avanzando y retrocediendo R, hasta que llega un momento en que R=0, y es la señal para que se detenga el algoritmo.

Si lo anterior te resulta complicado de entender, descarga uno de estos archivos

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/enfactores.ods
http://www.hojamat.es/sindecimales/divisibilidad/herramientas/hojas/enfactores.xls

y estudia el algoritmo con el Editor de Basic.

No hay comentarios: