ACM/ICPC程序设计与分析

出版时间：2010-7  出版社：清华大学  作者：沈云付  页数：396  
Tag标签：无  

前言

　　国际大学生程序设计竞赛（ACM Intcrnational Collegiate Programming Contest，ACM／ICPC）是由颇具权威性的美国计算机协会（Association for Computing Machinery，ACM）主办的、世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，旨在使大学生通过编程充分展示自己分析问题和解决问题的能力。该项竞赛从1970年举办至今已有30多届，分区域预赛和国际决赛两个阶段进行。ACM国际大学生程序设计竞赛已成为在世界各国大学生中最具影响力的国际级计算机类的赛事，是广大爱好计算机编程的大学生展示才华的舞台，是著名大学计算机教育成果的直接体现，是信息企业与世界顶尖计算机人才对话的最好机会。　　1996年上海大学将ACM国际大学生程序设计竞赛首次引入中国大陆，举办了首届亚洲区预选赛中国大陆赛区比赛。1996-2001年间，共6届比赛赛区设在上海，均由上海大学主办。2002年起每年分别由国内的2-5所高校轮流主办亚洲区预选赛。　　随着ACM国际大学生程序设计竞赛在中国大陆的蓬勃开展，一些高校在程序设计类课程（高级语言程序设计、数据结构、算法设计与分析等）方面进行了一系列的教学改革，将程序设计类课程进行整合，并纷纷推出了网上在线判题系统，注重学生平时的实践，强调学生的自主学习和上机实践，并按ACM国际大学生程序设计竞赛的模式进行课程考核。同时，学生在学过程序设计语言课程后有进一步提高程序设计能力的要求，在学过数据结构和算法设计与分析后进行在线判题系统实时解题的计划，甚至有参加各种程序设计竞赛以更快地提高编程能力的愿望.另外，全国每年仅参加国内主办的亚洲区域预赛的参赛队就达几千支，而参加各校举办的各类程序设计竞赛的学生更是众多。

内容概要

　　《ACM/ICPC程序设计与分析(C++实现)》介绍ACM国际大学生程序设计竞赛概况及程序设计基础，系统介绍数论、组合数学、动态规划、计算几何、搜索、图论和网络流等专题的典型算法，挑选历年竞赛中许多有代表性的竞赛题作为例题进行分析，便于学生编程时模仿学习。每章的例题和习题都配有输入输出样例，方便学生在编程时测试与调试程序。《ACM/ICPC程序设计与分析(C++实现)》以C++为程序设计语言，以提高编程能力为目标，按照由浅人深、循序渐进的原则编写。　　《ACM/ICPC程序设计与分析(C++实现)》不仅适合于计算机专业的学生，也适合于非计算机专业的学生。《ACM/ICPC程序设计与分析(C++实现)》是问题求解性自主式学习的程序设计教材，也是学习数据结构与算法设计与分析的参考教材，还可以作为ACM国际大学生程序设计竞赛的参考书。

书籍目录

