《算法及其设计基础》PPT课件.ppt

第1章 算法及其设计基础,教学目的和要求 了解算法描述的基本要求和目的，掌握用自然语言方式、流程图方式、盒图(N-S图)、 伪代码方式、PAD图方式和计算机语言方式来描述一个算法。 重点： 流程图方式、盒图(N-S图)、PAD图方式。 难点： 完整地用盒图(N-S图)来描述一个算法。,1.1 引言,程序设计方法首先强调的是设计，其次才是实现（写出程序代码）。其核心是将程序设计过程分为两部分。 第一部分集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。 第二部分集中于选择某一种程序设计语言，把算法表达给特定的计算机。,1.2 算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 你想查看计算机CPU，首先必须将计算机断电，拆除连线，打开机箱，然后按下夹子解除夹口，最后取出CPU进行查看。 复制文件，首先要寻找所要复制的文件，然后选中，再进行复制，最后移动到需要的地方进行粘贴。,计算机算法的分类： 本书所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。 计算机算法可分为两大类别：数值运算算法和非数值运算算法。 数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。 非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。,1.3 算法的特性,一个算法应该具有以下几个特性： 有穷性 确定性 输入 输出 有效性,1.3 算法的特性,1）有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 但是要注意，“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时几百年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们也不把它视做有效算法。究竟什么算“合理限度”，并无严格标准，由人们的常识和需要而定。,确定性 算法中的每一个步骤，必须是确切定义的，而不应当含糊不清或模棱两可的。即算法的含义应当是唯一的，而不应当产生“歧义性”。 例如，某人只说请您“复制文件”或查看计算机的CPU，是不确定的，因为此人没有说明复制哪一个文件或查看哪一台计算机的CPU。,1.3 算法的特性,输入 所谓输入是指在执行算法时需要从外界取得必要的信息。 例如，让计算机来完成“将N个正数按从小到大的次序排列”时，就需要输入N个正整数。一个算法可以有多个输入，也可以没有输入。,1.3 算法的特性,输出 算法执行过程中往往会产生一些数据，它们在算法执行之后被保存下来或传递给算法的调用者，这些数据被称为算法的输出。 一个算法可以有多个输出，没有输出的算法是没有意义的。 例如，计算机来完成“将N个整数按从小到大的次序排列”的算法时，输出的整数将是一组“从小到大的次序排列的N个整数”。,1.3 算法的特性,有效性 一个算法应该是具有现实意义的，如果算法中含有不能实现的某一个步骤，则这个所谓的“算法”无法解决问题，因此，不能称为算法。 算法贯穿于程序设计的始终，希望读者对算法给予很大的重视，在解决一个问题之前应当首先构造出一个好的算法。在本书各章中都贯穿这一原则。,1.3 算法的特性,1.4 算法的结构,1966年，计算机科学家Bohm和Jacopini的研究表明，任何简单或复杂的算法都可以由下述3种基本控制结构组成。 1）顺序结构 2) 选择结构 3) 循环结构,1）顺序结构,这是最简单的一种基本结构。顺序结构中的各个部分是按书写顺序依次执行的。例如某个算法中可能出现下列形式的一组操作： 操作 1 操作 2 操作 3 如果这样一组操作的执行顺序与操作出现的前后顺序相同，即先进行“操作1”，然后进行“操作2”，再后进行“操作3”，那么这段算法的结构就是顺序结构。,2) 选择结构,这种结构也称为分支结构，它表示操作的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支执行。例如下述算法描述片段： 如果 成立 则执行 否则执行 和 之间构成了一种选择关系，两个操作中哪一个将被执行是通过对 的判断来控制的。,3) 循环结构,循环结构是指被重复执行的一个操作集合。例如下述算法描述片段： 重复执行 直到 不成立 这段描述指出 将被反复运行多次，直到 不成立为止。,注意： 通过上述三种基本控制结构可以看到，它们有一个共同的特点，即：只有一个入口且只有一个出口，并且操作不会出现死循环。,1.5 算法的描述,算法的描述具有重要意义，描述一个算法的目的在于使其他人能够利用算法解决具体问题。 算法的描述方式没有统一规定，本书将介绍常用的自然语言、流程图、N-S图、PAD图、伪代码以及计算机语言等六种描述算法的方式。 注意： 不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。,1.5.1 自然语言方式,自然语言就是人们日常使用的语言，可以是汉语、英语或其他任何形式的语言。,算法可以表示如下： 第1步 使sign=1（sign代表数值的符号） 第2步 使sum1（sum代表累加和变量） 第3步 使deno=2（deno代表分母变量） 第4步 sign(-1)*sign（求级数中各项的符号，它的值为l或-1） 第5步 termsign*(1/deno) （term代表级数中的某一项） 第6步 sum=sum+term 第7步 deno=deno+l 第8步 若deno20，转去执行第4步以及其后的各个步骤；否则 执行第9步 第9步 打印sum的值（即所求之总和） 第10步 算法结束,例1.1 求,例1.2 用选择排序法，将N个正整数数列按照从小到大 的顺序排列。 选择排序法基本思想：在选择排序方法中，第一步在N个元素中选出最小元素，将其与第一个元素交换。第二步从剩下的N-1个元素中选出最小元素，将其与第二个元素交换，如此下去，直到剩下最后两个元素。,输入：将N个正整数放置在数组aN中。 第1步 使i=1 第2步 若iN-1，执行第3步；否则转第10步 第3步 使k=i，顺次执行第4步 第4步 使j=i+1，顺次执行第5步 第5步 若jN，执行第6步；否则转第8步 第6步 若ajak，则置k为j，然后顺次执行第7步；否则 直接执行第7步 第7步 使j=j+1，转第5步 第8步 若i!=k交换ai和ak的值(置t为 ai,ai为 ak， ak为 t )，顺次执行第9步；否则直接执行第9步 第9步 使i=i+1，转第2步 第10步 输出a1aN 第11步 算法结束,算法可以表示如下：,自然语言方式的优缺点： 用自然语言表示通俗易懂，但文字冗长，容易出现歧义性。 用自然语言描述的算法通用性差。例如，用汉语描述的算法只适合于懂得汉语的人，而用英语描述的算法也只能适合于懂得英语的人。 基于上述原因，除了很简单的问题以外，一般不用自然语言描述算法。,1.5.2 流程图方式,流程图是20世纪40年代末出现的一种描述算法或程序的工具，其特点是用一些图框表示各种类型的操作，用线表示这些操作的执行顺序。,图例中各结点的意义：,端点符：表示算法由此开始或结束。 处理框：表示一般的处理功能，应在框中对该功能进行简单标记和说明。 判断框：表示判断操作，应该在框中标明判断条件。此框具有两个或两个以上出口，在每个出口处标明出口的条件。 预定义功能框：代表未详细说明的一个或一组操作，通常用来表示调用一个已知的算法或函数，框中标明这个算法或函数的名字或入口地址。 连接符：表示连结点，框中标有数字。当流程图较复杂或分布在多张纸上时，用连接符表示各图之间的联系，相同符号的连接符是相互连接的（如图1.2所示）。 注释框：注释框不反映流程和操作，只是为了对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。,端点符,处理框,输入输出框,预定义功能框,判断框,流程线,连接符,图 1.1 流程图常用图形符号,使用流程图表示的顺序型、选择型、当型循环和直到型循环等四种基本控制结构如图1.3所示。,条件,处理2,处理1,顺序结构,处理2,处理,N,当型循环,直到型循环,选择结构,处理,条件,条件,Y,Y,N,处理,图 1.3 四种基本控制结构,N,Y,使用流程图表示的顺序型、选择型、当型循环和直到型循环等四种基本控制结构：,例1.3 求,的流程图如图1.4所示,例1.4 将N个正整数数列按照从小到大的顺序排列的算法用流程图表示。,流程图描述算法的不足之处?,随意地使用箭头控制算法的执行流程，从而造成算法的层次结构混乱。 降低了程序的可读性和可维护性。 不适于自顶向下、逐步求精的程序开发方式。,使用程序流程图描述算法，具有简捷、直观、使用方便的特点。,流程图特点:,1.5.3 盒图(N-S图)方式,出于要有一种不允许违背结构化程序设计思想的图形工具的考虑，1973年美国学者Nassi和Shneiderman提出了一种新的流程图形式,称为盒图（box diagram）,又称为N-S图。 在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框。 N-S图十分适合描述结构化程序或算法的结构化实现，能够较好地反映算法和程序的层次结构，可读性好，具有自顶向下逐步求精的特征。,N-S 图基本符号以及控制结构的描述方法,例1.5 求,图 1.7 N-S图描述,的N-S图表示。,例1.6 将N个正整数数列按照从小到大的顺序排列的N-S图描述,1.5.4 PAD图方式,PAD图是问题分析图（problem analysis diagram）的英文缩写，1973年由日本日立公司的二才 良彦等提出，是另一种可以用于算法和程序描述的图形工具。 PAD图用二维树型结构的图来表示程序的控制流，即可以用于表示程序中操作的逻辑顺序，也可用于表示数据结构，是一种结构化程序设计描述工具，适用于自顶向下、逐步求精的程序开发方法。,PAD图的符号及控制结构如图1.9和表1.1所示。,表1.1 PAD图的图形符号,例1.7求,的PAD图描述算法,例1.8 将N个正整数数列按照从小到大的顺序排列。,图1.11 PAD图描述,1.5.5 伪代码方式,伪代码(pseudo code)就是程序设计语言的控制结构和其他一些元素的速记符号。一般来说，伪代码的语法规则分为“外层语法”和“内层语法”。 外层语法类似于一般编程语言控制结构的关键字，比较严格。 内层语法则是灵活自由的，可以用自然语言，也可用程序设计语言，或使用自然语言与程序设计语言的混合体，以便使用于不同工程项目的需要。 伪代码不用图形符号，因此书写方便、格式紧凑，也比较好懂，便于转换成计算机高级语言(即程序)。,1) 层次,算法的书写应该具有层次，下面的一层采用缩进方式，同层次的缩进相同，例如： X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X,本书伪代码构成元素和书写规则如下：,2) 注释,其形式是由()括起来的中文或英文字符串。 3) 3种控制结构 (1) 顺序结构 书写格式如下： ,(2) 分支结构,有以下两种书写格式： 格式1： if() then else 格式2： if() then 多重选择的格式如下： ，执行 ，执行 ，执行,（3）循环结构,有以下三种书写格式： 格式l：do while() 格式2：while() do 格式3：for to 步长 ,4) 调用算法,书写方式如下： 调用() 5) 需要标明算法的“BEGIN(开始)”和“END(结束)”点。,例1.9 求,BEGIN sign=1（sign代表数值的符号） sum=1（sum代表累加和变量） deno=2（deno代表分母变量） while deno20 sign=(-1)*sign（求级数中各项的符号,它的值为l或-1） term=sign*1/deno（term代表级数中的某一项） sum=sum+term deno=deno+1 print sum（所求之总和） END,例1.10 将N个正整数数列按照从小到大的顺序排列。,BEGIN for i=1 to N-1 (每循环一次在未排序元素中找出一个最小的元素进行排序) k=i for j=i+1 to N（查找未排序元素中的最小的元素） if( ajak) then k=j if( ik ) then t=ai; ai=ak; ak=t; END,伪代码书写格式比较自由，可以随手写下去，容易表达出设计者的思想。 用伪代码写的算法很容易修改，例如增加一行、删除一行或将后面某一部分调到前面某一位置，都是很容易做到的。 用伪代码很容易写出结构化的算法。 用伪代码写算法不如流程图和N-S图直观，可能会出现逻辑上的错误。,1.5.6 计算机语言方式,前几节我们用自然语言方式、伪代码方式、流程图方式、N-S图方式、PAD图等5 种不同的方式描述了算法，用计算机语言（包括低级语言和高级语言）编写的程序也是算法的表示形式。 用计算机语言表示算法必须严格遵循所用语言的语法规则，这是与其它描述方式不同的。本书中将用C程序设计语言表示算法。,例1.11 求,main() int sign=1; float deno=2.0,sum=1.0,term; clrscr(); while(deno=20) sign=-sign; /* 求级数中各项的符号,值为l或-1 */ term=sign/deno; /* term代表级数中的某一项 */ sum=sum+term; deno=deno+1; printf(“sum=%fn“,sum); 程序运行结果： sum=0.668771,#define N 10 main() int i,j,k,t; int aN; printf(“input %d number:n“,N); for(i=0;iN;i+) printf(“a%d=“,i); scanf(“%d“, ,例1.12 将N个正整数数列按照从小到大的顺序排列。,程序运行结果： input 10 number: a0=13 a1=19 a2=22 a3=55 a4=66 a5=88 a6=11 a7=77 a8=55 a9=1 1 11 13 19 22 55 55 66 77 88,我们可以直接使用某种程序设计语言（如C程序设计语言或C+程序设计语言）来描述算法，不过直接使用程序设计语言不是很容易，而且不太直观，并常常需要借助注释才能使人看明白。,1.6 关于计算机算法的评价,关于一个计算机算法的好坏可用下面几个指标来衡量： 1）程序的可读性好 2）提高收敛速度 3）节省计算时间 4）节省存储空间 5）增强数值稳定性,1）程序的可读性好 在早期使用程序设计语言编程的时候，尤其是在使用汇编语言编程的时候，人们有这样一种认识，那就是程序只是给机器执行的，而不是供人阅读的。基于这一想法，人们往往采用一些编程技巧，从而造成算法难以理解，编程更加困难，程序不易阅读，也不便于程序的测试和维护。 20世纪70年代初，人们开始注意在编写程序时注意应该使程序具有良好的风格。这样使得今后有人阅读这个程序时能比较方便地沿着你的思路去理解程序的功能，从而使程序的可读性增强，方便了测试与维护。,2）提高收敛速度 对于一个迭代过程来说，理论上讲需要无限多步的计算才能得到某个量的真值，实际操作中采用的方法是根据精度要求决定是否停止进一步的计算。所以计算时间既与选定的方法有关，还与要求达到精度有关，用计算量来评估并不适宜。,3）节省计算时间 尽管现在计算机的运算速度极快，但是对于一些复杂的大规模问题求高精度数值解来说，最后折算成所需要进行的四则运算次数也是相当多的，所需要的计算时间也很多。通常我们使用机器完成一次浮点数的乘法或除法运算连同一次加法或减法运算的计算量作为评估计算量的计量单位。 现在由于CPU的运算速度以及数据总线的位数都得到了明显的改善，因此，这个问题的重要性现在已经大大降低了。但是，对于一些问题而言，设计算法时应该考虑节省计算的时间。,4）节省存储空间 节省存储空间有两层含义，第一层含义是指算法简单，因而程序就短，程序本身所占用的存储空间便少；另一层含义是指所需要保留的中间结果比较少，这样就可以省下为了保留中间结果所需要的额外的存储空间。 自20世纪90年代以来，计算机的机器字长，数据总线的位数，以及存储器的容量等都得到了明显的改善。因此，这个问题的重要性现在已经大大降低了。,5） 增强数值稳定性 对于某个数值算法，如果输入数据的误差，在计算过程中不断扩大而难以得到控制，则称该算法是数值不稳定的，否则是数值稳定的。 如果某算法在一定的条件下才是稳定的，则称该算法是条件稳定（相对稳定）的；若在任何条件下，某算法是稳定的，则称该算法是无条件稳定（绝对稳定）的。 误差的传播能否得到控制，是误差分析的重要内容，也是衡量一个算法优劣的一个重要标志，可以用算法的数值稳定性表示误差传播的控制。,1.7 常用算法设计及其实现,下面我们将介绍几种典型的方法，这些方法有一定的使用价值，但更重要的是为了使初学者容易理解算法，从而逐步掌握根据算法编写程序的方法。,1.7.1 排序算法及其实现,排序是将一个无序的数据序列按照某种顺序（升序或降序）重新排列的过程。例如，将一批杂乱无序的学生成绩按高分到低分的顺序排列。,1.7 常用算法设计及其实现,例 1.13 用冒泡排序法将N个正整数，按照从小到大的顺序排序。 冒泡排序法基本思想是将相邻两个数比较，把大数往后移，如图1.12所示的过程就是冒泡处理的形象过程。,6 6 6 6 6 6 6 8 8 8 4 4 4 4 4 4 4 8 7 7 7 7 7 7 7 8 2 2 2 2 2 2 2 8 5 5 5 5 5 5 5 8 第1次 第2次 第3次 第4次 第5次 结果 6 6 4 4 4 4 4 4 6 6 6 6 7 7 7 7 2 2 2 2 2 2 7 5 5 5 5 5 5 7 第1次 第2次 第3次 第4次 结果 图1.12 冒泡排序法第一趟比较和第二趟比较的示意,值得注意的是: 如果在一趟比较中没有数据的交换，说明所有的数据都已经从小到大排好了序，因此可以提前退出循环。为此，程序中设置exchange为交换标志，在一趟比较中数据进行了交换exchange置为1，没有进行数据交换exchange置为0，即可退出循环。其N-S图，如图1.13所示。,图 1.13 N-S图描述,#include #define N 6 main() int i,j,t,exchange; int aN+1; /* aN用于存放 */ printf(“input %d number:“,N); for(i=0;iaj+1) /* 顺序不符合要求时交换位置 */ t=aj; aj=aj+1; aj+1=t; exchange=1; if (!exchange) break; /* 若所有的元素都已排好序，则退出循环 */ for(i=0;iN;i+) printf(“%4d“,ai); printf(“n“); ,程序运行结果： input 6 number: 6 8 4 7 2 5 6 8 4 7 2 5 2 4 5 6 7 8,1.7.2 查找算法及其实现,在处理大量数据时，经常要按某种方法找出所需的数据，这个过程称为查找。 例如，在学生成绩中查找某位学生的成绩等。查找方法很多，下面将以例1.14为例介绍常用的顺序查找法。,例 1.14 编写一个程序，在给定的数组a中查找用户输入的值，并提示相应的查找结果。 顺序查找法基本思想是：从数组第一个元素开始，顺序扫描数组，依次将扫描元素和给定值x相比较，若当前扫描元素与x相等，则查找成功；若扫描结束后，仍未找到等于x的元素，则查找失败。,例 1.14 编写一个程序，在给定的数组a中查找用户输入的值，并提示相应的查找结果。,#define N 10 main() int a=6,3,9,8,1,5,4,10,2,7; int i=0,x; printf(“input x=“); scanf(“%d“, ,程序运行结果： input x=8 find 8 it position is :a3=8 input x=99 99 not been found,1.7.3 穷举算法及其实现,在循环算法中，穷举法是具有代表性的基本算法，穷举的基本思想是，对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试过为止。,例 1.15 编写一个程序，求这样四位数：该四位数的千位上的数字和百位上的数字都被擦掉了，知道十位上的数字是1，个位上的数字是2，又知道这个数如果减去7就能被7整除，减去8就能被8整除，减去9就能被9整除。 设这个数为n=abl2，则n=lOOO*a+lOO*b+lO+2，且有0a9，0b9。,main() int n,a,b; for(a=1;a=9;a+) for(b=0;b=9;b+) n=1000*a+100*b+10+2; if(n-7)%7=0 程序运行结果： n=1512