藍書劉汝佳算法競賽入門經(jīng)典勘誤

1、#算法競賽入門經(jīng)典勘誤 關于勘誤下面的勘誤很多來自于熱心讀者，再次向他們表示衷心的感謝！我并不清楚這些錯誤實際是在哪個版本中改正過來的，所以麻煩大家都看一下。 有發(fā)現(xiàn)新錯誤的歡迎大家在留言中指出，謝謝！ 一些一般性的問題運算符?已經(jīng)被廢棄，請用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=j; i+)應該為fo

2、r(k = i; k= 0 & i + j max) max = j*2+1; x = pi - j; y = pi + j; 6. 7. for (j = 0; i - j = 0 & i + j + 1 max) 11. max = j*2+2; x = pi - j; y = pi + j + 1; 12. 13. p53. 例題4-1. 組合數(shù). 輸入非負整數(shù)n和m，這里的n和m寫反了。應是“輸入非負整數(shù)m和n”。 p54. 舉例中的m和n也寫反了（真是個悲?。褻(20,1)=20。 p71. 周期串代碼的第8行，j+應為i+。 p72. 代碼的第7行，“return”改為“bre

3、ak”以和其他地方一致。 p81. k為奇數(shù)和偶數(shù)的時候，分子和分母的順序是不一樣的。正確代碼為： #include 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/%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,

4、 &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; 上述代碼已經(jīng)更新到代碼倉庫中。 p83. 應為am * an = am+n。 (感謝zr95.vip) p85. 兩張插圖下面的文字“順時針”、“逆時針”反了。 (感謝zr95.vip) p107. dfs函數(shù)有誤，應為： void dfs(int x, int y

5、) if(!matxy | visxy) return; / 曾經(jīng)訪問過這個格子，或者當前格子是白色 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); / 遞歸訪問周圍的八個格子 (感謝zhongying822) p124. 圖7-5最右邊的有兩個結點(3,1,*,*)，應該只有一個。下面一段第一行的“它只有18個結點”也應該為17個 (感謝zr95.vip, imxivid) p13

6、4. 代碼部分,vis36288應為vis362880。 （感謝lizhiwei） P142 表格下面第一行的最后，應該是2n (感謝imxivid） p152. 8.4.3【分析】情況2的“由貪心策略，k比j輕”應為“由貪心策略，j比k輕”。 (感謝zr95.vip) p159.【分析】一個n層數(shù)字三角形的完整路線有2n條。改為2n-1條。 （感謝imxivid） p160. 160頁的方法3 int d(int i, int j) .會產(chǎn)生一個重定義錯誤，因為函數(shù)和數(shù)組共用了一個標識符。隨便換一個數(shù)組名即可。 (感謝zhongying822) p171. 最上面，狀態(tài)轉(zhuǎn)移方程第二項應為f(

7、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

8、main() char nmaxn; 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 + ni - 0) % m); printf(%dn, ans); return 0; (感謝zr95.vip) p188. 中間的邊乘邊除，(n-i)/n前面應加上(double)強制類型轉(zhuǎn)換，不然結果會變成0. （感謝imxivid） p200. 情況2第2行，“則T+(u, v)”應為“則T+(u, v)”。 （感謝i

9、mxivid） p204. 中間代碼的下面第二行，因此可以用“”應為priority_queueint, vector, greater q。原文多寫了個vector。 （感謝imxivid） p205. 下面的程序的第一個注釋，應該是迭代n-1次。 （感謝imxivid） p207. 最大流問題上面，圖11-4(b)的方案并不是最優(yōu)的?？梢哉业皆鰪V路：從s到v2到v3到t，殘量分別是5(13)，4(9)，5(20)，由此可以得到一條由s到t的增廣路，所以最大的運送量應該是23而不是19 (感謝東北師大附中王玉。我還欠你一本書) p214. 第三行，Skenia應該是Skiena 小錯誤包括比

10、較明顯的筆誤或者排版問題。 p2.“實驗4”下方的“3+4”應為“3-4”。 (感謝zr95.vip) p4. 例1-1【分析】中“平面幾何”改成“幾何”比較妥當，因為底面積算是立體幾何中的概念 :) (感謝zr95.vip) p5. 頁腳. “不信的話用gcc-ansi編譯試試?！边@里的gcc和減號之間應有一個空格，即gcc -ansi p20. 程序2-4倒數(shù)第三行. printfA，多了一個A，應該是printf p70. 樣例輸出中的后雙引號格式有問題。 p107. 兩個程序的排版都有點小問題。上面的程序，倒數(shù)第三行的最后一個dfs應和它上面那一行的最后一個dfs對齊，這樣整齊一些；第

11、二個程序最后一個右花括號應該和上一個左花括號對齊。 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個兔子”應

12、為“第n個月的兔子”。 （感謝imxivid） p201. 圖11-3的標題“路經(jīng)”應為“路徑”。 （感謝imxivid） p207 最大流問題的第一段最后一行，“最多可以用9個物品”應為“最多可以有9個物品”。 （感謝imxivid） 其他p39頁提到sprintf和strchr，但是只講了sprintf。strchr的作用是在一個字符串中找一個子串，參見： Comment by zhongyin., Aug 25, 2011 1、160頁的方法3 int d(int i, int j) if (di?j? = 0) .這里會產(chǎn)生一個重定義錯誤，因為函數(shù)和數(shù)組共用了一個標識符 2、162頁，

