7
Puedo encontrar la mediana con 12 comparaciones. Pero quiero saber el número mínimo de comparaciones y cómo hacerlo.Número de comparaciones que encuentran la mediana de 7 números
A
Respuesta
7
Donald Knuth tiene un capítulo sobre "Selección mínima de comparación" en el Volumen III de El arte de la programación de computadoras.
Knuth dice: "ningún método general [de selección en el número mínimo de comparaciones] es evidente hasta el momento", pero da algunos métodos generales que se acercan al mínimo.
Al mirar la Tabla 5.3.3-1, podemos ver que V₄ (7) = 10 (es decir, puede encontrar el cuarto más grande de 7 elementos usando como máximo 10 comparaciones), y el algoritmo ("encontrado manualmente por ensayo y error ") se da en la solución para el ejercicio 5.3.3-10.
+1
Parece que TAoCP es necesario. @ - @ – zerr
+0
@zerr, Sin duda, siempre es necesario –
1
Si permite comparaciones en paralelo (una CPU moderna probablemente hará esto por usted), puede usar un sorting network para resolver el problema en seis pasos.
+0
¿Podría proporcionar una referencia a la implementación de 6 comparaciones? Gracias –
+0
Claro, aquí tienes: http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Rafe
+0
Vi ese artículo, pero creo que no puede decir que n = 7 podría hacerse con 6 comparaciones . –
Cuestiones relacionadas
- 1. Número de clasificación 4 con pocas comparaciones
- 2. Número de comparaciones con merge sort
- 3. ¿Es posible calcular la mediana de una lista de números mejor que O (n log n)?
- 4. Ordenar una matriz con un número mínimo de comparaciones
- 5. Cómo calcular la media, la mediana, el modo y el rango de un conjunto de números
- 6. ¿Cómo puedo calcular la mediana y la desviación estándar de una serie de números en Perl?
- 7. interviewstreet desafío mediana
- 8. Mediana de 5 matrices ordenadas
- 9. Pregunta de la entrevista: Halla la mediana del número mega de enteros
- 10. Encuentre una mediana en paralelo
- 11. ¿Cómo puedo encontrar la mediana de los números en tiempo lineal usando montones?
- 12. Comparaciones avanzadas de cadenas en Oracle SQL
- 13. Creando una matriz de números que suman un número dado
- 14. php importancia de un número en un conjunto de números
- 15. Java 7: ThreadLocalRandom que genera los mismos números aleatorios
- 16. Calcular la mediana en C#
- 17. hallazgo se preguntó mediana de 5 elementos
- 18. generación de números aleatorios - Mismo número devuelto
- 19. Probabilidad de encontrar la mediana con espacio finito
- 20. entendimiento "mediana de las medianas" algoritmo
- 21. Computación mediana incremental con la máxima eficiencia de memoria
- 22. la eliminación de duplicados utilizando comparaciones personalizados
- 23. Obtenga todos los números que se suman a un número
- 24. Buscar conjunto de números en una colección que se suma a un número en otra
- 25. comparaciones de fechas de Python
- 26. Obtenga números específicos de la cadena
- 27. Encuentra cuatro números consecutivos que suman el número dado
- 28. comparaciones de cadenas de bash
- 29. Mediana Función en C Biblioteca Matemática?
- 30. Comportamiento impar con mediana()?
Me gustaría ver su implementación: parece que no puedo hacerlo en menos de 18 operaciones. –
Para a, b, c, d, e, f, g, intente a
zerr