在C#中计算“中位数为5”的代码

注意:请不要将此解释为“作业问题”。 这只是我很想知道的事情:)

中值为5有时用作算法设计中的练习,并且已知仅使用6次比较可计算。

在C# 实现“使用6次比较的五个中值”的最佳方法是什么? 我所有的尝试似乎都导致代码笨拙:(我需要漂亮可读的代码,同时仍然只使用6次比较。

public double medianOfFive(double a, double b, double c, double d, double e){ // // return median // return c; } 

注意:我想我也应该提供“算法”:

我发现自己无法像Azereal在论坛post中那样清楚地解释算法。 所以我会在这里引用他的post。 来自http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

好吧,我在我的一个任务中提出了这个问题,我转向这个论坛寻求帮助,但没有帮助。 我终于找到了怎么做。

  1. 使用前4个元素启动mergesort并订购每对(2个比较)

  2. 比较每对中的两个较低的一个并从可能性中消除最低的一个(3个比较)

  3. 在没有配对的情况下添加第5个数字并比较两个(4个比较)

  4. 比较两个新对中的两个最低对并消除较低对(5个比较)

  5. 比较一个单独和最后一对中的较低者,较低的数字是中位数

    可能的中位数在肠胃外

(54321)

5:4 3:2 2比较

(4 <5 2 <3 1)

4:2 3比较

2(4 <5 3 1)

1:3 4比较

2(4 <5 1 <3)

4:1 5比较

1,2(4 <5 3)

4:3 6比较

1,2(3)4,5-

三是中位数

编辑:作为您的请求,并防止自己得到更多的downvotes,这是我写的C ++代码,找到五个中位数。 不要介意它的尴尬:

 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; } 

它应该更紧凑,不是吗?

编辑:

正如@pablito在他的回答中指出的那样。 内置的List.Sort()无法满足此要求,因为它最多使用13次比较:]

这基本上只是考虑了C ++示例中的交换和排序代码:

 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); } 

我发现这篇文章很有意思,作为一个练习我创建了这个只有6个比较而且没有其他的:

 static double MedianOfFive(double a, double b, double c, double d, double e) { return b < a ? d < c ? b < d ? a < e ? a < d ? e < d ? e : d : c < a ? c : a : e < d ? a < d ? a : d : c < e ? c : e : c < e ? b < c ? a < c ? a : c : e < b ? e : b : b < e ? a < e ? a : e : c < b ? c : b : b < c ? a < e ? a < c ? e < c ? e : c : d < a ? d : a : e < c ? a < c ? a : c : d < e ? d : e : d < e ? b < d ? a < d ? a : d : e < b ? e : b : b < e ? a < e ? a : e : d < b ? d : b : d < c ? a < d ? b < e ? b < d ? e < d ? e : d : c < b ? c : b : e < d ? b < d ? b : d : c < e ? c : e : c < e ? a < c ? b < c ? b : c : e < a ? e : a : a < e ? b < e ? b : e : c < a ? c : a : a < c ? b < e ? b < c ? e < c ? e : c : d < b ? d : b : e < c ? b < c ? b : c : d < e ? d : e : d < e ? a < d ? b < d ? b : d : e < a ? e : a : a < e ? b < e ? b : e : d < a ? d : a; } 

谢谢。 我知道你的post很旧,但对我的问题很有用。

我需要一种方法来计算5个SSE / AVX寄存器的中位数(一次4个浮点数/ 8个浮点数,或者一次计算2个双打/ 4个双打):

  • 没有任何条件跳跃

  • 仅限最小/最大指令

