我如何计算“五位数中位数”？在C＃中？ [英] How do I calculate the "median of five" in C#?
问题描述
5的中位数有时在算法设计中用作练习，并且已知可以通过<6>比较来进行计算。
The median of five is sometimes used as an exercise in algorithm design and is known to be computable using only 6 comparisons.
什么在C＃中实现这种使用6个比较中的5个中位数 的最佳方法是什么？我所有的尝试似乎都导致代码笨拙：(我需要漂亮且易读的代码，同时仍然仅使用6个比较。
What is the best way to implement this "median of five using 6 comparisons" in C# ? All of my attempts seem to result in awkward code :( I need nice and readable code while still using only 6 comparisons.
public double medianOfFive(double a, double b, double c, double d, double e){
//
// return median
//
return c;
}
注意：我想我也应该在此处提供算法 ：
Note: I think I should provide the "algorithm" here too:
我发现自己无法像 Azereal 在他的论坛帖子中那样清楚地解释该算法，因此我将在此处引用他的帖子。 http ：//www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi？board = riddles_cs; action = display; num = 1061827085
I found myself not able to explain the algorithm clearly as Azereal did in his forum post. So I will reference his post here. From http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085
好吧，我在一个
的作业中遇到了这个问题，我转向这个
论坛寻求帮助，但这里没有帮助。佛
Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it.
-
使用前4个元素开始合并排序并排序每对（2个
比较）
Start a mergesort with the first 4 elements and order each pair (2 comparisons)
比较每对中的两个较低的对，并从
中消除最低的可能性（3个比较）
Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons)
将第5个数字添加到不带对的数字中，然后将
进行两次比较（4个比较）
Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons)
比较两个新对中的两个最低的对，并消除较低的一个
（5个比较）
Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons)
单独比较一个对而最后一对货币对中的较低者和较低的
数字是中位数
Compare the one by itself and the lower of the last pair and the lower number is the median
可能的中位数在
括号内
The possible median is within the parentesis
（54321）
5：4 3：2 2比较
5:4 3:2 2 comparisons
（4 <5 2 <3 1）
(4<5 2<3 1)
4：2 3比较
2（4 <5 3 1）
2(4<5 3 1)
1：3 4比较
2（4 <5 1 <3）
2(4<5 1<3)
4：1 5比较
1,2（4 <5 3）
1,2(4<5 3)
4：3 6个比较
1,2（3 ）4,5
1,2(3)4,5
三个是中位数
这里是C ++我写的代码中位数是5。不要介意它的尴尬：
Here is the C++ code I wrote to find median of five. Don't mind its awkwardness:
double StageGenerator::MedianOfFive(double n1, double n2, double n3, double n4, double n5){
double *a = &n1, *b = &n2, *c = &n3, *d = &n4, *e = &n5;
double *tmp;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
if(*d < *c){
tmp = c; c = d; d = tmp;
}
// eleminate the lowest
if(*c < *a){
tmp = b; b = d; d = tmp;
c = a;
}
// gets e in
a = e;
// makes a < b and b < d
if(*b < *a){
tmp = a; a = b; b = tmp;
}
// eliminate another lowest
// remaing: a,b,d
if(*a < *c){
tmp = b; b = d; d = tmp;
a = c;
}
if(*d < *a)
return *d;
else
return *a;
}
它应该更紧凑，不是吗？
It should be more compact, isn't it ?
正如@pablito在他的回答中指出的那样，内置的 List.Sort（）不能满足此要求，因为它最多使用13个比较：]
As @pablito pointed out in his answer, the built-in List.Sort() cannot fulfill this requirement since it uses up to 13 comparisons :]
推荐答案
这基本上只是出于考虑C ++示例中的交换和排序代码：
This is basically just factoring out the swapping and sorting code from your C++ example:
private static void Swap(ref double a, ref double b) {
double t = a;
a = b;
b = t;
}
private static void Sort(ref double a, ref double b) {
if (a > b) {
double t = a;
a = b;
b = t;
}
}
private static double MedianOfFive(double a, double b, double c, double d, double e){
// makes a < b and c < d
Sort(ref a, ref b);
Sort(ref c, ref d);
// eleminate the lowest
if (c < a) {
Swap(ref b, ref d);
c = a;
}
// gets e in
a = e;
// makes a < b
Sort(ref a, ref b);
// eliminate another lowest
// remaing: a,b,d
if (a < c) {
Swap(ref b, ref d);
a = c;
}
return Math.Min(d, a);
}
这篇关于我如何计算“五位数中位数”？在C＃中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
