计算机程序设计竞赛-第1讲课件

计算机程序设计竞赛精品精品PPT课程介绍及要求课程介绍及要求v课程类别：全校公选课课程类别：全校公选课v总学时数：总学时数：36（实操课）（实操课）v开课目的：为信息科学系开课目的：为信息科学系竞赛项目：第六届竞赛项目：第六届“蓝蓝桥杯软件人才与设计大赛桥杯软件人才与设计大赛”培养人才。培养人才。v主要培养学生解决实际问题的编程能力、培养学生的主要培养学生解决实际问题的编程能力、培养学生的创新思维。程序是自己设计出来的，而不是某个固定创新思维。程序是自己设计出来的，而不是某个固定的方程式。的方程式。精品精品PPT主要内容主要内容算法算法程序设计的灵魂程序设计的灵魂123经典算法经典算法简单的数据结构知识简单的数据结构知识精品精品PPT1.11.1 什么是算法什么是算法一个程序应包括两个方面的内容:对数据的描述：数据结构(data structure)对操作的描述：算法(algorithm)数据结构数据结构 +算法算法 =程序程序 数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具 算法是解决算法是解决“做什么做什么”和和“怎么做怎么做”的问题的问题。即是为。即是为解决一个问题而采取的方法和步骤。解决一个问题而采取的方法和步骤。精品精品PPT1.2 1.2 简单算法举例简单算法举例步骤1：先求12，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120精品精品PPT1.2 1.2 简单算法举例简单算法举例何为算法何为算法“烧水泡茶”有如下五道工序：1、烧开水2、洗茶壶3、茶杯4、拿茶叶5、泡茶。烧开水、洗茶壶、茶杯，拿茶叶是泡茶的前提。其中烧开水需要15分钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需要1分钟。下面是两种“烧水泡茶”的方法。方法方法1：第一步：烧水；第二步：水烧开后，洗刷茶具，拿茶叶；第三步：沏茶。方法方法2：第一步：烧水；第二步：烧水过程中，洗刷茶具，拿茶叶；第三步：水烧开后沏茶。精品精品PPT1.3 1.3 算法的特性算法的特性有穷性有穷性一个算法应包含有限的操作步骤，而不能是无限的。确定性确定性算法中的每一个步骤都应当是确定的，不能含糊。输入输入有零个或多个输入，从外界获取必要信息。输出输出有一个或者多个输出，得到问题的解。有效性有效性每一个步骤有效执行，得到确定的结果。精品精品PPT1.4 1.4 算法的表示算法的表示l算法的表示算法的表示自然语言自然语言传统流程图传统流程图N-S流程图流程图伪代码伪代码计算机语言计算机语言精品精品PPT1.4 1.4 算法的表示算法的表示v传统流程图（流程图）传统流程图（流程图）美国国家标准化协会美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：规定了一些常用的流程图符号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点精品精品PPT1.4 1.4 算法的表示算法的表示1ti5开始开始2it*iti+1i结束结束NY1ti5开始开始2it*(2*i-1)ti+1i结束结束NY图1图2精品精品PPT1.4 1.4 算法的表示算法的表示n流程图的连接点举例流程图的连接点举例位置位置不够不够防止防止交叉交叉精品精品PPT1.4 1.4 算法的表示算法的表示n流程图表示三种基本结构流程图表示三种基本结构顺序结构顺序结构AB精品精品PPT1.4 1.4 算法的表示算法的表示n流程图表示三种基本结构流程图表示三种基本结构选择结构选择结构ABYpNAYpN精品精品PPT1.4 1.4 算法的表示算法的表示n流程图表示三种基本结构流程图表示三种基本结构循环结构循环结构AYp1NAYp2N当型循环结构直到型循环结构精品精品PPT1.4 1.4 算法的表示算法的表示vN-S流程图（流程图（N-S图）图）由由I.Nassi和和Shneiderman提出的新的流程图形式，称为提出的新的流程图形式，称为N-S流程图。其三种基本结构的流程图。其三种基本结构的N-S图表示：图表示：ABABYNpA当p1成立A直到p2成立顺序结构选择结构循环结构（当型）循环结构（直到型）精品精品PPT1.4 1.4 算法的表示算法的表示v例例2 求求12345：即：即求求5!的的N-S图算法表示图算法表示：直到直到i51t输出输出t2it*iti+1i1ti5开始开始2it*iti+1i结束结束NY输出输出tN-S图VS精品精品PPT1.4 1.4 算法的表示算法的表示v例例3 输入输入50名学生名学生的学号和的学号和成绩，并将成绩，并将50名学生名学生中成绩中成绩高于高于80分者的学号和成绩输分者的学号和成绩输出。出。算法用算法用N-S图表示图表示，如右图，如右图。练习：使用流程图表示算法。练习：使用流程图表示算法。直到直到i501i1ii+1i输入输入ni、gii+1i直到直到i50gi 80否否是是输出输出ni,gi精品精品PPT1.4 1.4 算法的表示算法的表示1ii50开始开始i+1i结束结束NY输入输入ni、gi1igi 80输出输出ni、gii+1ii50NYYNv例例3 流程图如下：流程图如下：精品精品PPT1.4 1.4 算法的表示算法的表示v例例4 判定判定2000-2500年中的每一年是否闰年，并将结果输出。年中的每一年是否闰年，并将结果输出。v闰年的条件：闰年的条件：能被能被4整除，但不能被整除，但不能被100整除的年份整除的年份 都是闰年，如都是闰年，如2008、2012、2048年年。能被能被400整除的年份是闰年，整除的年份是闰年，如如2000年年。year不能不能被被4整除整除非闰年非闰年year被被4整整除，但不除，但不能被能被100整整除除闰年闰年year被被100整除，整除，又能被又能被400整除整除闰年闰年其他其他非闰年非闰年逐渐缩小判逐渐缩小判断的范围断的范围精品精品PPT1.4 1.4 算法的表示算法的表示v例例4 判定判定2000-2500年中的每一年是否闰年，并将结果输出。年中的每一年是否闰年，并将结果输出。NYN开始开始2000yearyear不能被不能被4整除整除year是闰年是闰年year不能被不能被100整除整除year+1yearyear2500结束结束Yyear不能被不能被400整除整除year不是闰年不是闰年year是闰年是闰年year不是闰年不是闰年YNYN精品精品PPT1.4 1.4 算法的表示算法的表示v例例4 判定判定2000-2500年中的每一年是否闰年，并将结果输出。年中的每一年是否闰年，并将结果输出。直到直到year25002000yearyear+1year否否是是year%4为为0否否是是输出输出year非闰年非闰年year%100不为不为0year%400为为0是是否否输出输出year非闰年非闰年输出输出year闰年闰年输出输出year闰年闰年精品精品PPT1.4 1.4 算法的表示算法的表示v用伪代码表示算法用伪代码表示算法概念：概念：伪代码是用介于自然语言和计算机语言之间的文字和符伪代码是用介于自然语言和计算机语言之间的文字和符号，用来描述算法。号，用来描述算法。特点：特点：如一篇文章，自上而下地写下来。每一行如一篇文章，自上而下地写下来。每一行(或几行或几行)表示表示一个基本操作。它不用图形符号，因此书写方便一个基本操作。它不用图形符号，因此书写方便、格式紧、格式紧凑，也比较好懂，也便于向计算机语言算法凑，也比较好懂，也便于向计算机语言算法(即程序即程序)过渡。过渡。精品精品PPT1.4 1.4 算法的表示算法的表示v例例5：“打印打印x的绝对值的绝对值”，用伪代码表示算法。，用伪代码表示算法。用英文伪代码表示：用英文伪代码表示：IF x is positive THEN print x ELSE print-x也可以用汉字伪代码表示：也可以用汉字伪代码表示：若若 x为正为正 打印打印 x 否则否则 打印打印-x也可以中英文混用，如：也可以中英文混用，如：IF x 为正为正 print x ELSE print-x精品精品PPT1.4 1.4 算法的表示算法的表示v用计算机语言表示算法用计算机语言表示算法概念概念：用计算机语言描述算法，就是用计算机语言编写程序。用计算机语言描述算法，就是用计算机语言编写程序。计算机是无法识别流程图和伪代码的。只有用计算机语言计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。编写的程序才能被计算机执行。特点：特点：设计算法的目的是为了实现算法。设计算法的目的是为了实现算法。用计算机语言表示算法，必须严格遵循所用的语言的语法用计算机语言表示算法，必须严格遵循所用的语言的语法规则。规则。精品精品PPT1.4 1.4 算法的表示算法的表示v例例6：求：求5!用用C语言表示。语言表示。N-S图为：图为：#include int main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%dn,t);return 0;当当i=51t输出输出t2it*iti+1i精品精品PPT1.4 1.4 算法的表示算法的表示v算法算法广义地说，为解决一个问题而采取的方法和步骤，称为广义地说，为解决一个问题而采取的方法和步骤，称为“算法算法”。对同一个问题，可以有不同的对同一个问题，可以有不同的算法。算法。v计算机算法可分为两大类别：计算机算法可分为两大类别：数值运算算法，目的是求数值解。数值运算算法，目的是求数值解。非数值运算算法，包括的面十分广泛，最常见的是用于事务管理领非数值运算算法，包括的面十分广泛，最常见的是用于事务管理领域。域。n注意：注意：写出了写出了C程序，仍然只是描述了算法，并未实现算法。程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。只有运行程序才是实现算法。精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析v算法的复杂性越高，所需的计算机资源越多。算法的复杂性越高，所需的计算机资源越多。v最重要的计算机资源是时间资源与空间资源。最重要的计算机资源是时间资源与空间资源。v需要计算机时间资源的量称为时间复杂度，需要计算机空需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。间资源的量称为空间复杂度。v时间复杂度与空间复杂度集中反映算法的效率。时间复杂度与空间复杂度集中反映算法的效率。精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析一个算法的时间复杂度是指算法运行所需的时间。一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的一个算法的运行时间取决于算法所需执行的语句（运算）的多少。多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。量级决定。精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析 算法的执行频数的数量级直接决定算法的时间复杂算法的执行频数的数量级直接决定算法的时间复杂度。度。精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析2 2个语句各执行个语句各执行1 1次，共执行次，共执行2 2次次。时间复杂度为时间复杂度为O(1)O(1)(1)x=x+1;s=s+x;(2)for(k=1;k=n;k+)x=x+y;y=x+y;s=x+y;“k=1k=1”执行执行1 1次；次；“k=nk=n”与与“k+k+”各执行各执行n n次；次；3 3个赋值语个赋值语句，每个赋值语句各执行句，每个赋值语句各执行n n次；共执行次；共执行5n+15n+1次次.时间复杂度为时间复杂度为O(n).O(n).精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析例1-3 试计算下面三个程序段的执行频数(3)for(t=1,k=1;k=(3)for(t=1,k=1;k=n;kn;k+)+)t=t*2;t=t*2;for(j=1;j=for(j=1;j=t;jt;j+)+)s=s=s+js+j;“t=1t=1”与与“k=1k=1”各执行各执行1 1次；次；“k=nk=n”与与“k+k+”各执行各执行n n次；次；“t=t*2t=t*2”执行执行n n次；次；“j=1j=1”执行执行n n次；次；“j=tj=t”、“j+j+”与内循环的赋值语句与内循环的赋值语句“s=s=s+js+j”各执行频数为各执行频数为:总的执行总的执行频数为：频数为：精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析 在估算算法的时间复杂度时，为简单计，以后只考虑内循环在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其它语句的执语句的执行频数，而不细致计算各循环设计语句及其它语句的执行次数，这样简化处理不影响算法的时间复杂度。行次数，这样简化处理不影响算法的时间复杂度。例例1-41-4 估算以下程序段所代表算法的估算以下程序段所代表算法的时间时间复复杂杂度。度。for(k=1;k=for(k=1;k=n;kn;k+)+)for(j=1;j=for(j=1;j=k;jk;j+)+)x=x=k+jk+j;s=s=s+xs+x;每个每个赋值语句句执行行频率率为n(n+1)/2,该算法的算法的时间复复杂度度为:O(n2)精品精品PPT1.5 1.5 算法复杂度的分析算法复杂度的分析n一一个个程程序序运运行行所所需需的的存存储空空间通通常常包包括括固固定定空空间需需求求与与可可变空空间需求两部分。需求两部分。1.固固定定空空间需需求求包包括括程程序序代代码、常常量量与与静静态变量量等等所所占占的空的空间。2.可可变空空间需需求求包包括括局局部部作作用用域域非非静静态变量量所所占占用用的的空空间、从从堆堆空空间中中动态分分配配的的空空间与与调用用函函数数所所需需的的系系统栈空空间等。等。算法的空算法的空间复复杂度是指算法运行的存度是指算法运行的存储空空间，是，是实现算算法所需的内存空法所需的内存空间的大小。的大小。精品精品PPT1.6 1.6 学好算法的秘诀学好算法的秘诀（1）学的要深入，基础要扎实学的要深入，基础要扎实 基础的作用不必多说，在大学课堂上曾经讲过了很多次，在此重点说明基础的作用不必多说，在大学课堂上曾经讲过了很多次，在此重点说明“深入深入”。职场不是学校，企业要求你能高效的完成项目功能，但是现实中的。职场不是学校，企业要求你能高效的完成项目功能，但是现实中的项目种类繁多，我们需要从根上掌握项目种类繁多，我们需要从根上掌握C语言算法技术的精髓。走马观花式的学语言算法技术的精髓。走马观花式的学习已经被社会所淘汰，入门水平不会被开发公司所接受，他们需要的是高手。习已经被社会所淘汰，入门水平不会被开发公司所接受，他们需要的是高手。（2）恒心、演练、举一反三）恒心、演练、举一反三 学习编程的过程是枯燥的过程，我们需要将学习算法当成是自己的乐趣，学习编程的过程是枯燥的过程，我们需要将学习算法当成是自己的乐趣，只有做到持之以恒才能有机会学好。另外编程最注重实践，最害怕闭门造车。只有做到持之以恒才能有机会学好。另外编程最注重实践，最害怕闭门造车。每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识的每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识的理解。并且要做到举一反三，只有这样才能对知识的深入理解。理解。并且要做到举一反三，只有这样才能对知识的深入理解。（3）语言之争的时代更要学会坚持）语言之争的时代更要学会坚持精品精品PPT2.2.经典算法经典算法九大大九大大算法算法思想思想l枚举算法思想枚举算法思想l递推算法思想递推算法思想l递归算法思想递归算法思想l分治算法思想分治算法思想l贪心算法思想贪心算法思想l试探法算法思想试探法算法思想l迭代迭代算法算法思想思想l动态规划算法思想动态规划算法思想l模拟算法思想模拟算法思想精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法n比比较笨的枚笨的枚举算法思想算法思想 枚举枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一语言中，枚举算法一般使用般使用while循环实现循环实现。枚举。枚举算法一般按照如下三个步骤进行。算法一般按照如下三个步骤进行。（1）题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。（2）判断是否是真正解的方法。（3）使可能解的范围降至最小，以便提高解决问题的效率。精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法n使用枚举算法解题的基本思路如下所示。（1）确定枚举对象、枚举范围和判定条件；（2）逐一枚举可能的解，验证每个解是否是问题的解。精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法 2.枚举的框架描述枚举的框架描述n=0;n=0;for(k=for(k=;k=;k=;k+);k+)/控制枚举范围控制枚举范围 if(if()/)/根据约束条件实施筛选根据约束条件实施筛选 printfprintf();/);/输出解输出解 n+;/n+;/统计解的个数统计解的个数 精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法举例：完美综合式举例：完美综合式 案例提出：案例提出：把数字把数字1,2,.,91,2,.,9这这9 9个数字分别填入以下含加、减、乘、除个数字分别填入以下含加、减、乘、除与乘方与乘方()()的综合运算式中的的综合运算式中的9 9个个中中 +-=0 =0 要求数字要求数字1,2,.,91,2,.,9这这9 9个数字在式中出现一次且只出现一次，个数字在式中出现一次且只出现一次，且约定数字且约定数字“1 1”不出现在乘、乘方的一位数中。不出现在乘、乘方的一位数中。精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法 设置整数变量，其中设置整数变量，其中abab用用a a自乘自乘b b次实现。次实现。即要求的综合运算式为即要求的综合运算式为:ab+zab+z/c-d*e=0/c-d*e=0 设置设置a,b,c,d,ea,b,c,d,e循环，对每一组循环，对每一组a,b,c,d,ea,b,c,d,e，计算，计算z=(d*z=(d*e-abe-ab)*c)*c，省略，省略z z循环。循环。检测检测z z是否为二位数。若是否为二位数。若z z非二位数，则返回。非二位数，则返回。对对6 6个整数进行数字分离，设置个整数进行数字分离，设置f f数组对分离的数组对分离的9 9个数字进行统计，个数字进行统计，f(x)f(x)即为数字即为数字x(1x(19)9)的个数。的个数。若某若某f(x)f(x)不为不为1 1，标记，标记t=1t=1，则返回。，则返回。若所有若所有f(x)f(x)全为全为1 1，保持标记，保持标记t=0,t=0,则输出。则输出。1.枚举设计枚举设计要点要点精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法 for(a=2;a=9;a+)for(a=2;a=9;a+)for(b=2;b=9;b+)for(b=2;b=9;b+)for(c=12;c=98;c+)for(c=12;c=98;c+)for(d=12;d=98;d+)/for(d=12;d=98;d+)/实施枚举实施枚举 for(e=2;e=9;e+)for(e=2;e=9;e+)for(t=1,k=1;k=for(t=1,k=1;k=b;kb;k+)t=t*a;+)t=t*a;z=(d*e-t)*c;z=(d*e-t)*c;if(z98)continue;if(z98)continue;m1=m1=a;ma;m2=2=b;mb;m3=3=c;mc;m4=4=d;md;m5=5=e;me;m6=z;6=z;精品精品PPT2.1 2.1 经典算法经典算法枚举法枚举法 for(x=0;x=9;x+)fx=0;for(x=0;x=9;x+)fx=0;for(k=1;k=6;k+)for(k=1;k0)while(y0)x=y%10;fx=fx+1;y=y/10;x=y%10;fx=fx+1;y=y/10;for(t=0,x=1;x=9;x+)for(t=0,x=1;xmax,a(i)max,则则 max=a(i)max=a(i)。（4 4）在得到最大值在得到最大值maxmax后，最后在所有后，最后在所有n n项中搜索哪些项为最项中搜索哪些项为最大项大项(因最大项可能多于一项因最大项可能多于一项),),并输出最大值并输出最大值maxmax及所有搜索得及所有搜索得到的最大项。到的最大项。2.2 2.2 经典算法经典算法递推算法递推算法精品精品PPT2.递推设计递推设计描述描述scanfscanf(%(%d,&nd,&n););a1=1;max=0;a1=1;max=0;for(i=2;i=for(i=2;imax)max=ai;/if(aimax)max=ai;/比较得最大值比较得最大值 printfprintf(a(%d)=%d n,(a(%d)=%d n,n,an,an);n);精品精品PPT猴子爬山猴子爬山案例提出：一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。2.2 2.2 经典算法经典算法递推算法递推算法精品精品PPT 设爬设爬k k级台阶的不同爬法为级台阶的不同爬法为f(k)f(k)种。种。（1 1）探求探求f(k)f(k)的递推关系。的递推关系。上山最后一步到达第上山最后一步到达第3030级台阶，共有级台阶，共有f(30)f(30)种不同的爬种不同的爬法；到第法；到第3030级之前位于哪一级呢？无非是位于第级之前位于哪一级呢？无非是位于第2929级级（上跳（上跳1 1级即到），有级即到），有f(29)f(29)种；或位于第种；或位于第2727级（上跳级（上跳3 3级级即到），有即到），有f(27)f(27)种；于是有种；于是有 f(30)=f(29)+f(27)f(30)=f(29)+f(27)一般地有一般地有递推关系递推关系：f(k)=f(k-1)+f(k-3)f(k)=f(k-1)+f(k-3)（k3k3）（2 2）确定初始条件确定初始条件f(1)=1f(1)=1；即；即1=11=1f(2)=1f(2)=1；即；即2=1+12=1+1f(3)=2f(3)=2；即；即3=1+1+13=1+1+1；3=33=31.递推设计递推设计要点要点2.2 2.2 经典算法经典算法递推算法递推算法精品精品PPT2.递推设计递推设计描述描述 printfprintf(请输入台阶总数请输入台阶总数n:);n:);scanfscanf(%(%d,&nd,&n););f1=1;f2=1;f3=2;/f1=1;f2=1;f3=2;/赋初值赋初值 for(k=4;k=for(k=4;k=n;kn;k+)+)fk=fk-1+fk-3;/fk=fk-1+fk-3;/实施递推实施递推 printfprintf(s=%(s=%ldld,fn);,fn);2.2 2.2 经典算法经典算法递推算法递推算法精品精品PPT2.3 2.3 经典算法经典算法递归算法递归算法n充分利用自己的充分利用自己的递归算法思想算法思想 在在计算机编程应用中，递归算法对解决大多数问题是十分计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下法有如下3个特点。个特点。（1）递归过程一般通过函数或子过程来实现。）递归过程一般通过函数或子过程来实现。（2）递归算法在函数或子过程的内部，直接或者间接地调用）递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。自己的算法。（3）递归算法实际上是把问题转化为规模缩小了的同类问题）递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解的子问题，然后再递归调用函数或过程来表示问题的解。精品精品PPT2.3 2.3 经典算法经典算法递归算法递归算法在使用递归算法时，读者应该注意如下在使用递归算法时，读者应该注意如下4点。点。（1）递归是在过程或函数中调用自身的过程。）递归是在过程或函数中调用自身的过程。（2）在使用递归策略时，必须有一个明确的递归结束条件，）在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。这称为递归出口。（3）递归算法通常显得很简洁，但是运行效率较低，所以一）递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。般不提倡用递归算法设计程序。（4）在递归调用过程中，系统用栈来存储每一层的返回点和）在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。提倡用递归算法设计程序。精品精品PPTl排队购票排队购票案例提出：案例提出：一一场场球球赛赛开开始始前前，售售票票工工作作正正在在紧紧张张进进行行中中。每每张张球球票票为为5050元元，有有m+nm+n个个人人排排队队等等待待购购票票，其其中中有有m m 个个人人手手持持5050元元的的钞钞票票，另另外外n n个个人人手手持持100100元元的的钞钞票票。求求出出这这m+nm+n个个人人排排队队购购票票，使使售售票票处处不不至至出出现现找找不不开开钱钱的的局局面面的的不不同同排排队队种种数数 。（约约定定：开开始始售售票票时时售售票票处处没没有有零零钱钱，拿拿同同样样面面值值钞钞票票的人对换位置为同一种排队。）的人对换位置为同一种排队。）2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT1.递归设计递归设计要点要点 令令f(f(m,nm,n)表示有表示有m m个人手持个人手持5050元的钞票，元的钞票，n n个人手持个人手持100100元的钞元的钞票时共有的排除总数。票时共有的排除总数。分以下分以下3 3种情况来讨论。种情况来讨论。(1)n=0(1)n=0 n=0 n=0意味着排队购票的所有人手中拿的都是意味着排队购票的所有人手中拿的都是5050元的钱币，注元的钱币，注意到拿同样面值钞票的人对换位置为同一种排队，那么这意到拿同样面值钞票的人对换位置为同一种排队，那么这m m个人个人的排队总数为的排队总数为1 1，即，即f(m,0)=1f(m,0)=1。(2(2）mnmn 当当mnmn时，即购票的人中持时，即购票的人中持5050元的人数小于持元的人数小于持100100元的钞票，元的钞票，即使把即使把m m张张5050元的钞票都找出去，仍会出现找不开钱的局面，这元的钞票都找出去，仍会出现找不开钱的局面，这时排队总数为时排队总数为0 0，即，即f(f(m,nm,n)=0)=0。2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT(3(3）其它情况）其它情况 1 1）第第m+nm+n个人手持个人手持100100元的钞票，则在他之前的元的钞票，则在他之前的m+n-1m+n-1个人个人中有中有m m个人手持个人手持5050元的钞票，有元的钞票，有n-1n-1个人手持个人手持100100元的钞票，此元的钞票，此种情况共有种情况共有f(m,n-1)f(m,n-1)。2 2）第第m+nm+n个人手持个人手持5050元的钞票，则在他之前的元的钞票，则在他之前的m+n-1m+n-1个人个人中有中有m-1m-1个人手持个人手持5050元的钞票，有元的钞票，有n n个人手持个人手持100100元的钞票，此元的钞票，此种情况共有种情况共有f(m-1,n)f(m-1,n)。由加法原理得到由加法原理得到f(f(m,nm,n)的递归关系：的递归关系：f(f(m,nm,n)=f(m,n-1)+f(m-1,n)=f(m,n-1)+f(m-1,n)初始条件：初始条件：当当mnmn时，时，f(f(m,nm,n)=0)=0 当当n=0n=0时，时，f(f(m,nm,n)=1)=12.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT 2 2.购票排队的递归描述购票排队的递归描述购票排队的递归描述购票排队的递归描述long f(long f(intint j,intj,int i)i)long y;long y;if(i=0)y=1;if(i=0)y=1;else if(ji)y=0;/else if(ji)y=0;/确定初始条件确定初始条件 else y=f(j-1,i)+f(j,i-1);/else y=f(j-1,i)+f(j,i-1);/实施递归实施递归 return(y);return(y);2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT2.4 2.4 经典算法经典算法分治算法分治算法n各个各个击破的分治算法思想破的分治算法思想 在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。精品精品PPT2.4 2.4 经典算法经典算法分治算法分治算法n各个各个击破的分治算法思想破的分治算法思想 使用使用分治算法解题的一般步骤如下所示。分治算法解题的一般步骤如下所示。（1）分解，将要解决的问题划分成若干个规模较小的同类问题；）分解，将要解决的问题划分成若干个规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。题的解。精品精品PPT2.5 2.5 经典算法经典算法贪心算法贪心算法n贪心算法思想并不心算法思想并不贪婪婪 贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题：（1）不能保证最后的解是最优的；（2）不能用来求最大或最小解问题；（3）只能求满足某些约束条件的可行解的范围。精品精品PPT2.5 2.5 经典算法经典算法贪心算法贪心算法贪心算法的基本思路如下所示。贪心算法的基本思路如下所示。（1）建立数学模型来描述问题；）建立数学模型来描述问题；（2）把求解的问题分成若干个子问题；）把求解的问题分成若干个子问题；（3）对每一子问题求解，得到子问题的局部最优解；）对每一子问题求解，得到子问题的局部最优解；（4）把子问题的解局部最优解合成原来解问题的一个解。）把子问题的解局部最优解合成原来解问题的一个解。实现该算法的基本过程如下所示。实现该算法的基本过程如下所示。（1）从问题的某一初始解出发；）从问题的某一初始解出发；（2）while能向给定总目标前进一步；能向给定总目标前进一步；（3）求出可行解的一个解元素；）求出可行解的一个解元素；（4）由所有解元素组合成问题的一个可行解。）由所有解元素组合成问题的一个可行解。精品精品PPT案例：可拆背包问题案例：可拆背包问题2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT/已对已对n n件物品按单位重量的效益降序排序件物品按单位重量的效益降序排序cwcw=c;sc;s=0;=0;/cwcw为背包还可装的重量为背包还可装的重量 for(i=1;i=for(i=1;i if(wicwcw)break;)break;xi=1.0;xi=1.0;/若若w(i)=w(i)w(i)cwcw,装入一部分装入一部分)s=s=s+ps+pi*xi;i*xi;3.贪心算法描述贪心算法描述 2.3 2.3 经典算法经典算法递归算法递归算法精品精品PPT2.6 2.6 经典算法经典算法试探法试探法n试探法算法思想是一种委婉的做法探法算法思想是一种委婉的做法使用试探算法解题的基本步骤如下所示。（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。试探法为了求得问题的正确解，会先委婉的试探某一种可能的情况。试探法为了求得问题的正确解，会先委婉的试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉的退回一步重新选择，然后继续向前试探，如此厥驴般的反复进行，自觉的退回一步重新选择，然后继续向前试探，如此厥驴般的反复进行，直至得到解或证明无解时才死心。直至得到解或证明无解时才死心。精品精品PPT2.7 2.7 经典算法经典算法迭代法迭代法 迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点。在使用迭代算法解决问题时，需要做好度快、适合做重复性操作的特点。在使用迭代算法解决问题时，需要做好如下三个方面的工作。如下三个方面的工作。（1）确定迭代变量）确定迭代变量在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。接地不断由旧值递推出新值的变量。（2）建立迭代关系式）建立迭代关系式迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。决迭代问题的关键。（3）对迭代过程进行控制）对迭代过程进行控制精品精品PPT2.7 2.7 经典算法经典算法迭代法迭代法 在在编写迭代程序时，必须确定在什么时候结束迭代过程，编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：情况来控制迭代过程：所需的迭代次数是个确定的值，可以计算出来。可以构建一所需的迭代次数是个确定的值，可以计算出来。可以构建一个固定次数的循环来实现对迭代过程的控制；个固定次数的循环来实现对迭代过程的控制；所需的迭代次数无法确定，需要进一步分析出用来结束迭代所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。过程的条件。精品精品PPT2.8 2.8 经典算法经典算法动态规划算法动态规划算法动态规划的概念动态规划的概念(1)动态规划（动态规划（Dynamic programming）是运筹学的一个分支，是求解决策）是运筹学的一个分支，是求解决策过程最优化的数学方法。过程最优化的数学方法。(2)动态规划处理的对象是多阶段决策问题。动态规划处理的对象是多阶段决策问题。(3)多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。精品精品PPT2.8 2.8 经典算法经典算法动态规划算法动态规划算法动态规划的步骤：动态规划的步骤：（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。结构特性。（2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。间的递推关系，并确定初始条件。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。（3）应用递推求解最优值。）应用递推求解最优值。递推计算最优值是动态规划算法的实施过程。递推计算最优值是动态规划算法的实施过程。（4）根据计算最优值时所得到的信息，构造最优解。）根据计算最优值时所得到的信息，构造最优解。构造最优解就是具体求出最优决策序列。构造最优解就是具体求出最优决策序列。精品精品PPT2.9 2.9 经典算法经典算法模拟算法模拟算法n模拟算法思想模拟算法思想模拟算法是一种最基本的算法思想，是对程序员基本编程能力的一种考查，模拟算法是一种最基本的算法思想，是对程序员基本编程能力的一种考查，其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的理解。我们知道在理解。我们知道在C语言中，通常使用函数语言中，通常使用函数srand()和和rand()来生成随机数。来生成随机数。其中函数其中函数srand()用于初始化随机数发生器，然后使用函数用于初始化随机数发生器，然后使用函数rand()来生成随机来生成随机数。如果要使用上述两个函数，则需要在源程序头部包含数。如果要使用上述两个函数，则需要在源程序头部包含time.h文件。文件。在程序设计过程中，可使用随机函数来模拟自然界中发生的不可预测情况。在程序设计过程中，可使用随机函数来模拟自然界中发生的不可预测情况。在解题时，需要仔细分析题目给出的规则，要尽可能地做到全面地考虑所有在解题时，需要仔细分析题目给出的规则，要尽可能地做到全面地考虑所有可能出现的情况，这是解模拟类问题的关键点之一。可能出现的情况，这是解模拟类问题的关键点之一。精品精品PPT2.10 算法的综合举例v案例提出案例提出v给定由定由n n个整数（可能有个整数（可能有负整数）整数）组成的序列成的序列a(1),a(2),a(1),a(2),a(n),a(n)（约定：定：n n个整数中至少存在一个正个整数中至少存在一个正整数）整数）,求求该序列的子段和的最大序列的子段和的最大值，并确定最大子段，并确定最大子段的位置。的位置。v分分别应用枚用枚举、递归与与动态规划三种算法求解。划三种算法求解。精品精品PPT1.枚举求解（1 1）枚举设计要点枚举设计要点 设序列子段的首项为设序列子段的首项为i(1i(1n)n)，尾项为，尾项为j(ij(in)n)，该子，该子段和为段和为s s。设置。设置i,ji,j二重循环枚举，可确保所有子段既不重复也不二重循环枚举，可确保所有子段既不重复也不遗漏。遗漏。每一子段和每一子段和s s与最大变量值与最大变量值smaxsmax比较，可得最大子段和，同比较，可得最大子段和，同时应用变量时应用变量i1,j1i1,j1分别记录最大子段的首尾标号。分别记录最大子段的首尾标号。最后输出最大子段和最后输出最大子段和smaxsmax，同时输出最大子段的位置，同时输出最大子段的位置i1,j1i1,j1。精品精品PPT input a1:n input a1:n smaxsmax=0;=0;for(i=1;i=for(i=1;i=n;in;i+)+)s=0;s=0;for(j=for(j=i;ji;j=if(ssmaxsmax)smaxsmax=s;i1=i;j1=j;=s;i1=i;j1=j;print(i1:j1,smax)print(i1:j1,smax)（2 2）枚举设计描述枚举设计描述精品精品PPT2.2.递归求解递归求解递归求解递归求解精品精品PPT精品精品PPT精品精品PPT3.动态规划求解动态规划求解精品精品PPT/输入序列中输入序列中n n个正负数个正负数 b0=0;smax=0;b0=0;smax=0;for(j=1;j=for(j=1;j=n;jn;j+)+)if(bj-1=0)bj=aj;/if(bj-1 if(bjsmaxsmax)/)/比较得比较得bjbj的最大值的最大值 smaxsmax=bj;k=j;/=bj;k=j;/记录最大和子段尾标记录最大和子段尾标j j printfprintf(n (n 最大子段和为：最大子段和为：%ldldn,n,smaxsmax););（2）动态规划设计描述动态规划设计描述精品精品PPT4.三种求解算法的时间复杂度三种求解算法的时间复杂度 精品精品PPT3 3 简单的数据结构知识简单的数据结构知识学学习编程的注意事程的注意事项（1）在学习知识之前要有足够的理解，也就是说盖房打地基之前要先有一个大概的了解、规划。（2）做什么事情都有捷径可寻，但是有时候，在学习编程的过程中走捷径并不是一件很好的事情精品精品PPT3.13.1 线性表线性表n线性表线性表的特性的特性线性表是一个线性结构，它是一个含有n0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且仅有一个前驱和一个后继节点。n线性结构的特征线性结构的特征在编程领域中，线性结构具有如下两个基本特征。（1）集合中必存在唯一的一个“第一元素”和唯一的一个“最后元素”；（2）除最后一个元素之外，均有唯一的后继(后件)和唯一的前驱(前件)；由n(n0)个数据元素(节点)a1，a2，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表，我们通常将非空的线性表(n0)记作：(a1，a2，an)数据元素ai(1in)没有特殊含义，大家不必去“剖根问底”的研究它，它只是一个抽象的符号，其具体含义在不同的情况下可以不同。精品精品PPT3.1 线性表性表n线性表线性表的基本操作过程的基本操作过程线性表虽然只是一对一的单挑，但是其操作功能非常强大，具备了很多操作技能。n线性表线性表的结构特点的结构特点均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度；有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。精品精品PPT3 3 简单的数据结构知识简单的数据结构知识在现实应用中，有两种实现线性表数据元素存储功能的方法，分别是顺序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法，此方式的主要操作功能如下所示。（1）计算顺序表的长度（2）清空操作（3）判断线性表是否为空（4）判断顺序表是否为满（5）附加操作（6）插入操作（7）删除操作（8）获取表元（9）按值进行查找精品精品PPT3 3 简单的数据结构知识简单的数据结构知识链表操作链表操作链比顺序表要复杂一点，对于同一个数据，它可以和不相邻的数据发生关系。例如农民通常将收获的水果卖给商贩，商贩将收购的水果卖给加工厂。这是一条水果加工产业链，可以得出商贩是农民的财神、加工厂是商贩的财神这一论调。在那一年的某一天，老实的农民发现利润较低，于是拉着自己的水果不远万里的亲自卖给了加工厂。这样农民伯伯获得了更大的利润，而商贩也不能怎么着，这个产业链还得继续下去。由此可见，链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无需移动元素就而提高了运行效率。链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。精品精品PPT3 3 简单的数据结构知识简单的数据结构知识3.3 守守规矩的先矩的先进先出的先出的队列列3.3.1 队列基础队列基础队列和栈一样，只允许在断点处插入和删除元素，循环队的入队算法如下所示。（1）tail=tail+1；（2）如果tail=n+1，则tail=1；（3）如果head=tai，即尾指针与头指针重合，则表示元素已装满队列，会施行上溢出错处理；否则Q(tail)=X，结束整个过程，其中X表示新入出元素。3.3.2 链队列和循环队列链队列和循环队列使用C语言定义链队列的格式如下所示。typedef struct QNodeElemTypedata;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/*队头指针，指向头元素*/QueuePtr rear;/*队尾指针，指向队尾元素*/LinkQueue;精品精品PPT3 3 简单的数据结构知识简单的数据结构知识3.3.3 队列的基本操作队列的基本操作（1）初始化队列Q的目的是创建一个队列（2）入队的目的是将一个新元素添加到队尾，相当于到队列最后排队等候。（3）出队的目的是取出队头的元素，并同时删除该元素，使后一个元素成为队头。（4）获取队列第1个元素，即将队头的元素取出，不删除该元素，队头仍然是该元素。（5）判断队列Q是否为空3.3.4 队列的链式存储队列的链式存储当使用链式存储结构表示队列时，需要设置队头指针和队尾指针，这样做的好处是可以设置队头指的针和队尾的指针。在入队时需要执行如下三条语句。s-next=NULL;rear-next=s;rear=s;在C语言中，实现队列链式存储结构类型的代码如下所示。type struct linklist /链式队列的节点结构Elemtype Entry;/队列的数据元素类型struct linklist*next;/指向后继节点的指针LINKLIST;typedef struct queue/链式队列LINKLIST*front;/队头指针LINKLIST*rear;/队尾指针QUEUE;精品精品PPT3 3 简单的数据结构知识简单的数据结构知识3.4 后后进先出的先出的栈3.4.1 什么是栈什么是栈栈允许在同一端进行插入和删除操作，允许进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。栈底是固定的，而栈顶浮动的；如果栈中元素个数为零则被称为空栈。插入操作一般被称为进栈（PUSH），删除操作一般被称为退栈（POP）。在栈中有两种基本操作，分别是入栈和出栈。（1）入栈（Push）将数据保存到栈顶。在进行入栈操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。入栈（Push）操作的算法如下：如果TOP，则给出溢出信息，作出错处理。在进栈前首先检查栈是否已满，如果满则溢出；不满则进入下一步骤；设置TOP=TOP+1，使栈指针加，指向进栈地址；S(TOP)=X，结束操作，X为新进栈的元素。（2）出栈（Pop）将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。出栈