Nombre de comparaisons trouver la médiane de 7 chiffres [clos]

Question

Je peux trouver la médiane avec 12 comparaisons. Mais je veux connaître le nombre minimum de comparaisons et comment le faire.

Answer 1

Donald Knuth a un chapitre sur "Sélection minimum de comparaison" dans le volume III de L'art de la programmation informatique .

Knuth dit: « pas de méthode générale [de la sélection du nombre minimum de comparaisons] est évidente encore » mais il donne quelques méthodes générales qui se rapprochent au minimum.

Dans la table 5.3.3-1, nous pouvons voir que V4 (7) = 10 (qui est, vous pouvez trouver le 4ème plus grand de 7 articles en utilisant au plus 10 comparaisons), et l'algorithme ( "trouvé manuellement essais et erreurs ") est donnée dans la solution à l'exercice 5.3.3-10.

Answer 2

Si vous permettent des comparaisons en parallèle (un processeur moderne sera probablement le faire pour vous), vous pouvez utiliser un réseau de tri pour résoudre le problème en six étapes.

Answer 3

Pour (7s), vous savez que vous êtes sur la bonne voie quand vous repérer les robots volants (diagramme de Hasse). Il y a deux cas principaux pour vérifier 10 comps; d'autres cas ne sont pas près de la limite. (7S) est proche d'un casse-tête parfait, comme Puzzle Zebra E. Pas trop dur, mais assez dur pour que la discipline va se fissurer sur leur premier rendez-vous.

(4s, 3), également avec 7 chiffres, est l'égal de (7S). Ici, nous supposons que l'un des numéros répète trois fois (a) la multiplicité 3. Je ne vais pas vous dire ce que la réponse (hauteur de l'arbre optimal ternaire décembre.) Est. Allez trouver les gars!