|
|
| ||||||||||||||||||||||
前言 N.Wirth给出了程序设计的一个重要公式，程序=算法+数据结构。 作为一个程序员或者程序设计爱好者来说，不应该只把程序设计作为一门技术，更应该看成是一种艺术。其实，算法本身也是一门艺术，数据结构本身也是一门艺术。程序也好，算法也好，数据结构也好，其中都蕴涵了很多的数学，而数学更是一门艺术。如果把数学与程序设计完美地结合在一起，则是艺术的巅峰！ 从某种意义上来说，计算机源于数学。而作为计算机科学核心技术的程序设计，与数学之间的关系更是密不可分，可以这样说，数学是计算机程序设计的灵魂。利用数学方面的知识、数学分析的方法以及数学解题的技巧，可以使得程序设计变得轻松、美观、高效，而且往往能反映出问题的本质。 在ACM国际大学生程序设计竞赛（ACMICPC）和全国青少年信息学奥林匹克竞赛（NOI）系列活动中，越来越多地出现了数学的影子，也用到了越来越多数学方面的知识，对选手的数学修养要求越来越高。本书的目的就在于给广大编程爱好者和信息学参赛者，介绍和总结一些程序设计中常用的数学知识和数学方法，希望能起到抛砖引玉的作用。 本书由全国青少年信息学奥林匹克竞赛金牌指导教师、常州市第一中学林厚从老师主编。2008年，笔者编写出版了《数学与程序设计》一书，深受读者欢迎。相比而言，《信息学奥赛之数学一本通》知识内容更加丰富、体系结构更加完整、例题习题更加新颖，更加突出实战性和应用性。在编写过程中，吸收了很多OIer的灵感和智慧，参考了部分国家集训队员和教练员的论文，包括朱全明、贾志鹏、陈瑜希、董宏华、金策、鬲融、唐文斌、余林韵、朱泽园、俞华程、Matrix67的博客、ACdreamers的博客、pi9nc的博客。福州市第三中学黄志刚老师和吴钰晗、闫书弈两位同学，以及常州市第一中学吴睿海、孔瑞阳等同学为本书的编写做了大量调试和校对工作。全国青少年信息学奥林匹克竞赛（NOI）科学委员会主席、清华大学计算机科学与技术系王宏老师，在百忙之中审定了全书。在此，一并表示感谢！由于水平有限，书中难免存在不当之处，恳请谅解，也欢迎广大读者批评指正，不胜感激！ 书中所有例题的参考程序均采用DevC++实现。如果需要本书中所有题目的测试数据和PASCAL标程，请发邮件与我联系（hc.lin@163.com）。 笔者 目录 第1章数论1 1.1整除2 1.2同余6 1.3最大公约数9 1.31辗转相除法9 1.32二进制算法9 1.33最小公倍数10 1.34扩展欧几里得算法10 1.35求解线性同余方程11 1.4逆元*本书中加“*”号内容为提高性知识，一般在省队选拔及NOI比赛中才会涉及。16 1.5中国剩余定理*20 1.6斐波那契数23 1.7卡特兰数29 1.8素数32 1.81素数的判定33 1.82素数的相关定理35 1.83MillerRabin素数测试*36 1.84欧拉定理37 1.85Pollard Rho算法求大数因子*38 1.9BabyStepGiantStep及扩展算法*46 1.10欧拉函数的线性筛法*54 1.11本章习题57 第2章群论*64 2.1置换64 2.11群的定义64 2.12群的运算64 2.13置换65 214置换群65 2.2拟阵65 2.21拟阵的概念66 2.22拟阵上的最优化问题67 2.3Burnside引理69 2.4Polya定理72 2.5本章习题86 第3章组合数学91 3.1计数原理91 3.2稳定婚姻问题*101 3.3组合问题分类107 3.31存在性问题108 3.32计数性问题108 3.33构造性问题109 3.34最优化问题110 3.4排列110 3.41选排列110 3.42错位排列113 3.43圆排列113 3.5组合116 3.6母函数*129 3.61普通型母函数130 3.62指数型母函数132 3.7莫比乌斯反演*142 3.8Lucas定理*150 3.9本章习题155 第4章概率163 4.1事件与概率163 4.2古典概率165 4.3数学期望171 4.4随机算法181 4.5概率函数的收敛性*189 4.6本章习题197 第5章计算几何203 5.1解析几何初步203 5.11平面直角坐标系203 5.12点204 5.13直线204 5.14线段205 5.15多边形205 5.16圆206 5.2矢量及其运算213 5.21矢量的加减法213 5.22矢量的数量积213 5.23矢量的矢量积214 5.3计算几何的基本算法220 5.4平面凸包236 5.5旋转卡壳*243 5.51计算距离244 5.52外接矩形248 5.53三角剖分250 5.54凸多边形属性254 5.6半平面交*264 5.7离散化272 5.8本章习题278 第6章矩阵297 6.1矩阵及其运算297 6.11矩阵的基本运算298 6.12矩阵的乘法运算299 6.13矩阵的行列式299 6.14矩阵的特殊类别300 6.2数字方阵309 6.3线性方程组及其解法314 631高斯消元法314 632LU分解法318 6.4MatrixTree定理*327 6.5本章习题336 第7章函数347 7.1函数的基本知识347 7.11函数的特性348 7.12常见的函数类型350 7.2函数的单调性354 7.3函数的凹凸性361 7.4SG函数365 7.5快速傅立叶变换*368 7.6快速数论变换*373 7.7本章习题379 |
精品新书
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
 |
 |
