第1章 练习

证明

1. 用循环不变式证明插入排序的正确性（初始化、保持、终止）
2. 证明决策树下界 Ω(n lg n)：n! 个排列 ≤ 2^h 片叶 → h ≥ lg(n!) = Ω(n lg n)
3. 构造反例证明贪心硬币找换策略不可行：面额 {1, 3, 4}，找零6

实现

4. 实现六问诊断法的交互式程序：输入问题描述，逐步引导用户回答六个问题

建模

5. 将以下现实问题建模为组合对象（排列/子集/图/树/递归结构）：
   • 旅行商问题 → 排列
   • 子集和问题 → 子集
   • 课程排课 → 有向无环图

---

参考答案提示

1.3 反例：面额 {1, 3, 4}，找零6。贪心选4+1+1=3枚，最优3+3=2枚。