资源描述:
《蓝书刘汝佳算法竞赛入门经典勘误》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、#《算法竞赛入门经典》勘误关于勘误¶下面的勘误很多来自于热心读者,再次向他们表示衷心的感谢!我并不清楚这些错误实际是在哪个版本中改正过来的,所以麻烦大家都看一下。有发现新错误的欢迎大家在留言中指出,谢谢!一些一般性的问题¶运算符、>?已经被废弃,请用min、max代替(代码仓库中的代码已更新,g++4.6.2下编译通过)重大错误¶p24.最后一行,“然后让max=INF,而min=-INF”应该是“然后让max=-INF,而min=INF”。(感谢imxivid)p43.最后,判断s[i..j]是否为回文串的方法也不难写出:intok=1;for(k=i;i<=j;i++
2、)应该为for(k=i;k<=j;k++)(感谢imxivid)p45.第七行和第九行i-j+1应为i+j+1。修改后:1.{2.for(j=0;i-j>=0&&i+jmax){max=j*2+1;x=p[i-j];y=p[i+j];}6.}7.for(j=0;i-j>=0&&i+j+1max)11.{max=j*2+2;x=p[i-j];y=p[i+j+1];}12.}13.}p53
3、.例题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为奇数和偶数的时候,分子和分母的顺序是不一样的。正确代码为:#includeintmain(){intn;while(scanf("%d",&n)==1){intk=1,s=0;for(;;){s+=k;if(s>=n){if(k%2==1)printf("%d/%d
4、n",s-n+1,k-s+n);elseprintf("%d/%d",k-s+n,s-n+1);break;}k++;}}return0;}以及:#include#includeintmain(){intn;while(scanf("%d",&n)==1){intk=(int)floor((sqrt(8.0*n+1)-1)/2-1e-9)+1;ints=k*(k+1)/2;if(k%2==1)printf("%d/%d",s-n+1,k-s+n);elseprintf("%d/%d",k-s+n,s-n+1);}return0;}
5、上述代码已经更新到代码仓库中。p83.应为am*an=am+n。(感谢zr95.vip)p85.两张插图下面的文字“顺时针”、“逆时针”反了。(感谢zr95.vip)p107.dfs函数有误,应为:voiddfs(intx,inty){if(!mat[x][y]
6、
7、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)
8、;//递归访问周围的八个格子}(感谢zhongying822@163.com)p124.图7-5最右边的有两个结点(3,1,*,*),应该只有一个。下面一段第一行的“它只有18个结点”也应该为17个(感谢zr95.vip,imxivid)p134.代码部分,vis36288应为vis362880。(感谢lizhiwei)P142表格下面第一行的最后,应该是2^n(感谢imxivid)p152.8.4.3【分析】情况2的“由贪心策略,k比j轻”应为“由贪心策略,j比k轻”。(感谢zr95.vip)p159.【分析】一个n层数字三角形的完整路线有2n条。改为2n-1条。(感谢im
9、xivid)p160.160页的方法3intd(inti,intj){....会产生一个重定义错误,因为函数和数组共用了一个标识符。随便换一个数组名即可。(感谢zhongying822@163.com)p171.最上面,状态转移方程第二项应为f(k+1,j)。(感谢imxivid)p181.例10-2的代码段会导致无穷递归。改为:intpow_mod(inta,intn,intm){if(n==0)return1;intx=pow_mod(a,n/2,m);longlongans=(longlong)x