Re: [問題] 用最少比較次數找最大、最小等值

作者: cocoyan (摳摳厭)   2016-07-05 04:41:33
※ 引述《cocoyan (摳摳厭)》之銘言:
※ 引述《lionhome20 (林北大GG)》之銘言:
: 各位神人好
: 想請問在int array[5000]裡
: 如何用最少的compare次數
: 找出最大 最小 次大 次小的值
: 有沒有小於下列5000*4次 compare的找法
: (找每一個數都用暴力法)
: for(i=0;i<5000;i++)
: if(array[i] > Max)
: Max = array[i]
: 感謝
int Max;
int Max2;
int Min;
int Min2;
if(array[0]>array[1])
{
Max=array[0];
Max2=array[1];
Min=array[1];
Min2=array[0];
}
else
{
Max=array[1];
Max2=array[0];
Min=array[0];
Max2=array[1];
}
for(i=2;i<5000;i++)
{
if(array[i]>Max2)
{
Max2=array[i];
if(Max2>Max)
{
swap(Max,Max2);
}
}
if(array[i]<Min2)
{
Min2=array[i];
if(Min2<Min)
{
swap(Min,Min2);
}
}
}
推 yvb: 程式概念是對的,但細節是錯的,可能無法得到正確答案. 07/04 14:22
→ yvb: 1. for中兩個if內的式子,將導致Max和Max2相同,同理Min和Min2. 07/04 14:31
→ yvb: 2. for的if,應跟次大或次小比,不然a[i]若介於最大和次大間... 07/04 14:33
→ yvb: 3. 由2. 因為要和次大次小比,無法改成else if. 07/04 14:34
訂正完畢!
作者: yvb   2015-07-04 14:22:00
程式概念是對的,但細節是錯的,可能無法得到正確答案.1. for中兩個if內的式子,將導致Max和Max2相同,同理Min和Min2.2. for的if,應跟次大或次小比,不然a[i]若介於最大和次大間...3. 由2. 因為要和次大次小比,無法改成else if.

Links booklink

Contact Us: admin [ a t ] ucptt.com