1分治的三步契约
闭卷重建分治的三步契约的对象、状态、事件、不变量与一个失败反例。
算法设计与分析 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2归并排序
闭卷重建归并排序的对象、状态、事件、不变量与一个失败反例。
3二分查找与边界
闭卷重建二分查找与边界的对象、状态、事件、不变量与一个失败反例。
4逆序对计数
闭卷重建逆序对计数的对象、状态、事件、不变量与一个失败反例。
5最近点对思想
闭卷重建最近点对思想的对象、状态、事件、不变量与一个失败反例。
6大整数乘法与递推
闭卷重建大整数乘法与递推的对象、状态、事件、不变量与一个失败反例。
7分治综合实验
闭卷重建分治综合实验的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：对归并排序先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为归并排序实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析归并排序时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对分治的三步契约先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为分治的三步契约实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析分治的三步契约时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对逆序对计数先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为逆序对计数实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析逆序对计数时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对二分查找与边界先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为二分查找与边界实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析二分查找与边界时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对大整数乘法与递推先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为大整数乘法与递推实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析大整数乘法与递推时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对最近点对思想先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为最近点对思想实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析最近点对思想时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。
核心机制：对分治综合实验先写输入规格、输出规格和不变量，再给出算法、正确性论证、时空复杂度与边界反例；实验入口：为分治综合实验实现可运行参考程序，用手算小例、最小边界、反例和规模输入检查结果与增长率；边界：分析分治综合实验时不能只举成功例，必须声明前提、保存不变量，并区分正确、高效与对所有输入高效。