第1章 ACM国际大学生程序设计竞赛简介1.1 ACM国际大学生程序设计竞赛概况1.2 ACM国际大学生程序设计竞赛组织形式简介1.2.1 组队方式和比赛形式1.2.2 竞赛环境1.2.3 判题结果1.2.4 递交与评判1.3 程序设计对学生的要求1.4 程序设计语言选择1.5 ACM程序设计竞赛题形式习题1第2章 程序设计基础2.1 程序设计概述2.2 算法基础2.2.1 算法概述2.2.2 算法复杂性2.2.3 演绎方法的使用2.2.4 演绎法算法设计举例2.3 程序设计的输入输出形式2.4 C++文件操作2.5 输入输出格式控制2.5.1 流基类ios层次图2.5.2 非格式化抽取2.5.3 操纵算子2.6 排序2.6.1 冒泡排序2.6.2 快速排序2.7 简单应用2.7.1 转换十六进制数2.7.2 颠倒原文2.7.3 指定个数的整数求和2.7.4 不指定个数的整数求和习题2第3章 程序设计简单问题3.1 ACM／ICPC程序设计竞赛的题型3.2 简单例子3.2.1 空格字符与非空格字符统计3.2.2 荷兰国旗问题3.2.3 城市间的球面距离3.2.4 合并电话簿3.2.5 图书排序问题习题3第4章 高精度计算与代数计算4.1 高精度计算4.1.1 基本知识4.1.2 高精度数据的处理方法4.1.3 高精度四则运算的基本处理方法4.2 高精度四则运算应用4.2.1 A+B问题4.2.2 公牛和母牛4.2.3 A一月问题4.2.4 计算余数问题4.3 代数计算4.4 实例研究4.4.1 指数函数值4.4.2 是金还是银4.4.3 p倍和子集问题4.4.4 杨辉三角形4.4.5 黑白棋游戏习题4第5章 数论中的程序设计5.1 从跳兽问题谈起5.2 最大公因数与最小公倍数5.2.1 公因数和最大公因数的概念5.2.2 最小公倍数5.2.3 欧几里得算法5.3 利用欧几里得算法求整系数一次不定方程5.4 求解模线性方程5.4.1 模和同余5.4.2 模线性方程5.5 求modm的逆元素算法5.6 模线性方程组与中国剩余定理5.7 模幂运算与素数测试5.7.1 模幂运算5.7.2 素数测试5.8 二次剩余与Pell方程5.8.1 二次剩余5.8.2 Pell方程5.9 实例研究5.9.1 MagicHorse5.9.2 阶乘问题5.9.3 邮票问题5.9.4 Josephus问题5.9.5 负数进制转换5.9.6 数塔问题5.9.7 幸运数5.9.8 哥德巴赫猜想习题5第6章 组合数学中的程序设计6.1 组合数学中有关概念与公式6.1.1 排列与组合及有关的生成算法6.1.2 母函数6.1.3 容斥原理与错排6.1.4 P6lya定理6.2 实例研究6.2.1 蛋糕6.2.2 杨辉三角形中的奇偶问题6.2.3 足球赛票6.2.4 棋盘格数6.2.5 保险柜上锁6.2.6 弹球游戏6.2.7 最少砝码6.2.8 环6.2.9 珍珠项链6.2.1 0统计棋局数习题6第7章 动态规划7.1 动态规划原理7.2 实例研究7.2.1 游船费问题7.2.2 航线设置7.2.3 复制书稿7.2.4 括号序列7.2.5 整数匹配问题7.2.6 生日蛋糕7.2.7 乘积最大7.2.8 多边形计算习题7第8章 计算几何学8.1 几何基本知识8.1.1 矢量的概念8.1.2 矢量加减法8.1.3 矢量叉积8.1.4 折线段的拐向判断8.1.5 判断点是否在线段上8.1.6 跨立试验与判断两线段是否相交8.1.7 整数点与Pick定理8.2 基本算法8.3 凸包8.3.1 凸包的概念与实例8.3.2 Graham扫描法8.3.3 Jarvis步进法8.3.4 Graham扫描法与Jarvis步进法的程序实现8.4 实例研究8.4.1 有缺陷的卫星8.4.2 篱笆8.4.3 处于危险之中的飞行员8.4.4 穿街走巷8.4.5 三角形习题8……第9章 搜索算法第10章 一般图论中的程序设计第11章 网络流与二分图第12章 杂例

章节摘录

　　ACM国际大学生程序设计竞赛（ACM Intcrnational Collegiate Programming Contest，ACM／ICPC）是由颇具权威性的美国计算机协会（Association for Computing Machinery，ACM）主办的，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，是计算机界的奥林匹克比赛。该项竞赛从1970年起至2009年已举办30多届。历年来这样的竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，因而该赛事受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注。　　此项赛事的目的是大学生运用计算机编程平台，充分展示自己分析问题和解决问题的能力，团队合作精神以及他们在程序设计过程中的创新意识，同时也是检测学生们在压力下进行开发活动的能力。可以说，ACM国际大学生程序设计竞赛是参赛学生展示计算机才华的广阔舞台，是大学计算机教育成果的直接体现，是IT企业与世界顶尖计算机人才对话的最好机会。该项竞赛分区域预赛和世界总决赛两个阶段进行，世界总决赛安排在每年的3-4月举行，而区域预赛安排在上一年的9－12月在各大洲举行。另外，为配合世界总决赛和洲区域预赛，也有称为地区二级预赛的国家赛、省级赛、学校选拔赛以及邀请赛。IBM公司已连续多年赞助该项赛事的世界总决赛和区域预赛，而一些企业也争相赞助，使ACM赛事在各大洲蓬勃开展。