| Pregunta: | 14853 - FORMULA MATEMáTICA |
| Autor: | Natalia Vargas Serrano |
| Gente necesito por favor ¡Urgente! alguien que me ayude con el siguiente problema que me dejo un profe.Necesito lo mas pronto posible el algoritmo o en Pascal. Hallar la descomposición de un número entero positivo n cualquiera (que se debe leer igual que K ) en enteros cuyas sumas sea igual a K Ej: 5= 1+1+1+1+1 2+1+1+1 3+1+1 4+1 2+3 2+2+1 Gracias | |
| Respuesta: | Dabiz Spuch Calvar |
| Hola Natalia, a primera vista parecía sencillo este algoritmo, me ha llevado un ratillo pero finalmente conseguí un algoritmo aceptable, te explico: Me he valido de la recursividad (Pascal permite recursividad). Se define la función descomposición de n de la siguiente forma: des(1) = 1 des(2) = {des(1) + 1} des(3) = {des(2) +1, des(1) + 2} ... des(n) = {des(1) + (n-1) , des(2) + (n-2), ..., des(n-1) + 1} Esta es la definición matemática. Es importante darse cuenta de que des(n) no es matemáticamente una función ya que devuelve un conjunto de resultados. Cuando lo implementes en Pascal tendrás que tener en cuenta esto para ir almacenando los resultados en un vector. Ejemplo: des(5) = {des(4) + 1, des(3) + 2, des(2) + 3, des(1) + 4} des(4) = {des(3) + 1, des(2) + 2, des(1) + 3} des(3) = {des(2) + 1, des(1) + 2} des(2) = {des(1) + 1} = 1 + 1 des(3) = {(1+1)+1, (1) + 2} des(4) = {((1+1) + 1) + 1, ((1) + 2) + 1, (1+1) + 2, 1 + 3} des(5) = {(((1+1) + 1) + 1) + 1, (((1) + 2) + 1) + 1, ((1 + 1) + 2) + 1, (1 + 3) + 1, ((1+1)+1) + 2, ((1) + 2) + 2, (1+1) + 3, 1 + 4} Fíjate que con este algoritmo se nos van a repetir resultados, para la descomposición de 5 obtenemos: 5 = 1+1+1+1+1 5 = 1+2+1+1 5 = 1+1+2+1 5 = 1+3+1 5 = 1+1+1+2 5 = 1+2+2 5 = 1+1+3 5 = 1+4 De todas es fácil evitar los resultados repetidos, tienes dos alternativas: 1) Cuando almacenas el resultado en el vector comparas primero si ya existe. 2) Basta con que almacenes los resultados que tienen sus factores ordenados, es decir, almacena 1+1+1+2 y no almacenes 1+2+1+1, 2+1+1+1 ni 1+1+2+1. Si tienes problemas para implementarlo en Pascal no dudes en preguntarme. Un saludo. | |