一个正六边形被分成了6个相同的小三角形如果用红、黄两种颜色分别涂满小三角形，那么有（ ）种 不同的涂法。（旋转后图案相同的认为是同一种涂法）第一章 数学预备知识 第二章 导引与基本数据结构 第三章 递归算法武汉科技大学理学院信息与计算科学系杨 波cookie_yb73126.com2008年9月序专业基础课程：数据结构、计算机语言操作系统、编译 如何编写计算机程序：n数据结构+算法 = 程序n算法：计算机软件的“灵魂”算法是计算机科学和计算机应用的核心ACM国际大学生程序设计竞赛ACM国际大学生程序设计竞赛（英文全 称：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC ）是由美国计算机协会（ACM）主办的，一 项旨在展示大学生创新能力、团队精神和在 压力下编写程序、分析和解决问题能力的年 度竞赛。经过30多年的发展，ACM国际大学 生程序设计竞赛已经发展成为最具影响力的 大学生计算机竞赛。赛事目前由IBM公司赞 助。内容n入门三本：q数据结构与算法（傅清祥，王晓东编著）q程序设计导引及在线实践 作者: 李文新qACM程序设计培训教程 吴昊 n基础提高： q算法艺术与信息学竞赛 第二版 刘汝佳q算法设计与分析 王晓东q科曼：算法导论q组合数学 第三版 冯舜玺 译q计算几何算法设计与分析 周培德 qConcrete Mathematics - A Foundation For Computer Science Ronald L. Graham ， Donald E. Knuth ， Oren Patashnik具体数学计算机程 序设计艺术三卷 Knuth q组合数学的算法与程序设计q程序设计中的组合数学 吴文虎q图论的算法与程序设计教材与参考书n教 材：q余祥宣等编著，计算机算法基础（第三版），华中理工大 学出版社，2006年n参考书：q徐士良编，C常用算法程序集，华大学出版社，1998年qCLLIFORD A. SHAFFER著，A Practical Introduction to DATA STRUCTURES AND ALGORITHM ANALYSIS，电 子工业出版社，1998年q卢开澄编，计算机算法导引，清华大学出版社，2003年1.1 算法什么是算法？n算法如数字、计算一样，是一个基本概念。n算法是解一确定类问题的任意一种特殊的方法。n在计算机科学中，算法是使用计算机解一类问题 的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某 一特定类型问题的一系列运算。算法的五个重要特性确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定 义，不能有二义性。 例：不符合确定性的运算n5/0 n将6或7与x相加n未赋值变量参与运算2）能行性算法中有待实现的运算都是基本的运算， 原理上每种运算都能由人用纸和笔在“有限” 的时间内完成。例：整数的算术运算是“能行”的实数的算术运算是“不能行”的3）输入每个算法有0个或多个输入。这些输 入是在算法开始之前给出的量，取自于 特定的对象集合定义域（或值域）4）输出一个算法产生一个或多个输出，这 些输出是同输入有某种特定关系的量。5）有穷性一个算法总是在执行了有穷步的运算之后终 止。计算过程：只满足确定性、能行性、输入 、输出四个特性的一组规则。n算法和计算过程的区别：q计算过程：操作系统(不终止的运行过程)q算法是“可以终止的计算过程”n算法的时效性：只能把在相当有穷步内终止的算 法投入到计算机上运行算法学习的内容n如何设计算法：设计策略，创造性的活动n如何表示算法q条列式的步骤q流程图q伪码q程序语言n如何确认算法：证明算法的正确性n如何分析算法：时间和空间需求的定量分析n如何测试算法调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计算法学习的内容n如何设计算法：设计策略，创造性的活动n如何表示算法q条列式的步骤q流程图q伪码q程序语言n如何确认算法：证明算法的正确性n如何分析算法：时间和空间需求的定量分析n如何测试算法调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计算法学习的内容n如何设计算法：设计策略，创造性的活动n如何表示算法q条列式的步骤q流程图q伪码q程序语言n如何确认算法：证明算法的正确性n如何分析算法：时间和空间需求的定量分析n如何测试算法调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计1.2 分析算法n算法分析对算法所消耗的资源（时间和空间）进行估算n算法分析的目的q预计所涉及的算法能在什么样的环境中有效地运行，在最 好、最坏和平均情况下执行得怎么样。q对同一问题的不同算法进行时空耗费两方面的分析n算法分析的意义通过对算法的分析，在把算法变成程序实际运行前，就 知道为完成一项任务所设计的算法的好坏，从而运行好的算 法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的“古老”而“前沿”的课题 。重要假设计算机模型的假设n计算机形式理论模型： Turing机模型n通用计算机模型：q顺序计算机q有足够的“内存”q能在固定的时间内存取数据单元计算约定算法的执行时间=其中，fi是算法中用到的某种运算i的次数称 为该运算的“频率计数”。ti是该运算执行一次所用的时间 与程序语 言和硬件有关。n时间囿界于常数的运算：q基本算术运算，如整数、浮点数的加、减、乘、除q字符运算、赋值运算、过程调用等特点：尽管每种运算的执行时间不同，但一般只花一个固定量的时间（单位时间）就可完成。n其他运算：q字符串操作：与字符串中字符的数量成正比q记录操作：与记录的属性数、属性类型等有关特点：运算时间无定量。工作数据集的选择n编制能够反映算法在最好、平均、最坏 情况下工作的数据配置。然后使用这些 数据配置运行算法，以了解算法的性能 。编制测试数据是程序测试与算法分析中 的关键技术之一。q作为算法分析的数据集：反映算法的典型特征q作为程序正确性及性能测试的数据集：测试程序的对 错，反映对性能指标产生影响的方面，如边界值算法分析的两阶段n事前分析：求算法的一个时间/空间限界函数，即通过对算法的 “理论”分析，得出关于算法时间和空间特性的特征函数 与计算机物理软硬件没有直接关系。n事后测试：将算法编制成程序后实际放到计算机上运行，收集 其执行时间和空间占用等统计资料，进行分析判断 直接与物理实现有关。n目的：试图得出关于算法特性的一种形式描述 ，以“理论上”衡量算法的“好坏”。n如何给出反映算法特性的描述？统计算法中各种运算的执行情况，包括：q引用了哪些运算q每种运算被执行的次数（频率计数）q该种运算执行一次所花费的时间等。算法的执行时间=事前分析频率计数频频率计计数：算法中语句或运算的执行次数。 例：x=x+y; for(i=1;icurrlarge)currlarge=arrayi;return currlarge; 分析方法：找近似时间n问题规模n（数组的维数）n基本运算，将存放的当前最大数与数组每个元素比 较n假定每次比较的时间为cq变量i增加所需时间q找到一个新的最大元素时要做的工作q不考虑c的实际值，不考虑初始化时所需的一小部分时间， 只想得到该算法的一个合理近似时间。计算时间T(n)=cn 增长率：当问题规模增大时，算法代价增长的速度。 线性增长率例 2 一个整数数组的第一个元素值复制给另一 个变量。 分析：n问题规模nn基本运算是赋值nT(n)=c1 （c1表示赋值所需时间），与问题规 模无关。 常数运行时间例 3 程序段如下： sum=0; for(i=1;i0成立，则 f(n)=O(g(n)；n若f1(n) =O(g1(n)，f2(n) =O(g2(n)，则 f1(n)+f2(n)=O(max(g1(n), g2(n)；n若f1(n) =O(g1(n)，f2(n) =O(g2(n)，则 f1(n)f2(n)=O(g1(n)g2(n)。法则1说明：如果g(n)是算法代价函数的一个上限， 则g(n)的任意上限h(n)也是该算法代价的上限。对于 表示法有类似的性质：若如果g(n)是算法代价函 数的一个下限，则g(n)的任意下限h(n)也是该算法代 价的下限。表示法同理。 法则2的意义在于使我们能够忽略O表示法中的常数 因子。对于和表示法同样有这样的性质。 法则3说明，顺序给出一个程序的两个部分（两组 语句或两段代码），我们只需要考虑其中开销大的 部分。类似地，在和表示法中，也只看开销大 的部分就可以了。 法则4用于分析程序中的简单循环。如果要有限次 地重复某种操作，且每次重复的开销相等，则总开 销为每次的开销与重复次数之积。对于和表示 法结论也成立。 可以在计算任何算法开销的近似增长率 时，忽略所有的常数和低次项。 程序运行时间的计算例1：首先看一个给整型变量赋值的简单语句 ： a=b；分析：该语句执行时间为一个常量，为(1)。 例2：简单的循环：sum=0;for(i=1;ib例2 考 虑分析：a=1，b=3/2，c=1，d(n)=c差分方程法对于某些递归方程，一般项并不是由一个低次 项而是由多个低次项表示的。如： (1) T(n)=a1T(n-1)+a2T(n-2)+akT(n-k)，nk，ai，i=1,k为常数，ak0。K阶常系数齐次差分方程：T(n)-a1T(n-1)-a2T(n-2)-akT(n-k)=0K阶常系数齐次差分方程的特征方程：xk-a1xk-1-a2xk-2-ak-1x-ak=01) 如果k个根互不相同，则齐次方程的通解为 ：其中ci，i=1,k为待定常数，由初始条件确定2) 如果有r个重根，qi=qi+1=qi+r-1则通解为：例：求解递归方程例：求解递归方程差分方程法(2) T(n)=a1T(n-1)+a2T(n-2)+akT(n-k)+f(n)，nk，ai，i=1,k为常数，ak0 ，f(n)0 。K阶常系数非齐次差分方程：T(n)-a1T(n-1)-a2T(n-2)-akT(n-k)=f(n)通解是：对应齐次方程的通解特解n特解求法q试探法（因为并不存在寻找特解的一般方法）q根据f(n)的特点推测特解形式，用代定系数法确定 系数。q利用叠加原理将f(n)线性分解成若干个单项之和， 并求出各单项的特解，然后叠加得到f(n)的特解。 这使得试探法更有效三种特殊形式的f(n)，其中pi, i=0,1,s为待定的常数，c(x)为特征多项式。f(n)的形式条件特解形式 anc(a)0p0an a是c(x)的m重 根p0nmannsc(1)0p0+p1n+p2n2+psns 1是c(x)的m重 根nm(p0+p1n+p2n2+psns)nsanc(a)0(p0+p1n+p2n2+psns)an a是c(x)的m重 根nm(p0+p1n+p2n2+psns)an例1 求递归方程：T(n)+5T(n-1)+6T(n-2)=3n2的 一个特解。 解： c(x)=x2+5x+6=0 x1=-2 x2=-3 c(1)0 设T*(n)=p1n2+p2n+p3 得p1=1/4 p2=17/24 p3=115/288例2 求解递归方程：解：c(x)=x2+5x+6=0 x1=-2 x2=-3 c(4)0设T*(n)=p4n 得p=16c1=-112 c2=96生成函数（母函数）定义：生成函数 设a0,a1,an,是一个数列，做形式 幂级 数：