资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
#算法竞赛入门经典勘误 关于勘误下面的勘误很多来自于热心读者,再次向他们表示衷心的感谢!我并不清楚这些错误实际是在哪个版本中改正过来的,所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出,谢谢! 一些一般性的问题运算符?已经被废弃,请用 min、max 代替(代码仓库中的代码已更新,g+ 4.6.2 下编译通过) 重大错误p24. 最后一行, “然后让 max=INF,而 min=-INF”应该是“然后让 max=-INF, 而min=INF”。 (感谢 imxivid) p43. 最后,判断 si.j是否为回文串的方法也不难写出:int ok = 1; for(k = i; i= 0 j+) 3. 4. if (si - j != si + j) break; 5. if (j*2+1 max) max = j*2+1; x = pi - j; y = pi + j; 6. 7. for (j = 0; i - j = 0 j+) 8. 9. if (si - j != si + j + 1) break; 10. if (j*2+2 max) 11. max = j*2+2; x = pi - j; y = pi + j + 1; 12. 13. p53. 例题 4-1. 组合数. 输入非负整数 n 和 m,这里的 n 和 m 写反了。应是“输入非负整数 m 和 n”。 p54. 举例中的 m 和 n 也写反了(真是个悲剧) ,且 C(20,1)=20。 p71. 周期串代码的第 8 行,j+应为 i+。 p72. 代码的第 7 行, “return”改为“break”以和其他地方一致。 p81. k 为奇数和偶数的时候,分子和分母的顺序是不一样的。正确代码为: #include int main() int n; while(scanf(%d, for(;) s += k; if(s = n) if(k % 2 = 1) printf(%d/%dn, s-n+1, k-s+n); else printf(%d/%dn, k-s+n, s-n+1); break; k+; return 0; 以及: #include #include int main() int n; while(scanf(%d, &n) = 1) int k = (int)floor(sqrt(8.0*n+1)-1)/2 - 1e-9)+1; int s = k*(k+1)/2; if(k % 2 = 1) printf(%d/%dn, s-n+1, k-s+n); else printf(%d/%dn, k-s+n, s-n+1); return 0; 上述代码已经更新到代码仓库中。 p83. 应为 am * an = am+n。 (感谢 zr95.vip) p85. 两张插图下面的文字“顺时针” 、 “逆时针”反了。 (感谢 zr95.vip) p107. dfs 函数有误,应为: void dfs(int x, int y) if(!matxy | visxy) return; / 曾经访问过这个格子,或者当前格子是白色 visxy = 1; / 标记(x,y) 已访问过 dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x ,y-1); dfs(x ,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); / 递归访问周围的八个格子 (感谢 zhongying822163.com) p124. 图 7-5 最右边的有两个结点(3,1,*,*),应该只有一个。下面一段第一行的“它只有 18个结点”也应该为 17 个 (感谢 zr95.vip, imxivid) p134. 代码部分,vis36288 应为 vis362880。 (感谢 lizhiwei) P142 表格下面第一行的最后,应该是 2n (感谢 imxivid) p152. 8.4.3【分析】情况 2 的“由贪心策略,k 比 j 轻”应为“由贪心策略,j 比 k 轻” 。 (感谢 zr95.vip) p159.【分析】一个 n 层数字三角形的完整路线有 2n 条。改为 2n-1 条。 (感谢 imxivid) p160. 160 页的方法 3 int d(int i, int j) .会产生一个重定义错误,因为函数和数组共用了一个标识符。随便换一个数组名即可。 (感谢 zhongying822163.com) p171. 最上面,状态转移方程第二项应为 f(k+1, j)。 (感谢 imxivid) p181. 例 10-2 的代码段会导致无穷递归。改为: int pow_mod(int a, int n, int m) if(n = 0) return 1; int x = pow_mod(a, n/2, m); long long ans = (long long)x * x % m; if (n%2 = 1) ans = ans * a % m; return (int) ans; (感谢zr95.vip) p181. 例 10-1 的代码有误,改为: #include #include const int maxn = 100 + 10; int main() char nmaxn; int m; scanf(%s%d, n, i+) ans = (int)(long long)ans * 10 + ni - 0) % m); printf(%dn, ans); return 0; (感谢zr95.vip) p188. 中间的边乘边除,(n-i)/n 前面应加上(double)强制类型转换,不然结果会变成 0. (感谢 imxivid) p200. 情况 2 第 2 行, “则 T+(u, v)”应为“则 T+(u, v)”。 (感谢 imxivid) p204. 中间代码的下面第二行,因此可以用“”应为 priority_queue, greater q。原文多写了个 vector。 (感谢 imxivid) p205. 下面的程序的第一个注释,应该是迭代 n-1 次。 (感谢 imxivid) p207. 最大流问题上面,图 11-4(b)的方案并不是最优的。可以找到增广路:从 s 到 v2 到v3 到 t,残量分别是 5(13),4(9),5(20),由此可以得到一条由 s 到 t 的增广路,所以最大的运送量应该是 23 而不是 19 (感谢东北师大附中王玉。我还欠你一本书) p214. 第三行,Skenia 应该是 Skiena 小错误包括比较明显的笔误或者排版问题。 p2.“实验 4”下方的“3+4”应为“3-4 ”。 (感谢 zr95.vip) p4. 例 1-1【分析】中“平面几何”改成“几何”比较妥当,因为底面积算是立体几何中的概念 :) (感谢 zr95.vip) p5. 页脚. “不信的话用 gcc-ansi 编译试试。 ”这里的 gcc 和减号之间应有一个空格,即 gcc -ansi p20. 程序 2-4 倒数第三行. printfA,多了一个 A,应该是 printf p70. 样例输出中的后双引号格式有问题。 p107. 两个程序的排版都有点小问题。上面的程序,倒数第三行的最后一个 dfs 应和它上面那一行的最后一个 dfs 对齐,这样整齐一些;第二个程序最后一个右花括号 应该和上一个左花括号对齐。 p116. 7.1.4 的【分析】中“从 n+1 开始”应为“从 S+1 开始 ”。 (感谢 zr95.vip) p124. 插图 7-4 “a)皇后的攻击范围 ”没有画出范围。原稿中是有的,不知怎么没印出来. (感谢 zr95.vip) p180. 最上面,例 1 最后一句, “即 X=-6,Y=3 是 6x+15y=9”, “是”应为“时” 。 (感谢 imxivid) p187. 最后一段“不管是 C36523 还是 36523 都无法”应为“不管是 P36523 还是” 。(感谢 zr95.vip) p190. 提示 10-7 上面一段,1,1,2,3,5,8这行的下一行, “第 n 个兔子”应为“第 n 个月的兔子” 。 (感谢 imxivid) p201. 图 11-3 的标题“路经” 应为“路径” 。 (感谢 imxivid) p207 最大流问题的第一段最后一行, “最多可以用 9 个物品”应为“最多可以有 9 个物品” 。(感谢 imxivid) 其他p39 页提到 sprintf 和 strchr,但是只讲了 sprintf。strchr 的作用是在一个字符串中找一个子串,参见: http:/www.cplusplus.com/reference/clibrary/cstring/strchr/ Comment by zhongyin.163.com, Aug 25, 2011 1、160 页的方法 3 int d(int i, int j) if (di?j? = 0) .这里会产生一个重定义错误,因为函数和数组共用了一个标识符 2、162 页,dp 函数里面有一个运算符是 ?= ?这种复合了条件表达式和赋值表达式的运算符,我没有看过他的用法,也没有成功使用过 3、107 页那个深搜算法,(x - 1, y)这个方向被搜索了两次。 Comment by zr95.gmail.com, Oct 6, 2012 第 2 页“实验 4”下方的“3+4”应为“3-4 ”。 第 4 页例 1-1【分析】中“平面几何 ”应为“立体几何” (或“几何” ) 。 第 39 页提到 sprintf 和 strchr,但是只讲了 sprintf。 第 83 页指数式 am * an = am*n 错误,应为 am * an = am+n。 第 85 页两张插图下面的文字“顺时针” 、 “逆时针”反了。 第 116 页 7.1.4 的【分析】中“从 n+1 开始”应为“从 S+1 开始” 。 第 124 页插图 7-4 “a)皇后的攻击范围 ”没有画出范围? 第 124 页图 7-5 最右边的叶子结点 (3, 1, *, *)多了一个。 第 152 页 8.4.3【分析】情况 2 的“由贪心策略,k 比 j 轻”似乎应为“由贪心策略,j 比 k轻” 。 第 181 页例 10-2 的代码段 int pow_mod(int a, int n, int m) int x = pow_mod(a, n/2, m); .
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号