第1章 概览 1 1.1 算法设计的若干通用策略 1 1.1.1 穷举搜索 2 1.1.2 回溯法 3 1.1.3 减而治之 6 1.1.4 分而治之 7 1.1.5 变而治之 8 1.1.6 贪心法 14 1.1.7 迭代改进 15 1.1.8 动态规划 18 1.2 分析技术 19 1.2.1 几个求和公式，兼论算法效率 20 1.2.2 非递归算法分析 21 1.2.3 递归算法分析 23 1.2.4 不变量 25 第2章 谜题 29 2.1 简单谜题 29 2.2 中等难度谜题 41 2.3 较难谜题 55 第3章 提示 67 第4章 答案 78 算法谜题列表 第1章　概览 1 第2章　谜题 29 1．狼羊菜过河 29 2．手套选择 29 3．矩形切割 29 4．士兵摆渡 29 5．行列变换 30 6．数数的手指 30 7．夜过吊桥 30 8．拼图问题 30 9．心算求和 30 10．硬币中的假币 31 11．假币堆问题 31 12．平铺多米诺问题 31 13．被堵塞的路径 31 14．复原国际象棋棋盘 31 15．三格骨牌平铺问题 32 16．煎饼制作 32 17．国王的走位 32 18．骑士的征途 32 19．页码计数 32 20．寻找最大和 33 21．正方形的拆分 33 22．球队排名 33 23．波兰国旗问题 33 24．国际象棋棋盘着色问题 33 25．科学家在世的最好时代 34 26．寻找图灵 34 27．Icosian游戏 35 28．一笔画 35 29．重温幻方 35 30．棍子切割 35 31．三堆牌魔术 35 32．单淘汰赛 36 33．真伪幻方 36 34．星星的硬币 36 35．三个水壶 37 36．有限的差异 37 37．2n筹码问题 37 38．四格骨牌平铺问题 37 39．方格遍历 38 40．四个调换的骑士 38 41．灯之圈 38 42．狼羊菜过河问题的另一个版本 39 43．数字填充 39 44．孰轻孰重 39 45．骑士的捷径 39 46．三色排列 39 47．展览规划 39 48．麦乐鸡数字 40 49．传教士与食人族 40 50．最后一个球 40 51．缺失的数字 41 52．数三角形 41 53．弹簧秤甄别假币 41 54．矩形切割 41 55．里程表之谜 42 56．新兵列队 42 57．斐波那契的兔子问题 42 58．二维排序 42 59．双色帽子 42 60．硬币三角形变正方形 43 61．对角线上的棋子 43 62．硬币收集 43 63．加减归零 43 64．构建八边形 43 65．猜密码 44 66．留下的数字 44 67．均分减少 44 68．数位求和 44 69．扇区上的筹码 44 70．跳跃成对I 44 71．标记方格I 45 72．标记方格II 45 73．逮公鸡 45 74．地点选择 46 75．加油站检查问题 46 76．高效的车 46 77．模式搜索 47 78．直三格板平铺 47 79．储物柜门 47 80．王子之旅 47 81．再论名人问题 47 82．头像朝上 48 83．受限的汉诺塔 48 84．煎饼排序 48 85．散布谣言I 49 86．散布谣言II 49 87．倒置的玻璃杯 49 88．蟾蜍和青蛙 49 89．纸牌交换 49 90．座位重排 50 91．水平的和垂直的多米诺骨牌 50 92．梯形平铺 50 93．击中战舰 51 94．搜索排好序的表 51 95．最大-最小称重 51 96．平铺楼梯区域 51 97．Topswops游戏 51 98．回文计数 52 99．倒序排列 52 100．骑士的走位 52 101．房间喷漆 52 102．猴子和椰子 52 103．跳到另一边 53 104．堆分割 53 105．MU问题 53 106．开灯 54 107．狐狸和野兔 54 108．最长路径 54 109．双n多米诺骨牌 54 110．变色龙 55 111．反转硬币三角形阵 55 112．再次讨论多米诺平铺问题 55 113．拿走硬币 55 114．划线过点 56 115．Bachet的砝码 56 116．轮空计数 56 117．一维跳棋 57 118．六骑士 57 119．有色三格板平铺 57 120．硬币分发机 57 121．超级蛋测试 58 122．议会和解 58 123．荷兰国旗问题 58 124．切割链条 58 125．对5个物品称重7次来排序 58 126．公平切分蛋糕 58 127．骑士之旅 58 128．安全开关 59 129．Reve之谜 59 130．毒酒 59 131．Tait筹码谜题 59 132．跳棋军队 60 133．生命的游戏 60 134．点着色 61 135．不同的配对 61 136．抓捕间谍 61 137．跳跃成对Ⅱ 62 138．糖果分享 62 139．亚瑟国王的圆桌 62 140．重温n皇后问题 62 141．约瑟夫问题 63 142．12枚硬币 63 143．被感染的棋盘 63 144．拆除方格 63 145．十五谜题 63 146．击中移动目标 64 147．编号的帽子 64 148．自由硬币 64 149．卵石扩张 65 150．保加利亚接龙 66 第3章 提示 67 1．狼羊菜过河 67 2．手套选择 67 3．矩形切割 67 4．士兵摆渡 67 5．行列变换 67 6．数数的手指 67 7．夜过吊桥 67 8．拼图问题 67 9．心算求和 67 10．硬币中的假币 67 11．假币堆问题 67 12．平铺多米诺问题 67 13．被堵塞的路径 67 14．复原国际象棋棋盘 68 15．三格骨牌平铺问题 68 16．煎饼制作 68 17．国王的走位 68 18．骑士的征途 68 19．页码计数 68 20．寻找最大和 68 21．正方形的拆分 68 22．球队排名 68 23．波兰国旗问题 68 24．国际象棋棋盘着色问题 68 25．科学家在世的最好时代 68 26．寻找图灵 68 27．Icosian游戏 68 28．一笔画 68 29．重温幻方 68 30．棍子切割 68 31．三堆牌魔术 69 32．单淘汰赛 69 33．真伪幻方 69 34．星星的硬币 69 35．三个水壶 69 36．有限的差异 69 37．2n筹码问题 69 38．四格骨牌 69 39．方格遍历 69 40．四个调换的骑士 69 41．灯之圈 69 42．狼羊菜过河问题的另一个版本 69 43．数字填充 69 44．孰轻孰重 69 45．骑士的捷径 69 46．三色排列 69 47．展览规划 69 48．麦乐鸡数字 70 49．传教士与食人族 70 50．最后一个球 70 51．缺失的数字 70 52．数三角形 70 53．弹簧秤甄别假币 70 54．矩形切割 70 55．里程表之谜 70 56．新兵列队 70 57．斐波那契的兔子问题 70 58．二维排序 70 59．双色帽子 70 60．硬币三角形变矩形 70 61．对角线上的棋子 70 62．硬币收集 71 63．加减归零 71 64．构建八边形 71 65．猜密码 71 66．留下的数字 71 67．均分减少 71 68．数位求和 71 69．扇区上的筹码 71 70．跳跃成对I 71 71．标记方格I 71 72．标记方格II 71 73．逮公鸡 71 74．地点选择 71 75．加油站检查问题 71 76．高效的车 71 77．模式搜索 71 78．直三格板平铺 72 79．储物柜门 72 80．王子之旅 72 81．再论名人问题 72 82．头像朝上 72 83．受限的汉诺塔 72 84．煎饼排序 72 85．散布谣言I 72 86．散布谣言II 72 87．倒置的玻璃杯 72 88．蟾蜍和青蛙 72 89．纸牌交换 72 90．座位重排 72 91．水平的和垂直的多米诺骨牌 72 92．梯形平铺 72 93．击中战舰 73 94．搜索排好序的列表 73 95．最大-最小称重 73 96．平铺楼梯区域 73 97．Topswops游戏 73 98．回文计数 73 99．倒序排列 73 100．骑士的走位 73 101．房间喷漆 73 102．猴子和椰子 73 103．跳到另一边 73 104．堆分割 73 105．MU问题 73 106．开灯 73 107．狐狸和野兔 73 108．最长路径 73 109．双n多米诺骨牌 73 110．变色龙 73 111．反转硬币三角形阵 74 112．再次讨论多米诺平铺问题 74 113．拿走硬币 74 114．划线过点 74 115．Bachet的砝码 74 116．轮空计数 74 117．一维跳棋 74 118．六骑士 74 119．有色三格板平铺 74 120．硬币分发机 74 121．超级蛋测试 74 122．议会和解 74 123．荷兰国旗问题 74 124．切割链条 75 125．对5个物品称重7次来排序 75 126．公平切分蛋糕 75 127．骑士之旅 75 128．安全开关 75 129．Reve之谜 75 130．毒酒 75 131．Tait筹码谜题 75 132．跳棋军队 75 133．生命的游戏 75 134．点着色 75 135．不同的配对 76 136．抓捕间谍 76 137．跳跃成对Ⅱ76 138．糖果分享 76 139．亚瑟国王的圆桌 76 140．重温n皇后问题 76 141．约瑟夫问题 76 142．12枚硬币 76 143．被感染的棋盘 76 144．拆除方格 76 145．十五谜题 76 146．击中移动目标 76 147．编号的帽子 76 148．自由硬币 77 149．卵石扩张 77 150．保加利亚接龙 77 第4章 答案 78 1．狼羊菜过河 78 2．手套选择 79 3．矩形切割 79 4．士兵摆渡 80 5．行列变换 80 6．数数的手指 81 7．夜过吊桥 82 8．拼图问题 83 9．心算求和 83 10．硬币中的假币 84 11．假币堆问题 85 12．平铺多米诺问题 85 13．被堵塞的路径 86 14．复原国际象棋棋盘 86 15．三格骨牌平铺问题 87 16．煎饼制作 88 17．国王的走位 88 18．骑士的征途 89 19．页码计数 90 20．寻找最大和 90 21．正方形的拆分 91 22．球队排名 92 23．波兰国旗问题 92 24．国际象棋棋盘着色问题 93 25．科学家在世的最好时代 94 26．寻找图灵 94 27．Icosian游戏 95 28．一笔画 95 29．重温幻方 97 30．棍子切割 99 31．三堆牌魔术 99 32．单淘汰赛 100 33．真伪幻方 101 34．星星的硬币 102 35．三个水壶 103 36．有限的差异 104 37．2n筹码问题 105 38．四格骨牌平铺问题 106 39．方格遍历 108 40．四个调换的骑士 108 41．灯之圈 109 42．狼羊菜过河问题的 另一个版本 110 43．数字填充 111 44．孰轻孰重 111 45．骑士的捷径 112 46．三色排列 112 47．展览规划 113 48．麦乐鸡数字 114 49．传教士与食人族 115 50．最后一个球 116 51．缺失的数字 116 52．数三角形 117 53．弹簧秤甄别假币 118 54．矩形切割 118 55．里程表之谜 119 56．新兵列队 120 57．斐波那契的兔子问题 120 58．二维排序 121 59．双色帽子 122 60．硬币三角形变正方形 123 61．对角线上的棋子 125 62．硬币收集 126 63．加减归零 127 64．构建八边形 128 65．猜密码 129 66．留下的数字 130 67．均分减少 130 68．数位求和 131 69．扇区上的筹码 132 70．跳跃成对I 133 71．标记方格I 133 72．标记方格II 134 73．逮公鸡 135 74．地点选择 137 75．加油站检查问题 138 76．高效的车 139 77．模式搜索 140 78．直三格板平铺 141 79．储物柜门 141 80．王子之旅 142 81．再论名人问题 143 82．头像朝上 144 83．受限的汉诺塔 144 84．煎饼排序 147 85．散布谣言I 148 86．散布谣言II 149 87．倒置的玻璃杯 150 88．蟾蜍和青蛙 150 89．纸牌交换 152 90．座位重排 153 91．水平的和垂直的多米诺骨牌 153 92．梯形平铺 154 93．击中战舰 157 94．搜索排好序的表 157 95．最大-最小称重 158 96．平铺楼梯区域 159 97．Topswops游戏 161 98．回文计数 162 99．倒序排列 163 100．骑士的走位 164 101．房间喷漆 165 102．猴子和椰子 166 103．跳到另一边 167 104．堆分割 167 105．MU谜题 169 106．开灯 169 107．狐狸和野兔 171 108．最长路径 172 109．双n多米诺骨牌 173 110．变色龙 174 111．反转硬币三角形阵 174 112．再次讨论多米诺平铺问题 177 113．拿走硬币 178 114．划线过点 179 115．Bachet的砝码 179 116．轮空计数 182 117．一维跳棋 183 第4118．六骑士 184 119．有色三格板平铺 186 120．硬币分配机 187 121．超级蛋测试 188 122．议会和解 189 123．荷兰国旗问题 190 124．切割链条 191 125．对5个物品称重7次来排序 192 126．公平切分蛋糕 194 127．骑士之旅 194 128．安全开关 196 129．Reve之谜 197 130．毒酒 199 131．Tait筹码谜题 200 132．跳棋军队 202 133．生命的游戏 204 134．点着色 205 135．不同的配对 206 136．抓捕间谍 207 137．跳跃成对Ⅱ 209 138．糖果分享 210 139．亚瑟国王的圆桌 211 140．重温n皇后问题 212 141．约瑟夫问题 214 142．12枚硬币 215 143．被感染的棋盘 217 144．拆除方格 218 145．十五谜题 220 146．击中移动目标 221 147．编号的帽子 223 148．自由硬币 223 149．卵石扩张 226 150．保加利亚接龙 228