Título: Particion aritmetica en python Publicado por: dijsktra en 11 Marzo 2018, 00:47 am Vuelvo a recuperar la cuestión no resuelta desde Mayo del 2017
https://foro.elhacker.net/ejercicios/ejercicio_bucle_while_en_python-t469250.0.html "Dados dos números enteros n (n≥0) y a (a>0) encontrar, si existe, el menor entero x del intervalo [0, n] para el que se cumpla lo siguiente: la diferencia entre las sumas de los valores enteros de los intervalos [n-x, n] y [0, x] coincide con a." Se mostraron dos soluciones: La primera es incorrecta, ya que para n = 100000 y para a= 350 se daba x=449, cosa que no es cierta, pues Código: >>> n,a,x = 100000, 350, 449 En la segunda, se dice que el problema se puede resolver en O(1) sin más que resolver la ecuacion Código: (n-x)x+(n-x)=a Código: >>> n,x Propongo mi solución. La ecuación que hay que resolver en valores enteros 0 <= x <=n es (al final del mensaje digo como la he obtenido): Código: n(n+1) = 2(a+x^2) En el cuerpo de los complejos, siempre tiene solución, pero en los enteros 0 <= x <= n puede que ésta no exista, por lo que emplearé el tipo None de Python para expresar esta circunstancia... El algoritmo python que lo resuelve es el siguiente: Código
Van algunos ejemplos Código: >>> for n in range(5,10): Lo que arroja esta salida Código: 5 6 => Sol : 3 Vemos que Código:
El caso n=100000 y a = 350, no tiene solución. Si puedo, mañana escribo de donde sale la ecuación. |