第4章 计算的灵魂--算法和程序设计

第4章算法与程序设计,河北农业大学信息科学技术学院,主要内容,为什么做,平凡不美,4.1问题求解与算法,在日常生活中，我们做事情都要遵循一定的顺序步骤。比如我们在商场买一台笔记本，顺序是这样的：,有些步骤的前后顺序是不能改变的，就如同我们必须“先穿袜子后穿鞋”一样，实际上，这就是生活中的“算法”。一道菜的做法，就是该“菜的算法”。,平凡不美,4.1.1计算机处理问题的顺序,平凡不美,4.1.2问题求解,刚才提到的最多的一个词语就是顺序！因为计算机问题求解的核心就是顺序性，在计算机里所有的程序都是顺序执行，所以对任何需要解决的问题进行顺序安排变得异常重要。,以“西红柿炒蛋”为例，让我们看一下做这道菜的步骤。（S1是Step1的缩写，依次类推）S1：把西红柿和鸡蛋清洗干净S2：西红柿去掉蒂部，切成块S3：鸡蛋加点盐打散S4：锅里放油，油热后倒入鸡蛋液S5：炒鸡蛋的同时，用铲子把鸡蛋捣成碎块，炒好后盛出备用S6：锅里放入少量油，油热倒入西红柿煸炒S7：西红柿变软开始出汁时改成小火，放入白糖和盐，一边熬出汤汁一边用铲子捣碎。S8：放进提前炒好的鸡蛋，混合均匀关火。,问题：那么，我要求你来准备一个晚宴，你该如何进行问题求解呢？,平凡不美,4.1.3算法定义,Q:什么是算法通俗地讲，算法(Algorithm)是步骤和描述,【例】交换酱油和醋两瓶调料。问题描述：有两瓶调料，分别标明的是“酱油”和“醋”。但由于工人疏忽，将瓶子灌装错了，现在要求将其交换回来。,解决思路：设目前“酱油”瓶为1号瓶，它里面装的实际是醋；设目前“醋”瓶为2号瓶，它里面装的实际是酱油；设空瓶为3号瓶。算法描述：S1：将1号瓶中的醋倒入3号瓶S2：将2号瓶中的酱油倒入1号瓶S3：将3号瓶中的醋倒入2号瓶,平凡不美,4.1.4算法的分类和特性,算法的分类,平凡不美,4.1.5算法举例,【例】判定20002500年中的每一年是否是闰年，将结果输出。,解决思路：闰年的条件是能被4整除，但不能被100整除的年份都是闰年，如1996年，2004年；能被100整除，又能被400整除的年份是闰年，如1600年、2000年。不符合这两个条件的年份都不是闰年。算法描述：设y为被检测的年份，可采用以下步骤：S1：输入：y2000S2：若y不能被4整除，则输出y“不是闰年”。然后转到S6S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6S4：若y能被100整除，又能被400整除，输出y“是闰年”；否则输出“不是闰年”。然后转到S6S5：输出y“不是闰年”S6：y+1=yS7：当y2500时，转S2继续执行，如y2500，算法停止,平凡不美,4.1.6算法描述,一个问题可以设计不同的算法来求解，而同一个算法可以采用不同的形式来表述，常用的描述方法有以下几种：,【例】用自然语言描述计算并输出z=xy的流程：（1）输入变量x，y；（2）判断y是否为0；（3）如果y=0，则输出出错提示信息；（4）否则计算z=x/y；（5）输出z。,【例】用传统流程图表示：输入x、y，计算z=xy，输出z。,平凡不美,4.1.6算法描述,【例】用伪代码描述：输入x、y，计算z=xy，输出z。（1）Begin/*算法伪代码开始*/（2）输入x，y/*输入变量x、y*/（3）ify=0thenError转到（6）/*判断如果y为0，则输出错误提示，并转到（6）*/（4）elsezx/y/*否则计算xy，并赋值给z*/（5）输出z/*输出z的值*/（6）End/*算法伪代码结束*/,【例】输入x、y，计算z=xy，输出z的计算机C语言描述形式。floatdiv(floatx,floaty)floatz;if(y=0)printf(“Error!n”);elsez=x/y;returnz;,平凡不美,4.1.7流程图,在上述算法描述中，最常用到的就是传统流程图。以特定的图形符号加上说明，表示算法的图，称为流程图。有时也称作输入-输出图。流程图使用一些标准符号代表某些类型的动作。,平凡不美,1S,Visio,流程图软件,Raptor,Word,1、Visio属于OFFICE系列，功能全面，推荐大家使用。2、Raptor是一种基于流程图的可视化程序设计环境。推荐有一定编程基础的同学使用。3、Word可以做基本的流程图，最容易上手。,4.1.8流程图常用的制作软件,4.1.9算法的评价和算法复杂度,解决某一问题存在多种算法，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，那怎样才算是一个优秀的算法呢？一般有这么几个标准：（1）正确性（2）可读性（3）健壮性（4）效率,以效率标准举例：【例】9个外观一样的金币.，其中一个赝品重量较轻。如果用天平秤鉴别真伪，一共需要称几次？算法1：天平左边金币固定，不断变换右边金币，最多称7次可鉴别出假币。算法2：天平两边各一个金币，每次变换两边金币，最多称4次可鉴别出假币。算法3:：天平左边3个，右边3个，留下3个，最多称2次可以鉴别出假币。,为了更公平的比较和衡量算法质量的优劣程序，需要一个客观的标准，这个标准就是著名计算机科学家，算法分析之父高德纳提出的算法复杂度。,平凡不美,1S,算法描述了问题处理的方式或步骤，程序则是采用具体语言规则实现了算法的功能，算法要依靠程序来完成功能，算法是程序的灵魂；,4.2程序和程序设计,问题：什么是计算机程序？,程序是计算机解决实际问题的计算步骤。它是有始与有终的闭环，有选择，有循环，有过程，有函数等，算法是程序的核心。,平凡不美,1S,程序设计语言是随着计算机软硬技术的发展而产生和发展的，每一种程序设计语言都有着各自的特点。,4.2.1程序设计语言,平凡不美,1S,程序设计是借助一定工具（编程环境）利用计算机解决实际问题的全过程。包括建立模型，数据组织，设计算法，程序实现，上机调试，结果反馈及算法分析的全过程。可以用三阶段六步骤来进行概括。,4.2.2程序设计的一般过程,平凡不美,1S,结构化的程序设计就是把一个程序分成若干互相独立的模块。基本要点：（1）自上而下，逐步细化将复杂的大问题逐步分解多个简单的小问题。（2）模块化设计一个程序是由一个主控模块和若干个字模块组成的。（3）结构化编码,4.2.3程序的控制结构,结构化程序是由若干个基本结构组合而成，每一个结构可以包含若干条语句和其它基本结构。共有三种基本结构，即顺序结构，选择结构和循环结构。下面我们通过几个连贯性实例来讲解这三种基本结构,平凡不美,1S,4.2.4程序的控制结构,1.顺序结构顺序结构是最简单的程序结构，也是最常用的程序结构，只要按照解决问题的顺序写出相应的语句就行，它的执行顺序是自上而下，依次执行。,问题1:你会吃蟹黄汤包吗?,轻轻提,慢慢移,先开窗,再喝汤。,平凡不美,1S,4.2.4程序的控制结构,吃一只蟹黄汤包的“算法”,顺序很重要：将包子从蒸笼中轻轻提起，andthen将包子慢慢移动到面前的小碟子中，andthen在包子的正上方咬开一个小口，andthen通过小口吸食包子里的汤(当心别烫着)，andthen将包子送入口中。完成！,平凡不美,1S,4.2.4程序的控制结构,2.选择结构选择结构用于判断给定的条件，根据判断的结果来控制程序的流程。,问题2:如何确保过程无误，以免烫伤?,解决方案：假如我们认为在步骤4和5执行前要确保步骤3的结果是正确的，可以在相应的地方设个“监视哨”“guard”。,平凡不美,1S,4.2.4程序的控制结构,确保S3（步骤3）正确“算法”S1.将包子从蒸笼中轻轻提起，andthenS2.将包子慢慢移动到面前的小碟子中，andthenS3.在包子的正上方咬开一个小口，S4.If（3OK）andthen；else3againS5.通过小口吸食包子里的汤(当心别烫着)，andthenS6.将包子送入口中。S7.完成！,平凡不美,1S,4.2.4程序的控制结构,3.循环结构循环结构可以看成是一个条件判断语句和一个向回转向语句的组合，用于处理需要重复执行的某一组操作，是程序设计中最能发挥计算机特长的程序结构。循环结构的三个要素：循环变量、循环体、循环终止条件。,问题3:但是我们并不只是吃一只，怎么办?,平凡不美,1S,4.2.4程序的控制结构,策略一：控制数量假如规定吃8只：,策略二：吃饱为止,思考：策略1里的计数器可以不从0开始么？,平凡不美,1S,4.2.4程序的控制结构,问题4:如何根据不同的情况选择策略?,说明：以上策略1和策略2是两种不同的循环结构，他们分别嵌入在一个分支结构中，而整体上是一个顺序结构。,4.三种结构综合运用接上面实例，成年人是自己知道饱不饱的，但有些人是不知道的，例如孩子，是要进行限制的，否则吃多了会积食生病，所以又引出下一个问题。,平凡不美,1S,4.2.4程序的控制结构,问题5:如果要判断的不止俩种可能，那怎么办?,解决方法：分类定量控制,思考：这个流程图里的结构套用关系你能看出来么？参数设定可以修改么？参数设为8的部分可以修改成策略2吗？,4.2.4程序的控制结构,通过对上述一系列的实例的分析，我们可以更加深入的理解：任何一个简单或复杂的程序都可以由顺序结构、选择结构和循环结构这三种基本结构之一或者组合来实现。所以顺序结构，选择结构，循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的基本结构单元。,顺序结构：,选择结构：,循环结构：又称重复结构,4.2.5常见问题的算法描述,下面将通过典型问题来说明计算机求解这些问题的思路及具体算法。,先从简单的入手，问题描述：任意给定两个数，找出其中的最大者。,4.2.5常见问题的算法描述,俩个数最值流程图,思考1：如果是3个数的话上述流程图如何修改？假如更多的呢？,问题分析：1、定义两个未知数m和imax（m用作计数初始值1指向第一个同学，imax用来存放最大值，初始值0）2、先比较imax和第一个同学的成绩，然后和第二个同学比较，依次类推，如果小于当前比较的同学，就把当前同学的成绩存入到imax中，当m大于班级人数的时候结束循环，这样最后imax中存放的就是最大者。,思考2：哪个步骤是分支结构？哪是循环结构？,4.2.5常见问题的算法描述,2、排序问题有序化是人们在日常生活中频繁遇到的问题，例如：成绩按降序排名、学生按身高站队等。排序算法很多，如冒泡排序，选择排序，插入排序，快速排序，堆排序，归并排序等。这里我们以冒泡法排序来讲解排序问题，教材上还有选择排序和插入排序，希望大家能够独立完成理解的过程。,冒泡排序算法思想：比较相邻2个元素，如果次序不对，则将2个元素位置互换，依次由上往下比较，最终较大（或较小）的元素向上浮起，犹如冒泡。,4.2.5常见问题的算法描述,例：用冒泡法对8个数排序排序过程：（1）比较第一个数与第二个数，若为逆序a0a1，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上。（2）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置。（3）重复上述过程，共经过n-1趟冒泡排序后，排序结束。,思考：计算机里如何进行俩个数的交换？,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,4.2.5常见问题的算法描述,4.2.5常见问题的算法描述,冒泡法排序的流程图,思考：试着写出利用temp交换的等式顺序（代码）。,4.2.5常见问题的算法描述,3、搜索问题这是人们工作和生活中经常遇到的问题，例如：在学生库中找一个学生甲的信息、到图书馆查找资料、在网上使用搜索引擎搜寻信息等。搜索（Searching）问题就是在给定的一个文件（或数据集合）中，按照指定的关键字寻找该关键字或者寻找包含该关键字的记录。搜索问题通常又称为查找或检索。常见搜索方法：顺序搜索，二分搜索，枚举法，广度优先搜索，深度优先搜索等,4.2.5常见问题的算法描述,搜索问题举例：穷举法-百钱百鸡穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。穷举法也称为枚举法。,问题抽象：设鸡翁、鸡母、鸡雏分别为x，y，z只，由题意得：x+y+z=1005x+3y+(1/3)z=100以上两个方程式中有三个未知量，这样的方程组为不定方程组，其解有多种。用穷举法解决百钱买百鸡的问题，就是在0-100的范围内，确定x、y、z的值，当三者满足上述条件和时，所求得的x、y、z值就是其中的一个解。,【例】我国古代数学家张丘建在算经一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？,常见问题的算法描述,算法设计一（蛮力枚举法）：算法描述如下：S1：设x=0，y=0，z=0S2：判断x=20，真则继续S3；假则结束S3：判断y=33真则继续S4；假xx+1，并返回S2S4：判断z=100真则继续S5；