3

编辑：有人正在阅读这篇文章的奇怪变化，我想添加最后一件事。假设有问题的三个值已经在内存中并且它们没有改变，我计算出不少于 14 条指令来实现这一壮举。

如果有人可以的话，我非常喜欢这一点。

[顶部编辑结束]

问题很简单。我有三个整数值，我需要找到最大和最小的。最大我的意思不是最小或介于两者之间，反之亦然。

由于无法在网上找到“优质解决方案”，我不得不自己尝试。

if(a > b) {
  if(a > c) {
    high = a;
    if(b > c) {
      low = c;
    }
    else {
      low = b;
    }
  }
  else {
    if(b > c) {
      high = b;
      low = c;
    }
    else {
      high = c;
      low = b;
    }
  }
}
else if(a > c) {
  if(b > c) {
    high = b;
    low = c;
  }
  else {
    high = c;
    low = b;
  }
}
else {
  low = a;
  if(b > c) {
    high = b;
  }
  else {
    high = c;
  }
}

假设我没有犯任何错误，这应该使用三个条件来解决问题。

假设它按预期工作，我实际上对我的努力很满意，但是我的目的是找到最有效的算法，所以我现在问你那是什么。

最好的祝福。

编辑：我已经审查了迄今为止提出的解决方案，它们都很好。

到目前为止我最喜欢的。

if(a>b) {
  max = a;
  min = b;
}
else {
  max = b;
  min = a;
}
if(c>max)
  max = c
else if(c< min)
  min = c

2-3个信号和2-3个条件句，如果我没记错的话。这很让人佩服。

上面的小修改，使用'a'作为'min'的别名。

if(a>b) {
  max = a;
  a = b;
}
else {
  max = b;
}
if(c>max)
  max = c
else if(c< a)
  a = c

如果只有一种简单的方法来交换变量......好吧，我唯一能想到的是可以消除对“max”的需要，至少在 C 和 C 派生中，肯定不会有效，除了在内存使用方面，我可以多花 4 个字节。;)

4

8 回答 8

4

因为你只有 3 我会使用类似的东西：

Maximum = max(a, max(b,c))
Minimum = min(a, min(b,c))

我不确定您使用的是哪种语言，但大多数语言都有一个内置或易于访问的 max 函数。

于 2012-09-02T14:48:54.933 回答
3 
if(a>b){swap(a,b);    /* in other words: a=a^b;b=a^b;a=a^b; */}
if(a>c){swap(a,c);    /*in other words: a=a^c;c=a^c;a=a^c;  */}
if(b>c){swap(b,c);    /*in other words: b=b^c;c=b^c;b=b^c;  */}
//now a is the smallest, c is the largest, but names are changed
high=c;
low=a;

如果你绝望了，

void swap(int & x, int & y)  //<--- yes it needs to be pass by reference
{
    __asm
    {
       movaps xmm5,[x]
       movaps xmm6,[y]   
       movaps [x],xmm6
       movaps [y],xmm5   //i cant say anything without trying ^^
    }

    return;

}

只有 3 次比较=更少的 cpu 错误分支预测和总循环指令将足够小以适合 cpu-loop-cache（decoded-inst.cache）

于 2012-09-02T14:54:05.443 回答
3 
def min_max(a, b, c):
    if a > b:
        min, max = b, a   # two assignments
    else:
        min, max = a, b   # ditto

    if c > max:
        max = c
    elif c < min:
        min = c

    return (min, max)
于 2012-09-02T16:02:59.987 回答
2

也许

 highest = a; lowest = a;
 if (b>a)
 {
     highest = b;
 }
 else
 {
     lowest = b;
 }
 if (c>highest)
 {
     highest = c;
 }
 else
 {
     if (c<lowest)
     {
         lowest = c;
     }
 }
于 2012-09-02T14:53:10.887 回答
1

这使用 3 个比较和 3 或 4 个分配。

min = max = a;

if a < b
    max = b
else
    min = b

if b < c
    if c > a:
        max = c
else
    if c < a:
        min = c
于 2012-09-02T14:59:33.557 回答
1

此解决方案使用 between 2to3比较。

返回值是一对（最小值，最大值）。

  • 从给定的 3 个号码中选择 2 个号码。
  • 比较它们，让我们称较小的一个a和较大的一个b。
  • 让我们拨打未被选中的号码c。
  • 如果 c>=b 则返回 (a, c)。
  • 如果 c>=a 则返回 (a, b)。
  • 返回（c，b）。
于 2012-09-02T16:02:14.457 回答
0

计算/枚举开关应该给编译器足够的自由来最小化（条件）跳转的数量：

#include <stdio.h>

static inline void minmax3(int*themin,int*themax, int a, int b, int c)
{
switch(
          1 * (a>b)
        + 2 * (a>c)
        + 4 * (c>b)
        ) {
        case 0: *themin = a; *themax = b; break;
        case 1: *themin = b; *themax = a; break;
        case 2: *themin = c; *themax = b; break;
        case 3: *themin = b; *themax = a; break;
        case 4: *themin = a; *themax = c; break;
        case 5: *themin = b; *themax = c; break;
        case 6: *themin = b; *themax = c; break;
        case 7: *themin = b; *themax = a; break;
        }
return ;
}

int main(void)
{
int a,b,c,mi,ma;

for (a=0; a <3; a++) {
        for (b=0; b <3; b++) {
                for (c=0; c <3; c++) {

                        minmax3( &mi, &ma, a, b, c);
                        printf("a=%d b=%d c=%d min=%d max=%d\n"
                        , a, b, c, mi, ma
                        );
        }}}
return 0;
}
于 2012-09-02T15:47:31.167 回答
0 
if(a>=b)
 {if(a>=c)
   {MAX=a;
    MIN=c;
    if(c>=b)
     MIN=b;
     }
  else
   MAX=c,MIN=b;
 }
else
{if(b>=c)
   {MAX=b;
    MIN=c
    if(c>=a)
     MIN=a;
     }
  else
   MAX=c,MIN=a;
 }
于 2012-09-02T15:54:59.060 回答