首页 > 试题广场 >

16.将5个数的序列排序,不论原先的顺序如何,最少都可以通过

[单选题]

16.将5个数的序列排序,不论原先的顺序如何,最少都可以通过(  )次比较,完成从小到大的排序。

  • 6
  • 7
  • 8
  • 9
法一转自新浪微博
(NOIP2006普及组)将5个数的序列排序,不论原先的顺序如何,最少都可以通过( )次比较,完成从小到大的排序。
 A. 6 B. 7 C. 8 D. 9 

5个数,a、b、c、d、e
第一次比较a、b,不妨设a>b
第二次比较c、d,不妨设c>d
第三次比较a、c,不妨设a>c


这个时候有结果a>b且a>c>d
关键的时候到了,千万不要让b提前排序,这样会浪费掉1次。


第四次比较c,e
第五次(e>c,则e与a比较;e<c,则e与d比较)
第五次结束后会形成以下四种情况之一:(另已知a>b)
1、e>a>c>d
2、a>e>c>d
3、a>c>e>d
4、a>c>d>e


情况1、e>a>c>d
第六七次用b分别与c,d比较就行。


情况2、a>e>c>d
第六次,b与c比较
第七次(b>c,则b与e比较;b<c,则b与d比较)


情况3、a>c>e>d(方法同情况2继续六七次)
情况4、a>c>d>e(方法同情况2继续六七次)

方法二来自作业帮
7 次
5个数的总排列可能情况数是5!=120
比较出任意两个数的大小一次,情况数就可减少一半
(一半是存在甲大于乙的排列情况,一种是存在甲小于乙的排列情况)
120/2=60
60/2=30
30/2=15
15/2=8(7.5)
8/2=4
4/2=2
2/2=1
(当分组分到每组只有一个时,从小到大的排列就唯一确定了)

发表于 2018-10-13 10:44:23 回复(0)