#《算法竞赛入门经典》勘误

发布时间:2016-12-8 4:15:12 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"#《算法竞赛入门经典》勘误",主要涉及到#《算法竞赛入门经典》勘误方面的内容,对于#《算法竞赛入门经典》勘误感兴趣的同学可以参考一下。

转自http://code.google.com/p/aoapc-book/wiki/BeginningAlgorithmContestsErrata #《算法竞赛入门经典》勘误 关于勘误 下面的勘误很多来自于热心读者,再次向他们表示衷心的感谢!我并不清楚这些错误实际是在哪个版本中改正过来的,所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出,谢谢! 一些一般性的问题 运算符<?、>?已经被废弃,请用min、max代替(代码仓库中的代码已更新,g++ 4.6.2下编译通过) 重大错误 p24. 最后一行,“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 (感谢imxivid) p31. 习题2-2 水仙花数。定义应该是ABC=A3+B3+C3 (感谢chnln0526) p43. 最后,判断s[i..j]是否为回文串的方法也不难写出:int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) (感谢imxivid) p45. 第七行和第九行i-j+1应为i+j+1。修改后: 1. { 2. for (j = 0; i - j >= 0 && i + j < m; j++) 3. { 4. if (s[i - j] != s[i + j]) break; 5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7. for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. } p50. 单词pig的输入方式写错了,最后少了g的输入方式,即p1i3i1g1 (感谢yszhou4tech) p53. 例题4-1. 组合数. 输入非负整数n和m,这里的n和m写反了。应是“输入非负整数m和n”。 p54. 举例中的m和n也写反了(真是个悲剧),且C(20,1)=20。 p71. 《周期串》代码的第8行,j++应为i++。 p72. 代码的第7行,“return”改为“break”以和其他地方一致。 p74. 第9行,s[1]=1应为s[3]=1 (感谢metowolf88) p81. k为奇数和偶数的时候,分子和分母的顺序是不一样的。正确代码为: #include<stdio.h> int main() { int n; while(scanf("%d", &n) == 1) { int k = 1, s = 0; for(;;) { s += k; if(s >= n) { if(k % 2 == 1) printf("%d/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", k-s+n, s-n+1); break; } k++; } } return 0; } 以及: #include<stdio.h> #include<math.h> 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/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", 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(!mat[x][y] || vis[x][y]) return; // 曾经访问过这个格子,或者当前格子是白色 vis[x][y] = 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); // 递归访问周围的八个格子 } ([email protected]) p124. 图7-5最右边的有两个结点(3,1,*,*),应该只有一个。下面一段第一行的“它只有18个结点”也应该为17个 (感谢zr95.vip, imxivid) p134. 代码部分,vis[36288]应为vis[362880]。 (感谢lizhiwei) P142 表格下面第一行的最后,应该是2^n (感谢imxivid) p152. 8.4.3【分析】情况2改为: 情况2:i和另外一人k同船。由贪心策略,j是“可以和i一起坐船的人”中最重的,因此k比j轻。把j和k交换后k所在的船仍然不会超重(因为k比j轻),而i和j所在的船也不会超重(由贪心法过程),因此所得到的新解不会更差。 (感谢zr95.vip) p156 结论2第二行的“f(z)=f(x)+f(z)”改为f(z)=f(x)+f(y) (感谢imxivid) p159.【分析】一个n层数字三角形的完整路线有2n条。改为2n-1条。 (感谢imxivid) p160. 160页的方法3 int d(int i, int j) { .... 会产生一个重定义错误,因为函数和数组共用了一个标识符。随便换一个数组名即可。 ([email protected]) 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<cstdio> #include<cstring> const int maxn = 100 + 10; int main() { char n[maxn]; int m; scanf("%s%d", n, &m); int len = strlen(n); int ans = 0; for(int i = 0; i < len; i++) ans = (int)(((long long)ans * 10 + n[i] - '0') % m); printf("%d\n", 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<int, vector<int>, greater<int> >q。原文多写了个vector。 (感谢imxivid) p205. 下面的程序的第一个注释,应该是迭代n-1次。 (感谢imxivid) p207. 最大流问题上面,图11-4(b)的方案并不是最优的。改成:图11-4(b)展示了一种可能的方案... (感谢东北师大附中王玉。我还欠你一本书) 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</a>, 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</a>, 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); ... ... 似乎显然会导致无穷递归。 第187页的最后一段“不管是C36523还是36523都无法……”似乎应为“不管是P36523)还是……”。 Comment by zr95....@gmail.com</a>, Oct 6, 2012 第181页例10-1的代码没有定义n和m。并且n是作为字符串读取的,代码第8行的n[i]似乎应为n[i] - '0'。 Comment by project member rujia....@gmail.com</a>, Oct 6, 2012 谢谢zr95.vip的回复!第4页的“底面积公式”实际上就是圆面积公式,说平面几何也是合理的。不过严密起见,改成“几何”确实更妥 :) 第124页有些意外,我的原稿是用灰色格子表示攻击范围的,不知为何印刷出来却没有。其他问题我都同意。第181页的两处代码错误很不应该,我得自我反省一下... Comment by imxi...@gmail.com</a>, Oct 19, 2012 P142 表格下面第一行的最后,应该是2^n。 P124 解答树修改以后,下面一段第一行的“它只有18个结点”也应该为17个。 P72 代码的第7行,“return”似乎改为“break”更好。 P71 代码的第8行,j++应为i++。 P70 样例输出的最后一个双引号格式似乎应和'not to be'后面的双引号一样。 P54 第二行,“很不幸……-19.手算不难得到……是1。”很不幸,这两个结果我都没能得到。C(N,M)=C(1,20)显然无意义。 P48 最后一行,sscanf、sprintf和sstream的功能似乎不是很相似。用sscanf读字符串时,(多条语句)每用一个sscanf都会从字符串开头开始读取,但用sstream,会接上次结束部分继续读。 P47 中间的代码,if(si? == 1)应为if(si? == '1')。 P43 最后,判断s[i..j]是否为回文串的方法也不难写出: int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) P24 最后一行,“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 P21 小注:“如果将两次操作一起做,可以在一定程度上缓解这个问题。”我试了一下,似乎对缓解问题没有任何效果。不知道作者在这里说的是什么意思。 Comment by Tankc...@gmail.com</a>, Oct 27, 2012 代码在那里下载? Comment by imxi...@gmail.com</a>, Oct 29, 2012 P21 现在好像看明白了,作者好像是让我们用double试一下两次操作一起做。 Comment by imxi...@gmail.com</a>, Oct 29, 2012 P190 提示10-7上面一段,1,1,2,3,5,8……这行的下一行,“第n个兔子”应为“第n个月的兔子”。 P180 最上面,例1最后一句,“即X=-6,Y=3是6x+15y=9”,“是”应为“时”。 P171 最上面,状态转移方程第二项应为f(k+1, j)。 P159 【分析】一个n层数字三角形的完整路线有2n条,好像应该是2(n-1)条。 P156 分两步证明算法的正确性,我没看懂在说什么,不知道设的函数f(x)是什么意义。但是结论2第二行的“f(z)=f(x)+f(z)”似乎应为f(z)=f(x)+f(y)。 P152 乘船问题,情况2,改成j比k轻以后依然看不懂,哪个哪个不会超重,不知道到底怎么推出来的。 Comment by imxi...@gmail.com</a>, Oct 29, 2012 P178 下面的代码,prime[c++] = i; 这句放到循环体内好像只能统计出1~m(根号n)范围内的素数吧…… Comment by imxi...@gmail.com</a>, Oct 31, 2012 P211 “限于篇幅”上边,“我们规定capv?u?=0”是怎么回事?虽然我没大看懂,但是觉得好像应该是capv?v?=0。 P207 最大流问题的第一段最后一行,“最多可以用9个物品”似乎应为“最多可以有9个物品”。 P205 下面的程序的第一个注释,好像应该是迭代n-1次。 P204 中间代码的下面第二行,因此可以用“……”应为priority_queue<int, vector<int>, greater<int> >q。原文多写了个vector。 P201 图11-3的标题“路经”应为“路径”。 P200 情况2第2行,“则T'+(u, v)”似乎应为“则T+(u, v)”。 P177的gcd函数我觉得写成return b?gcd(b, a%b):a;更简单,不知道对不对…… 终于把这本书看完了,感觉选这本书真是选对了,这是我看过的最明白好懂的OI书!感谢作者!如果不是这本书,好多东西我自己在别处都看不懂!找出这些错误就当是报答作者吧~为这本书做点贡献……我很快会把书正文部分所有例题和算法都写成程序然后发出来! Comment by imxi...@gmail.com</a>, Nov 2, 2012 P183 中间的杨辉三角递推,C[i-1][j-1]和C[i-1]j?会有负数下标的危险,外层循环应该为i=1,然后在外面加一句C0?0?=1。内层虽然没有错误,但是我觉得改成j <= i比较好。 P173~174最优配对问题的代码好像有误。直接照着书上打进去,答案是不正确的。 Comment by imxi...@gmail.com</a>, Nov 2, 2012 P188中间的边乘边除,(n-i)/n前面应加上(double)强制类型转换,不然结果会变成0. Comment by project member rujia....@gmail.com</a>, Nov 3, 2012 感谢imxivid!你说的绝大多数都是对的,我会尽快写在勘误中。有几个代码错误之前已经在googlecode中改正了,但是忘记在勘误里写了,呵呵。其他几个需要说明的:P54是m和n写反了,P48的sscanf/sstream的用法以及几个贪心问题的证明我稍后详细叙述;P47是故意的,也就是“实验2”里会发现这个函数得不到正确的结果,然后“改正”。P21就是说的用double。P211没问题。cap[v][u]=0是为了允许反向增广 Comment by Tankc...@gmail.com</a>, Nov 4, 2012 训练指南 p80 Uva 11627 翻译错误 输出不是数量 应是速度能通过的速度最大的滑雪板的速度 (坑死了) Comment by project member rujia....@gmail.com</a>, Nov 4, 2012 回复Tankchen:啊,真是抱歉。另外请在训练指南的相应章节后汇报勘误哈,这里是《入门经典》的勘误页。还有,下载代码的方法是使用git。我会不定期打包放在downloads里面的,目前还没有... Comment by chong97...@gmail.com</a>, Dec 13, 2012 p77 貌似把冒泡排序和选择排序弄错了吧? Comment by tplee...@gmail.com</a>, Jan 23, 2013 P38 最后一行 可以用scanf("%s",si?)读取第i个字符串 这里有问题吧,什么意思啊? Comment by chnln0...@gmail.com</a>, Feb 22, 2013 P31 习题2-2 水仙花数 若3位数ABC满足ABC=A2+B2+C2 应为ABC=A3+B3+C3 Comment by yszhou4t...@gmail.com</a>, Mar 11, 2013 p50. 单词pig的输入方式写错了 Comment by metowol...@gmail.com, Aug 2, 2013 P74. 第9行:【原文】s0?=4,s1?=3,s2?=2,s1?=1;【应该为】s0?=4,s1?=3,s2?=2,s3?=1; Comment by wtx20074...@gmail.com, Dec 3, 2013 p186.图中以及下面的说明中,以b开头的字典序小于caba的串的个数应为f(cba) Comment by project member rujia....@gmail.com</a>, Dec 16, 2013 回复wtx20074587:以b开头的所有串都满足条件,所以是caa三个字母的全排列。你觉得呢? Comment by project member rujia....@gmail.com</a>, Dec 16, 2013 回复metowolf88:的确如此。谢谢! Comment by project member rujia....@gmail.com</a>, Dec 16, 2013 回复yszhou4tech:的确如此。谢谢! Comment by project member rujia....@gmail.com</a>, Dec 16, 2013 回复chnln0526:的确如此。谢谢! Comment by project member rujia....@gmail.com</a>, Dec 16, 2013 回复tplee923:注意声明的是一个二维字符数组,即字符串数组,所以可以这样输入。你发现什么问题了? Comment by chu.p...@gmail.com</a>, Feb 6, 2014 P118 7.2.2, 应为i是从1到n, 如果用数组P来作为输入 应该改为Aj?==P[i-1] 和 Acur?=P[i-1]. 或者i应该从0到n-1. Comment by chu.p...@gmail.com</a>, Feb 12 (6 days ago) 130页 图7-7 的注解 最后一个state应该是(4,2,0) 而不是 (4,2,1). Comment by chu.p...@gmail.com</a>, Today (10 hours ago) P171 最上面的状态转移方程 应该是min 而不是max吧? 还有如其他人指出的第二项应该是(k+1, j) ► Sign in to add a comment

上一篇:Qt for Android on Mac OSX部署
下一篇:基础练习 十进制转十六进制

相关文章

相关评论