作业

6次比较找出5个数的中位数

jxtxzzw · 9月6日 · 2018年 543次已读

本文写于 2018年09月06日,距今已超过 1 年,距 2018年11月02日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


因为只能比较6次,所以这个程序不能使用排序算法。

众所周知,5个整数需要完成排序,最少需要7次比较。

也就是,不能先让数组排序,然后输出中间那位。

只能一次性找到中位数。

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		// Input
		int[] a = new int[5];
		int mid;
		for (int i = 0; i < 5; i++) {
			a[i] = Integer.parseInt(args[i]);
		}

		// Sort
		if (a[0] < a[1]) {
			int tmp = a[0];
			a[0] = a[1];
			a[1] = tmp;
		}
		if (a[2] < a[3]) {
			int tmp = a[2];
			a[2] = a[3];
			a[3] = tmp;
		}
		if (a[0] < a[2]) {
			int tmp = a[0];
			a[0] = a[2];
			a[2] = tmp;
			tmp = a[1];
			a[1] = a[3];
			a[3] = tmp;
		}
		if (a[1] < a[4]) {
			int tmp = a[1];
			a[1] = a[4];
			a[4] = tmp;
		}
		if (a[1] < a[2]) {
			int tmp = a[1];
			a[1] = a[2];
			a[2] = tmp;
			tmp = a[3];
			a[3] = a[4];
			a[4] = tmp;
		}
		if (a[4] < a[2]) {
			mid = a[2];
		} else {
			mid = a[4];
		}

		// Output
		System.out.println(mid);
	}

}

这个方法与一种排序方法类似,不完全一致,就是分成有序区域和无序区域。

前2次判断保证了[0]>[1]、[2]>[3]。

第3次判断保证了[0]>[2]。

因此,到这里为止,[0]、[1]、[2]、[3]这4个数里,[0]是最大的。

不论[4]比[0]大还是比[0]小,[0]都不可能是中位数了。

第3次比较,如果需要交换,那么不仅要交换[0]和[2],还要把[1]和[3]一起交换。

至于为什么要一起交换,因为[0]>[1]、[2]>[3],应该把[0]和[1]、[2]和[3]看成组合了,如果[0]和[2]交换了,就要把[1]和[3]也一块儿交换了,不然的话(比如只交换了[0]和[2]),交换之后可能不是有序的(由于此时[0]是最大的,所以[0]>[1]显然保证,但是也许无法保证[0]和[2]交换以后,[2]还是大于[3]),只有一起交换才能保证已知组合都是有序的。

后面第4次比较保证[1]>[4]。

这时又回到了与最初情况类似的状态,[1]>[4]和[2]>[3]。

下面继续,第5次比较,比较[1]和[2],这里就相当于上面比较的[0]和[2]。

同样地,保证了[1]是[1]、[2]、[3]、[4]这4个数中最大的,所以也不可能是中位数。

这样一来,中位数只可能是[2]、[3]、[4]中的一个。

而[2]>[3],所以[3]不可能是中位数。

最后一次比较只要在[2]和[4]中比较就行了。

谁大,谁就是中位数。

 

0 条回应