题目

Problem

The numbers below are to be packed into bins of size 60.

35, 17, 10, 7, 28, 23, 41, 15, 20, 29

(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60.

(3)

(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

(4)

(3)

The ten distinct numbers below are to be sorted into descending order.

20, 24, 17, 26, 8, 15, x, y, 19, 12

A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.

After the second complete pass the list is

24, 26, 20, 17, 15, y, 19, 12, x, 8

(d) Find the constraints on the values of x and y.

(3)

(Total 13 marks)

题目中文翻译

以下数字需要装入容量为 60 的箱子中。

35、17、10、7、28、23、41、15、20、29

(a) 使用首次适应装箱算法确定上述数字如何装入容量为 60 的箱子中。

(b) 将数字列表按降序排列。使用快速排序获得排序后的列表。你应该显示每趟的结果并清楚地标出你的基准元素。

以下十个不同的数字需要按降序排列。

20、24、17、26、8、15、x、y、19、12

使用冒泡排序从列表左端开始获得排序后的列表。

第二趟完整遍历后列表为

24、26、20、17、15、y、19、12、x、8

(d) 求 x 和 y 的取值范围。

解答

(a)

解法一

思路

展开

按原顺序逐个处理数字。每个数字都从第一个箱子开始检查，放入第一个剩余容量足够的箱子；若所有已有箱子都放不下，才开启新箱子。

答题过程

展开

Applying first fit in the given order gives

Bin	Contents	Total
1	$35,17,7$	$59$
2	$10,28,15$	$53$
3	$23,20$	$43$
4	$41$	$41$
5	$29$	$29$

(b)

解法一

思路

展开

采用官方评分资料中的 middle-right 选取方式：每个子列表取中间偏右的元素为 pivot，把较大元素放在 pivot 左侧、较小元素放在右侧，并同时处理各个尚未排好的子列表。

答题过程

展开

Using middle-right pivots:

Pass	Pivot(s)	Result
1	$23$	$35,28,41,29\mid\mathbf{23}\mid17,10,7,15,20$
2	$41,7$	$\mathbf{41}\mid35,28,29\mid23\mid17,10,15,20\mid\mathbf{7}$
3	$28,15$	$41,35,29\mid\mathbf{28}\mid23\mid17,20\mid\mathbf{15}\mid10,7$
4	$29,20,(10)$	$41,35,29,28,23,20,17,15,10,7$

Hence the completed descending list is

\boxed{41,35,29,28,23,20,17,15,10,7}.

解法二

思路

展开

也可采用官方接受的 middle-left 选取方式。算法原则不变，只是偶数长度子列表改取中间偏左的元素，因此各趟 pivot 和中间列表不同，但最终降序列表相同。

答题过程

展开

Using middle-left pivots:

Pass	Pivot(s)	Result
1	$28$	$35,41,29\mid\mathbf{28}\mid17,10,7,23,15,20$
2	$41,7$	$\mathbf{41}\mid35,29\mid28\mid17,10,23,15,20\mid\mathbf{7}$
3	$35,23$	$41,\mathbf{35},29,28,\mathbf{23},17,10,15,20,7$
4	$(29),10$	$41,35,29,28,23,17,15,20,\mathbf{10},7$
5	$15$	$41,35,29,28,23,17,20,\mathbf{15},10,7$
6	$17$	$41,35,29,28,23,20,\mathbf{17},15,10,7$

Therefore the sort is complete with

\boxed{41,35,29,28,23,20,17,15,10,7}.

(c)

解法一

思路

展开

使用 (b) 的严格降序列表，再按 first fit 逐项扫描已有箱子。前三组较大数字分别配成 $41+17$ 、 $35+23$ 、 $29+28$ ，其余数字依次进入第四个箱子。

答题过程

展开

Applying first fit to the decreasing list gives

Bin	Contents	Total
1	$41,17$	$58$
2	$35,23$	$58$
3	$29,28$	$57$
4	$20,15,10,7$	$52$

(d)

解法一

思路

展开

降序冒泡排序从左端开始比较，会在每一趟把当前最小值逐步推到右端。第一趟后 8 位于末端，因此 $x>8$ ；第二趟后 $x$ 位于倒数第二位、12 在其左侧，因此 $x<12$ 。要让第二趟比较到 $x,y$ 时交换二者，并使 $x$ 继续向右移动，还必须有 $y>x$ 。

答题过程

展开

After the first pass, $8$ is the smallest value and is moved to the final position. Since the values are distinct,

x>8.

After the second pass, $x$ is the second-smallest value and lies immediately to the right of $12$ , so

x<12.

During this pass, $x$ must also interchange with $y$ , which requires

y>x.

Therefore the required constraints are

\boxed{8<x<12\quad\text{and}\quad y>x}.

IAL 2020 Jan D1 Q4

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

解法二

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程