13、dp函數(shù)里面有一個運算符是 ?= ?這種復合了條件表達式和賦值表達式的運算符，我沒有看過他的用法，也沒有成功使用過 3、107頁那個深搜算法，(x - 1, y)這個方向被搜索了兩次。 Comment by zr95., Oct 6, 2012 第2頁“實驗4”下方的“3+4”應為“3-4”。 第4頁例1-1【分析】中“平面幾何”應為“立體幾何”（或“幾何”）。 第39頁提到sprintf和strchr，但是只講了sprintf。 第83頁指數(shù)式am * an = am*n錯誤，應為am * an = am+n。 第85頁兩張插圖下面的文字“順時針”、“逆時針”反了。 第116頁7.1.4的【

14、分析】中“從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., Oc

15、t 6, 2012 第181頁例10-1的代碼沒有定義n和m。并且n是作為字符串讀取的，代碼第8行的ni似乎應為ni - 0。 Comment by project member rujia., Oct 6, 2012 謝謝zr95.vip的回復！第4頁的“底面積公式”實際上就是圓面積公式，說平面幾何也是合理的。不過嚴密起見，改成“幾何”確實更妥 :) 第124頁有些意外，我的原稿是用灰色格子表示攻擊范圍的，不知為何印刷出來卻沒有。其他問題我都同意。第181頁的兩處代碼錯誤很不應該，我得自我反省一下. Comment by imxi., Oct 19, 2012 P142 表格下面第一行的最后

16、，應該是2n。 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，會

17、接上次結束部分繼續(xù)讀。 P47 中間的代碼，if(si? = 1)應為if(si? = 1)。 P43 最后，判斷si.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., Oct 27, 2012 代碼在那里下

18、載？ Comment by imxi., Oct 29, 2012 P21 現(xiàn)在好像看明白了，作者好像是讓我們用double試一下兩次操作一起做。 Comment by imxi., Oct 29, 2012 P190 提示10-7上面一段，1,1,2,3,5,8這行的下一行，“第n個兔子”應為“第n個月的兔子”。 P180 最上面，例1最后一句，“即X=-6，Y=3是6x+15y=9”，“是”應為“時”。 P171 最上面，狀態(tài)轉(zhuǎn)移方程第二項應為f(k+1, j)。 P159 【分析】一個n層數(shù)字三角形的完整路線有2n條，好像應該是2(n-1)條。 P156 分兩步證明算法的正確性，我沒看懂

19、在說什么，不知道設的函數(shù)f(x)是什么意義。但是結論2第二行的“f(z)=f(x)+f(z)”似乎應為f(z)=f(x)+f(y)。 P152 乘船問題，情況2，改成j比k輕以后依然看不懂，哪個哪個不會超重，不知道到底怎么推出來的。 Comment by imxi., Oct 29, 2012 P178 下面的代碼，primec+ = i; 這句放到循環(huán)體內(nèi)好像只能統(tǒng)計出1m（根號n）范圍內(nèi)的素數(shù)吧 Comment by imxi., Oct 31, 2012 P211 “限于篇幅”上邊，“我們規(guī)定capv?u?=0”是怎么回事？雖然我沒大看懂，但是覺得好像應該是capv?v?=0。 P207

20、 最大流問題的第一段最后一行，“最多可以用9個物品”似乎應為“最多可以有9個物品”。 P205 下面的程序的第一個注釋，好像應該是迭代n-1次。 P204 中間代碼的下面第二行，因此可以用“”應為priority_queueint, vector, greater q。原文多寫了個vector。 P201 圖11-3的標題“路經(jīng)”應為“路徑”。 P200 情況2第2行，“則T+(u, v)”似乎應為“則T+(u, v)”。 P177的gcd函數(shù)我覺得寫成return b?gcd(b, a%b):a;更簡單，不知道對不對 終于把這本書看完了，感覺選這本書真是選對了，這是我看過的最明白好懂的OI書

21、！感謝作者！如果不是這本書，好多東西我自己在別處都看不懂！找出這些錯誤就當是報答作者吧為這本書做點貢獻我很快會把書正文部分所有例題和算法都寫成程序然后發(fā)出來！ Comment by imxi., Nov 2, 2012 P183 中間的楊輝三角遞推，Ci-1j-1和Ci-1j?會有負數(shù)下標的危險，外層循環(huán)應該為i=1，然后在外面加一句C0?0?=1。內(nèi)層雖然沒有錯誤，但是我覺得改成j = i比較好。 P173174最優(yōu)配對問題的代碼好像有誤。直接照著書上打進去，答案是不正確的。 Comment by imxi., Nov 2, 2012 P188中間的邊乘邊除，(n-i)/n前面應加上(double)強制類型轉(zhuǎn)換，不然結果會變成0. Comment by project member rujia., Nov 3, 2012 感謝imxivid！