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

Question

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

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

在C#中实现"使用6次比较的五个中位数"的最佳方法是什么？我的所有尝试似乎都导致了尴尬的代码:(我需要漂亮可读的代码,同时仍然只使用6次比较.

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

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

我发现自己无法像Azereal在论坛帖子中那样清楚地解释算法.所以我会在这里引用他的帖子.来自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次比较:]

Answer 1

我发现这篇文章很有趣,作为一个练习我创建了这个只有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;
}

Answer 2

这基本上只是将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);
}

Answer 3

谢谢.我知道你的帖子很旧,但对我的问题很有帮助.

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

• 没有任何条件跳跃

• 仅限最小/最大指令

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

    template<class V> 
    inline V median(const V &a, const V &b, const V &c)
    {
      return max(min(a,b),min(c,max(a,b))); 
    } 

    template<class V> 
    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);
    } 

Answer 4

一个有趣的主题:

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

从线程引用:

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

2. 使用三个比较并在数字周围移动,以便[1] <a [2],a [4] <a [5]和[1] <a [4].

3. 如果[3]> a [2],则问题相当容易.如果a [2] <a [4],则中值为a [3]和[4]中的较小者.如果不是,则中值是a [2]和[5]中的较小者.

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

Answer 5

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

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