查找三个值中较大和较小值的最有效算法

编辑：有人正在阅读这个奇怪的改变，我想补充最后一件事。假设问题中的三个值已经在内存中，并且没有改变，我已经计算出不少于14条指令能够实现这个壮举。查找三个值中较大和较小值的最有效算法

我非常喜欢这证实，如果任何人都可以。

[top edit end]

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

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

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

如果只存在于交换变量的简单方法...好吧，我能想到的唯一的事情就是可以消除的需要，“最大”，至少在C和C衍生物，一定止跌除了内存使用方面外，它的效率并不高，我可以花费额外的4个字节。 ;）

来源

2012-09-02 Zacariaz

“但是我的意图离子是找到最有效的算法“最有效的方面是什么？使用最少的内存？平均执行时间最快？最快的最坏情况执行时间？最少的比较？最少的代码行？ –

对于只有两个条件运行的输入？ – Deestan

我的错误是，没有只有两个条件的情况。至于我的意思是最有效......也许我应该用“聪明”这个词代替。我可以从数学的角度来说，涉及最少的步骤或最优雅的解决方案。 – Zacariaz

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-02 16:02:59 ladaghini

与我以前的最爱一样，只是在作业上更聪明。谢谢 – Zacariaz

既然你只有3我会使用类似：

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

我不能完全确定你使用的是什么语言，但大多数每一种语言都有一个最大的功能，内置的或容易无障碍。

来源

2012-09-02 14:48:54 mjgpy3

如果你定义这个短语，“我的意图是找到最有效的算法”，意思是“最少的比较”，而不是确定的意思。我认为他的意思是最短的代码长度和最简单的。 – mjgpy3

我喜欢这个，因为它很容易理解。所以除非这是一种实时嵌入式软件 - 我认为这将是最好的选择 – Gir

它简洁易懂，但它使用4种比较，而真正需要3种。 –

也许

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-02 14:53:10 podiluska

这是不是有什么问题？ – Zacariaz

只有复制和粘贴错误。 – podiluska

我尽量多的。聪明的解决方案。 – Zacariaz

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（已解码的本机缓存）

来源

2012-09-02 14:54:05

好 - 但XOR交换噱头不仅邪恶，而且效率也很低。 –

我知道:)，刚刚添加来填补空白区域。也可以在__asm {}中使用SIMD（也许xchg就足够了）。是的你是对的，但这是有效的空间我觉得:) –

没有想到这一点。基本上与我正在做的事情是一样的，除非如上所述，这是非常低效的。 ;） – Zacariaz

这使用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-02 14:59:33 verdesmarald

非常聪明，只有两个额外的分配。 – Zacariaz

一种计算机/列举的开关应该给编译器足够的自由来minimalise（条件）的量跳转：

#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-02 15:47:31 wildplasser

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-02 15:54:59 user1398593

此解决方案使用比较23之间。

返回值是夫妻（最小，最大）。

挑选3个给定数字中的2个数字。
比较他们，并让我们打电话给较小的一个a和较大的一个b。
可以拨打未选号码c。
如果c> = b，则返回（a，c）。
如果c> = a，则返回（a，b）。
return（c，b）。

来源

2012-09-02 16:02:14

我必须承认这让我困惑。 – Zacariaz

我将编辑答案。 –

-1

如果（NUM1> NUM2 & & NUM1> NUM3）然后 - > NUM1是最大的

否则，如果（NUM2> NUM1 & & NUM2> NUM3）然后 - > NUM2是最大

其他然后 - > NUM3是最大的

来源

2015-08-16 08:36:37

查找三个值中较大和较小值的最有效算法

回答

相关问题