東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年8月実施 専門科目 問題2
Author
祭音Myyura, zephyr
Description
C言語で書かれた以下のプログラムは整数配列 a の a[i] から a[j-1] までを昇順に整列する関数 mysort(a, i, j) を定義している (i < j)。
プログラム中の関数 multifrac(k, l, m) は k, l, m が正の整数であるときに
int multifrac(int k, int l, int m) {
return (k * l + (m-1))/m;
}
void compare_swap(int *p, int *q) {
if (*p > *q) {
int tmp = *p;
*p = *q;
*q = tmp;
}
}
void mysort(int a[], int i, int j) {
int k = j - i;
if (k < 4) {
[ 空欄 X ]
} else {
mysort(a, i, i + multifrac(k, x, w));
mysort(a, j - multifrac(k, y, w), j);
mysort(a, i, i + multifrac(k, z, w));
}
}
以下の問いに答えよ。
(1) (w, x, y, z) が (4, 3, 3, 3) である場合、空欄 X に入れるべき適切なコードを考えよ。 ただし、compare_swap 以外の関数呼び出しは不可とする。 なお、コードは複数行にわたってもよい。
(2) mysort(a, 0, n) が呼び出された時にコード断片 X が実行される回数の合計を
(3) (w, x, y, z) が (4, 2, 3, 3), (4, 3, 2, 3), (4, 3, 3, 2), (4, 2, 3, 2) である場合のそれぞれについて、mysort 関数が常に正しく動作するか否かを答えよ。
(4) mysort が常に正しく動作するために w, x, y, z が満たすべき必要十分条件を答えよ。
Kai
(1)
if (k == 3) {
compare_swap(&a[i], &a[i+1]);
compare_swap(&a[i+1], &a[i+2]);
compare_swap(&a[i], &a[i+1]);
} else if (k == 2) {
compare_swap(&a[i], &a[i+1]);
} else {
// Do nothing if k == 1, as a single element is already sorted.
}
(2)
When
Hence,
(3)
- Case (4, 2, 3, 3), (4, 3, 2, 3) and (4, 3, 3, 2) works
- (4, 2, 3, 2): not work
(4)
Key Insights
To guarantee that mysort always works correctly, the recursive calls must ensure that all elements in the array are covered and sorted properly. This requires:
- Coverage: The recursive calls must cover all elements in the array.
- Overlap: There must be sufficient overlap to ensure that elements are sorted correctly and their positions are fixed in each step.
- Problem Size Reduction: Each recursive call must reduce the problem size to ensure termination.
Critical Observation
After the first two recursive calls:
- The largest
elements must be correctly positioned at the end of the array.
Thus, for the third call to ensure full sorting:
- The third call must cover the remaining
elements.
Necessary and Sufficient Conditions
Based on our analysis of the multfrac function and the requirements for correct sorting, we can derive the following necessary and sufficient conditions:
- Problem Size Reduction Condition:
This condition, derived from the analysis of the multfrac function, guarantees that each recursive call reduces the problem size for any
- Overlap Condition for Third Call:
This ensures that the third call covers all elements not fully sorted by the first two calls.
- Integer Parameter Conditions:
These conditions ensure that all parameters are positive integers and that x, y, and z are strictly less than w.
Complete Necessary and Sufficient Condition
Combining all these conditions, the complete necessary and sufficient condition for mysort to work correctly is:
Explanation
- The first condition ensures proper coverage of the array by the first two recursive calls.
- The second condition, derived from the
multfracfunction analysis, guarantees problem size reduction in each recursive call, preventing infinite recursion. - The third condition ensures that the third call covers any elements not fully sorted by the first two calls.
- The fourth and fifth conditions ensure that all parameters are valid positive integers, with x, y, and z being strictly less than w.
These conditions together guarantee that mysort will correctly sort the array and terminate for any input size.
Knowledge
递归 分治算法 排序算法
解题技巧和信息
- 递归调用的正确性依赖于覆盖和重叠。每个递归调用必须覆盖整个数组段，确保所有元素最终被排序。
- [[时间复杂度#递归算法的时间复杂度 / Time Complexity of Recursive Algorithms|主定理（Master Theorem）]] 是解决递归关系的有力工具，特别是在分析算法复杂度时。
- 对于分治算法，理解各个部分的覆盖范围和重叠部分对于正确性和效率的保证非常重要。
重点词汇
recursive call 递归调用
coverage 覆盖
overlap 重叠
Master Theorem 主定理
complexity analysis 复杂度分析
参考资料
- Introduction to Algorithms, Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chap. 4.
- Algorithms, Fourth Edition, by Robert Sedgewick and Kevin Wayne, Chap. 2.