现在的位置: 首页 > 综合 > 正文

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

2014年02月08日 ⁄ 综合 ⁄ 共 2975字 ⁄ 字号 评论关闭

0. 前言:“要学好C语言,绝非熟悉语法和语义这么简单”不太正确,语言是语言,算法是算法,不能说算法厉害了才算把语言学好了(作者说如果把”学好“改成”用好“就更明白了)。

“学习C语言的过程是痛苦的”,有点吓人,其实C语言是很好学的……也许作者逻辑思维太厉害,所以对语法这种语文类型的内容不太敏感(作者对此回复说对语言并不是不敏感,学习C语言的过程是痛苦的是学生们的感慨,只是照搬)。
1. P8: a^=b^=a^=b,Undefined。
2. 31页2-2说ABC满足ABC=A^2+B^2+C^2,不应该是2而应该是3。
3. P23: 见man 3 clock:
RETURN VALUE
The value returned is the CPU time used so far as a clock_t; to get the
number of seconds used, divide by CLOCKS_PER_SEC. If the processor
time used is not available or its value cannot be represented, the
function returns the value (clock_t) -1.
在Linux中等待输入数据的时间是不被计算的,由于我当时发现Linux下运行时间结果总是为0,还以为是clock()出了问题,因此有了此帖:http://topic.csdn.net/u/20100827/07/1cb16cb8-b776-4e4c-8e30-d56795254da8.html?10223
4. P52:对于hypot,查看man page:
CONFORMING TO
C99, POSIX.1-2001. The variant returning double also conforms to SVr4,
4.3BSD.
不知道为什么作者说这个函数不是ANSI C的(作者回复说明明是标准函数,但在一些OJ的编译器上确实没有这个函数并且曾经有选手因此杯具过)。
5. p71:“这个语法不是ANSI C的”这句有误,这个语法在C99中已经被标准化了(作者对此回复说他没有打算在书中涉及C99)。
    另外周期串这道题的代码中j++应该改为i++。
6. p77:那个“冒泡排序”是不带辅助变量的选择排序= =!想知道冒泡排序是何物请到百度搜索学习,另外还有个优化,每一趟之前sorted = 1,如果一趟下来一次交换都没有那就sorted保持不变,退出循环,有一次交换就改成0,这样就可以避免排序完了还继续检查的情况(这里只是提一下,作者说竞赛中还是别优化了,毕竟用它就是因为好写)。
7. p81:作者给的分析和程序有误,如果输入3,那结果是1/2而不是样例的2/1,因为作者没有考虑到正数(三声)和倒数的问题,而是一概处理为倒数,而如果k是偶数,那输出应该反过来。我就想他那个公式怎么那么神奇,竟然能同时兼顾两种情况,后来编译运行了他的代码才发现程序有问题。这里给出个人修正后的代码:

if (s >= n) {
    k % 2 ? printf("%d/%d\n", s-n+1, k-s+n) : 
         printf("%d/%d\n", k-s+n, s-n+1);
    break;
}

82页的程序也同样有此问题,改法相同。
8. 83页的a^m*a^n=a^(mn)不正确。
9. 95页作者说:“用%c会读到这个回车换行符,而只有%s才会跳过它”,这是不对的,只要在%c前面加个空格即可跳过:

scanf(" %c%d%d", &cmmnd, &x, &y);

完全不用费力地去用%s(作者说他也知道,不过故意使用笨方法,让学生们能快速理解并且避免在以后出错,因为他惊异于小朋友们能犯出简单语法错误的能力- -)。
10. 96页的小球问题配套的代码这行有问题:

for(int X = right[0]; X != n+1; X = right[X])

right[0]本来就是虚拟的小球,如果输入5 1[enter]B 3 5[enter],由于right[0]默认总是0,就会出现死循环,偶修改了多次,总会有各种各样的Bug,所以偶目前没什么好的解决方案。

11. 99页题目说如果该结点上的开关关闭,则往左走……而种种迹象表明明明是开关打开才往左走……

12. 101页作者说而一共可能有10000组数据,而99页题目上明明写着最多包含1000组数据……

13. 发现不是错误。

14. 109页中的dist在这里没有用处。

15. 115页下面的样例输出中的那个8应该改成12。

16. 116页中,根据双基回文数的题目分析,2<=b1,b2<=10应该改为:b1, b2∈[2, 10]。

以下不是错误,但需要提醒:

1. 在整本书中,作者都在printf()中对double使用%lf,这说明作者不懂C语言中的默认参数提升。因为float类型参数会被提升为double类型,所以单单有%f就是足够的,而C99考虑到了很多人并不了解这点,所以定义了与%f等价的%lf,所以你为了防止编译器不支持C99的这一特性,应该在printf()中使用%f而不是%lf。

2. int main()在C语言中并不属于函数原型,在C99中并认为是过时的,不建议使用。大多数情况下应该使用int main(void)。int main()在C++中则是没有问题的。
3. 作者没有对fopen(),fclose()这类函数做错误处理,在算法竞赛中虽然是可以但是在实际编程中往往是需要的。
4. 71页的那个j % i也许有点不好理解,如果你理解透了会发现改成j-i也是没问题的……
5. 79页的比较函数有点长,其实都可以写成这样的形式(作者说不敢写这么简短,本科生都得好长一段时间才能适应i++- -):

int cmp_char(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}

6. 82页中作者说为了避免浮点误差,用了一点技巧。我看了代码后发现作者的技巧就是利用floor函数来完成了ceil函数的功能,而且为了防止k多加了个1,还减去了1e-9,似乎即使不减数也应该不会多加1的,毕竟运算过程中开了根号,结果应该总是小的,不过作者懒得考虑了,为了保险(作者承认)就减了。而实际上把那行代码写成这样更加方便:

int k = (int)ceil(((sqrt(8.0*n+1)-1)/2));

7. 50页的3-4计算器不知道各位怎么写的,但最简单的读取输入的方式莫过于:

scanf("%d %c%d", &a, &sign, &b);

注意%c前面的空格是必不可少的,若是不知道为什么,请参考一本较好的C语言教程。
8. 54页的那个素数判定函数,书上写注意n不能太大,原因是i*i可能溢出。其实何必呢,直接i<=根n不就不容易溢出了。

9. 101页的一些程序上的小技巧是什么呢?就是这个(已通过作者验证):

for (int i = 0; i < D-1; i++) {
	k = 2*k+(!(I%2)); // 当I是偶数的时候才往右走(k=2*k+1)
	I = (I+1)/2; // 容易证明,对于除1以外的正整数来说,相邻的偶数和奇数加1除以2的结果都是一样的,所以在这里可以通用
}

10. 7.2.2中最开始的那个程序,其实还要把7.2.1的for (i = 1; i <= n; ++i)进行修改才能得到,当然在下面的代码中已经有所体现。

抱歉!评论已关闭.