Dada una permutación de $n$número $1, 2, 3,\dots,n$. Cómo comprobar si existen $a,\ b$ con la misma paridad tal que $\frac {a + b} 2$ entre $a, b$.
¿Cómo resolver este problema eficazmente? (algoritmo aproximado es buena también)
Respuesta
¿Demasiados anuncios?
kabumm
Puntos
96
Mi primera idea: digamos que usted tiene los números de $x,y,z$ en su permutación con $y=\frac{x+z}{2}$ y aparecen en ese orden. Esto significa $y-x=z-y$ debe ser cierto. Ahora iterar a través de todos los posibles valores de $y$, yo. e. todos los números en la posición $2,\dots,n-1$ y generar dos listas: calcular el $y-x$ para todos los valores de $x$$y$, e $z-y$ para todos los valores de $z$ a la derecha de $y$. Si usted encuentra un número que coincida en estas listas, la respuesta es sí, de lo contrario no.
Ejemplo: Permutación es $(5,1,6,4,2,7,3)$. Primer paso $y=1$ los rendimientos de las listas: $(-4)$ $(5,3,1,6,2)$ sin partidos. En el segundo paso $y=6$ obtenemos $(\mathbf{1},5)$$(-2,-4,\mathbf{1},-3)$. La coincidencia de número 1 corresponde a la 5, 6 y 7 en la permutación. Este debe tener cúbicos tiempo de complejidad. Si eso no es lo suficientemente rápido para usted, me gustaría considerar el uso de algún tipo de árbol basado en el algoritmo.
Actualización: he implementado este algoritmo y de hecho algunas pruebas. Para una permutación aleatoria el algoritmo es bastante rápido y puede calcular la respuesta a a $n=100000$ en cuestión de segundos. Pero, por supuesto, el más grande de su $n$, la más difícil llega a encontrar una permutación que no tiene la propiedad deseada: por ejemplo, Para $n=9$ ya tenemos el 99,9% de las permutaciones de los cuales se destacan la prueba. Así que la mayoría de las veces usted sólo tiene que calcular algunas de las listas con el fin de obtener el resultado. Pero si tenía que comprobar todas las permutaciones para un n dado que vas a necesitar algunos otros métodos...
