Herramientas de usuario
algoritmos-oia:busqueda-ternaria
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:busqueda-ternaria [2018/01/20 14:31] santo [Utilidad de la búsqueda ternaria] |
algoritmos-oia:busqueda-ternaria [2018/01/21 16:57] (actual) santo |
||
|---|---|---|---|
| Línea 161: | Línea 161: | ||
| Hay que tener cuidado porque cuando hagamos (b-a)/3, quizás no caemos en un número de igual resto en la división por $3$ que lo que queremos, entonces pensar en llevar a todos los número hacia éste no tendría sentido. Lo que podemos hacer en este problema para evitar esto, es primero, restarles a todos los números su resto en la división por $d$, total lo que importa son sus diferencias relativas ya que vamos a sumar y restar $d$. Y luego, es pensar "a qué múltiplo de $d$ queremos llevar a todos los números". Otra manera también sería divir todo por $d$ y pensar que las movidas suman y restan $1$, es completamente equivalente. | Hay que tener cuidado porque cuando hagamos (b-a)/3, quizás no caemos en un número de igual resto en la división por $3$ que lo que queremos, entonces pensar en llevar a todos los número hacia éste no tendría sentido. Lo que podemos hacer en este problema para evitar esto, es primero, restarles a todos los números su resto en la división por $d$, total lo que importa son sus diferencias relativas ya que vamos a sumar y restar $d$. Y luego, es pensar "a qué múltiplo de $d$ queremos llevar a todos los números". Otra manera también sería divir todo por $d$ y pensar que las movidas suman y restan $1$, es completamente equivalente. | ||
| + | |||
| + | Otra manera diferente de razonar y resolver este problema se explica [[algoritmos-oia:ordenamiento:mediana|en este artículo]]. | ||
| ==== Código ==== | ==== Código ==== | ||
| Línea 207: | Línea 209: | ||
| // El minimo seguro esta en el rango [a,b) elegido | // El minimo seguro esta en el rango [a,b) elegido | ||
| int a=minimo/d, b=maximo/d + 1; | int a=minimo/d, b=maximo/d + 1; | ||
| + | #define costo(x) obtenerMovidas(matriz, (x)*d, d) | ||
| while (b-a>1) | while (b-a>1) | ||
| { | { | ||
| int m1 = a + (b-a)/3; | int m1 = a + (b-a)/3; | ||
| int m2 = a + (2*(b-a))/3; | int m2 = a + (2*(b-a))/3; | ||
| - | if (obtenerMovidas(matriz, m1*d, d) <= obtenerMovidas(matriz, m2*d, d)) | + | if (costo(m1) <= costo(m2)) |
| b = m2; | b = m2; | ||
| else | else | ||
| Línea 217: | Línea 220: | ||
| } | } | ||
| // El optimo se encuentra en a, pues el rango es [a,a+1) | // El optimo se encuentra en a, pues el rango es [a,a+1) | ||
| - | cout << obtenerMovidas(matriz, a*d, d) << endl; | + | cout << costo(a) << endl; |
| }else{ | }else{ | ||
| cout << -1 << endl; | cout << -1 << endl; | ||
algoritmos-oia/busqueda-ternaria.1516458675.txt.gz · Última modificación: 2018/01/20 14:31 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
