elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Particion aritmetica en python
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Particion aritmetica en python  (Leído 1,004 veces)
dijsktra

Desconectado Desconectado

Mensajes: 100


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Particion aritmetica en python
« en: 11 Marzo 2018, 00:47 »

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
>>> n,a,x
(100000, 350, 449)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> a ,  sum(range(x,n+1)) - sum(range(0,x+1))
(350, 4999848399)

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
diciendo que (n-x)x+(n-x)  es la diferencia buscada. Cosa que no es, ya que

Código:
>>> n,x
(100000, 449)
>>> (n-x)*x+(n-x) ==  sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> (n-x)*x+(n-x) , sum(range(x,n+1)) - sum(range(0,x+1))
(44797950, 4999848399)

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
  1. '''
  2.   P :  N >= 0 and a > 0
  3.   Q : x = min i : 0 <= i <= N and N(N+1)==2(a +i^2) : i
  4. '''
  5. def partition(N,a):
  6.    m = 0
  7.    while (m<=N) and (N*(N+1)!=2*(a+m*m)):
  8.        m=m+1
  9.    return (None if m>N else m)



Van algunos ejemplos

Código:
>>> for n in range(5,10):    
        for a in range(6,10):
            print n,a , " => Sol : " , partition(n,a)


Lo que arroja esta salida
Código:
5 6  => Sol :  3
5 7  => Sol :  None
5 8  => Sol :  None
...
9 7  => Sol :  None
9 8  => Sol :  None
9 9  => Sol :  6


Vemos que
Código:

>>> n,a,x = 5,6,3
>>> n,a,x
(5, 6, 3)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
True
>>> a , sum(range(x,n+1)) - sum(range(0,x+1))
(6, 6)

El caso n=100000 y a = 350, no tiene solución.

Si puedo, mañana escribo de donde sale la ecuación.


« Última modificación: 12 Marzo 2018, 15:08 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Operación aritmética
PHP
WHK 5 1,520 Último mensaje 20 Diciembre 2007, 23:20
por WHK
calcular media aritmética con while
Programación C/C++
indict 6 5,738 Último mensaje 8 Noviembre 2012, 22:49
por leosansan
Aritmética Binaria
Electrónica
bl@ck 0 966 Último mensaje 22 Septiembre 2014, 18:04
por bl@ck
problema con aritmetica modular
Java
+ 1 Oculto(s) 2 905 Último mensaje 22 Mayo 2016, 18:30
por + 1 Oculto(s)
ayuda con aritmetica de punteros
Programación C/C++
leo soto 2 863 Último mensaje 17 Marzo 2017, 19:21
por MAFUS
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines