[已解决]求大佬解答！！急！！

‘林夕’

编写一个算法，求出5个数的中位数（两个数比它小，两个数比它大），要求对于任意有效的输入，算法种发生比较的次数都要小于7次。

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-9-23 23:28:44

如果只是求中位数的话，六次就够了，排序才需要七次

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.     int a,b,c,d,e;
   
5.     int max1,max2,min1,min2;
   
6.     scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
   
7.     if (a>b)//第一次
   
8.         max1=a,min1=b;
   
9.     else
   
10.         max1=b,min1=a;
    
11.     if (c>d)//第二次
    
12.         max2=c,min2=d;
    
13.     else
    
14.         max2=d,min2=c;
    
15.     if (max1>max2)//第三次
    
16.         if (min1>e)//第四次
    
17.             if(min1>max2)//第五次
    
18.                 if(max2>e)//第六次
    
19.                     printf("中位数是：%d",max2);
    
20.                 else
    
21.                     printf("中位数是：%d",e);
    
22.             else
    
23.                 if(min1>min2)//第六次
    
24.                     printf("中位数是：%d",min1);
    
25.                 else
    
26.                     printf("中位数是：%d",min2);
    
27.         else
    
28.             if(e>max2)//第五次
    
29.                 if(max2>min1)//第六次
    
30.                     printf("中位数是：%d",max2);
    
31.                 else
    
32.                     printf("中位数是：%d",min1);
    
33.             else
    
34.                 if(min2>e)//第六次
    
35.                     printf("中位数是：%d",min2);
    
36.                 else
    
37.                     printf("中位数是：%d",e);
    
38.     else
    
39.         if (min2>e)//第四次
    
40.             if(min2>max1)//第五次
    
41.                 if(max1>e)//第六次
    
42.                     printf("中位数是：%d",max1);
    
43.                 else
    
44.                     printf("中位数是：%d",e);
    
45.             else
    
46.                 if(min2>min1)//第六次
    
47.                     printf("中位数是：%d",min2);
    
48.                 else
    
49.                     printf("中位数是：%d",min1);
    
50.         else
    
51.             if(e>max1)//第五次
    
52.                 if(max1>min2)//第六次
    
53.                     printf("中位数是：%d",max1);
    
54.                 else
    
55.                     printf("中位数是：%d",min2);
    
56.             else
    
57.                 if(min1>e)//第六次
    
58.                     printf("中位数是：%d",min1);
    
59.                 else
    
60.                     printf("中位数是：%d",e);
    
61.     return 0;
    
62. }

复制代码

跳转到最佳答案楼层

‘林夕’

想了好多算法，还是想不起来怎么在只比较不大于七次的情况下求出中位数

sunrise085

如果只是求中位数的话，六次就够了，排序才需要七次

1. #include<stdio.h>
   
2. int main()
   
3. {
   
4.     int a,b,c,d,e;
   
5.     int max1,max2,min1,min2;
   
6.     scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
   
7.     if (a>b)//第一次
   
8.         max1=a,min1=b;
   
9.     else
   
10.         max1=b,min1=a;
    
11.     if (c>d)//第二次
    
12.         max2=c,min2=d;
    
13.     else
    
14.         max2=d,min2=c;
    
15.     if (max1>max2)//第三次
    
16.         if (min1>e)//第四次
    
17.             if(min1>max2)//第五次
    
18.                 if(max2>e)//第六次
    
19.                     printf("中位数是：%d",max2);
    
20.                 else
    
21.                     printf("中位数是：%d",e);
    
22.             else
    
23.                 if(min1>min2)//第六次
    
24.                     printf("中位数是：%d",min1);
    
25.                 else
    
26.                     printf("中位数是：%d",min2);
    
27.         else
    
28.             if(e>max2)//第五次
    
29.                 if(max2>min1)//第六次
    
30.                     printf("中位数是：%d",max2);
    
31.                 else
    
32.                     printf("中位数是：%d",min1);
    
33.             else
    
34.                 if(min2>e)//第六次
    
35.                     printf("中位数是：%d",min2);
    
36.                 else
    
37.                     printf("中位数是：%d",e);
    
38.     else
    
39.         if (min2>e)//第四次
    
40.             if(min2>max1)//第五次
    
41.                 if(max1>e)//第六次
    
42.                     printf("中位数是：%d",max1);
    
43.                 else
    
44.                     printf("中位数是：%d",e);
    
45.             else
    
46.                 if(min2>min1)//第六次
    
47.                     printf("中位数是：%d",min2);
    
48.                 else
    
49.                     printf("中位数是：%d",min1);
    
50.         else
    
51.             if(e>max1)//第五次
    
52.                 if(max1>min2)//第六次
    
53.                     printf("中位数是：%d",max1);
    
54.                 else
    
55.                     printf("中位数是：%d",min2);
    
56.             else
    
57.                 if(min1>e)//第六次
    
58.                     printf("中位数是：%d",min1);
    
59.                 else
    
60.                     printf("中位数是：%d",e);
    
61.     return 0;
    
62. }

复制代码

sunrise085

图中a,b,c,d,e为节点，边’|’为已比较关系，大者在上，小者在下，红色为待比较数。

第1次比较，先任取两个数a, b进行比较，不妨设结果为a>b：
  a
  |
  b

第2次比较，再取另外两个数c, d进行比较，不妨设结果为c>d：
  a  c
  |  |
  b  d

第3次比较，按照上图比较a, c，比较结果如下（由于树3.1和3.2形状相同，以下仅考虑3.1的情况，而3.2同理可得）：
   a                c
  /  \           /  \
c    b         a      d
|              |         
d              b

(3.1)                   (3.2)

第4次比较，按照上图3.1比较短分枝中红色数b, e，比较结果有两种情况：
   a   e             a
  /  \ /           / \
c     b             c  b
|                   |  |
d                   d  e

(4.1)            (4.2)

第5次比较，按照上图比较其中两个标记为红色的数，4.1比较c, e，4.2比较c, b：
4.1 比较后有两种情况：e>c，见5.1；e<c，见5.2；
4.2比较后有两种情况：c>b，见5.3；c<b，见5.4；
由于树5.2，5.3，5.4形状相同，因此下面仅以5.2为例，5.3，5.4做法与5.2同。
a    e                 a                          a                        a
\ /                     |                          |                        |
/ \                     c                          c                         b
c   b                 /  \                      /  \                    /  \
|                     d    e                   d    b                  e    c
d                          |                          |                        |
                            b                          e                        d

(5.1)           (5.2)                   (5.3）                (5.4)

第6次比较，按照上图比较其中两个标记为红色的数，比较结果有两种情况：
5.1中c, b比较，c<b，b为中值，见6.1；c>b，c为中值，见6.2；
5.2中d, e比较，d>e，d为中值，见6.3；d<e，e为中值，见6.4；
a   e        a    e              a                   a
\  /          \  /               |                   |
  b             c                  c                   c
  |           /  \                |                  |
  c          d   b                d                  e
  |                                 |                 / \
  d                                 e                d  b
                                     |
                                     b

(6.1)        (6.2)         (6.3)             (6.4)

至此，经6次比较得出5个数的中值。

乐乐学编程

我来学习

‘林夕’

sunrise085 发表于 2020-9-23 23:34
图中a,b,c,d,e为节点，边’|’为已比较关系，大者在上，小者在下，红色为待比较数。

第1次比较，先任取 ...

非常感谢