如果使用条件跳转为标量寄存器编程最小/最大函数,则我的代码在比较方面不是最佳的。 但是如果使用相应的CPU指令编写最小/最大函数,我的代码非常有效,因为CPU在执行时不会执行条件跳转。

  template inline V median(const V &a, const V &b, const V &c) { return max(min(a,b),min(c,max(a,b))); } template inline V median(const V &a, const V &b, const V &c, const V &d, const V &e) { V f=max(min(a,b),min(c,d)); // discards lowest from first 4 V g=min(max(a,b),max(c,d)); // discards biggest from first 4 return median(e,f,g); } 

这非常难看并且可以使用一些重构,但它明确地遍历所有比较和交换,以便您可以看到正在发生的事情。

 public double medianOfFive(double a, double b, double c, double d, double e){ double median; // sort a and b if(a > b) // comparison # 1 { double temp = a; a = b; b = temp; } // sort c and d if(c > d) // comparison # 2 { double temp = c; c = d; d = temp; } // replace the lower of a and c with e // because the lowest of the first four cannot be the median if(a < c) // comparison # 3 { a = e; // re-sort a and b if(a > b) // comparison # 4 { double temp = a; a = b; b = temp; } } else { c = e; // re-sort c and d if(c > d) // comparison # 4 { double temp = c; c = d; d = temp; } } // eliminate a or c, because the lowest // of the remaining four can't be the median either if(a < c) // comparison #5 { if(b < c) // comparison #6 { median = c; } else { median = b; } } else { if(d < a) // comparison #6 { median = a; } else { median = d; } } return median; } 

一个有趣的主题:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

从线程引用:

  1. 将数字放在一个数组中。

  2. 使用三个比较并在数字周围移动,使得[1]

  3. 如果[3]> a [2],则问题相当容易。 如果a [2]

  4. 所以a [3] a [4],那么解是[3]和[5]中较小的一个。 否则,解决方案是a [2]和[4]中的较小者。

只是为了检查一下比较:

  class MyComparable : IComparable { public static int NumberOfComparisons = 0; public int NumPart { get; set; } #region IComparable Members public int CompareTo(object obj) { NumberOfComparisons++; //I know, not thread safe but just for the sample MyComparable mc = obj as MyComparable; if (mc == null) return -1; else return NumPart.CompareTo(mc.NumPart); } #endregion } class Program { static void Main(string[] args) { List list = new List(); list.Add(new MyComparable() { NumPart = 5 }); list.Add(new MyComparable() { NumPart = 4 }); list.Add(new MyComparable() { NumPart = 3 }); list.Add(new MyComparable() { NumPart = 2 }); list.Add(new MyComparable() { NumPart = 1 }); list.Sort(); Console.WriteLine(MyComparable.NumberOfComparisons); } } 

结果是13。

为了完整起见,问题是分类网络的具体情况, Knuth( 计算机编程艺术 ,第3卷)详细介绍了该分类网络 。 KE Batcher关于这一主题的经典论文简短而值得一读。

这应该做到这一点

 private Double medianofFive(double[] input) { Double temp; if (input[0] > input[1])//#1 - sort First and Second { temp = input[0]; input[0] = input[1]; input[1] = temp; } if (input[2] > input[3])//#2 sort Third and Fourth { temp = input[2]; input[2] = input[3]; input[3] = temp; } // replace the smaller of first and third with 5th, then sort int smallerIndex = input[0] < input[2] ? 0 : 2;//#3 input[smallerIndex] = input[4]; //sort the new pair if(input[smallerIndex]>input[smallerIndex+1])//#4 { temp = input[smallerIndex]; input[smallerIndex] = input[smallerIndex+1]; input[smallerIndex+1] = temp; } //compare the two smaller numbers // then compare the smaller of the two's partner with larger of the two // the smaller of THOSE two is the median if (input[2] > input[0]) //#5 { temp = input[2] > input[1] ? input[1] : input[2];//#6 } else { temp = input[0] > input[3] ? input[3] : input[0];//#6 } return temp; } 
 -- In Haskell the solution could look like import Data.Function median5By pred [a,b,c,d,e] = fst $ merge2 c' d' where merge2 = merge2By pred merge2By pred xy = if x `pred` y then (x,y) else (y,x) ((_,b'), de ) = merge2By (pred `on` fst) (merge2 ab) (merge2 de) ((_,c'),(d',_)) = merge2By (pred `on` fst) (merge2 b' c) de main = print $ median5By (<) [2,5,4,1,3] 

有趣的MSDN样本中有多少比较……

 public static double Median(this IEnumerable source) { if (source.Count() == 0) throw new InvalidOperationException("Cannot compute median for an empty set."); var sortedList = from number in source orderby number select number; int itemIndex = (int)sortedList.Count() / 2; if (sortedList.Count() % 2 == 0) { // Even number of items. return (sortedList.ElementAt(itemIndex) + sortedList.ElementAt(itemIndex - 1)) / 2; } else { // Odd number of items. return sortedList.ElementAt(itemIndex); } }