算法和算法的描述

第二节算法和算法的描述知识与技能（1）了解算法的定义及其表达方法；（2）认知流程图的六种基本符号；（3）理解计算机解决问题的一般过程。（4）理解用不同的表达方法描述算法的优缺点；（5）掌握用流程图描述简单的算法。重点难点（1）算法的定义；（2）算法的三种表达方法；（3）流程图的六种基本符号；（4）用流程图描述简单的算法。什么是算法算法是解决问题的方法和步骤。通俗点说，就是计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。算法独立于任何具体的程序设计语言，一个算法可以用多种程序设计语言来实现。例：求两个整数的最大公约数，设两正整数分别为为M和N，其具体过程为：1、以M除以N，所得余数为R2、若R＝0，则输出结果N，结束；否则，继续步骤33、令M=N,N=R，返回步骤1继续。若给定两整数，M＝112，N＝64，则算法如下：1、112除以64，余数为_________2、_______除以_______余数为_______3、_______除以_______余数为_______112和64的最大公约数为_______486448164816016算法的特征算法要有一个清晰的起始步，表示处理问题的起点，且每一个步骤只能有一个确定的后继步骤(算法的确定性)，从而组成一个步骤的有限序列(算法的有穷性)；要有一个终止步(序列的终止)表示问题得到解决或不能得到解决；每条规则必须是确定的、可行的(算法的可行性)、不能存在二义性。算法总是对数据进行加工处理，因此，算法的执行过程中通常要有数据输入(0个或多个)和数据输出（至少一个）的步骤。描述算法的方法1、自然语言：即用人们日常使用的语言和数学语言描述的算法。无需专门训练，描述的算法通俗易懂。思考：经典算法中的百钱百鸡。现拿100文钱去买100只鸡，公鸡为5文钱一只，母鸡3文钱一只，小鸡是1文钱买三只。有哪些买法？输出组合。通过阅读P10的例1-2和1-3得知，自然语言描述算法的缺点有：（1）、由于自然语言的歧义性而导致算法执行的不确定性；（2）、自然语言语句较长而导致描述的算法太长；（3）、难以清楚地描述循环和分支结构的算法；（4）、不便于翻译成计算机设计语言。实践：判断输入的三角形边长A、B、C能否构成三角形，能构成三角形则输出其面积，否则输出“不能构成三角形”。算法：1、输入三边长，分别为A、B、C2、判断三边能否构成三角形3、能构成三角形则计算其面积并显示，否则显示“不能构成三角形”4、结束韩信点兵算法1从1开始,取出一个自然数判断它被3、5、7整除后的余数是否为1、3、4，如果是，则这个数即是所求的数，求解结束。否则，用下一个数再试，直到找到这个数为止。(假设人数N100)自然语言描述1、将N的初始值赋为12、如果N100并且N被3、5、7整除后余数为1、3、4，则输出N的值，转入第4步3、将N的值加1,转到第2步4、结束程序开始/结束符，表示算法的开始或结束；输入/输出框,用于指出数据的输入或输出;处理框，用于指出要处理的内容；判断框，用于指出分支情况，通常，上面的顶点表示入口，其它顶点表示出口；流程线，表示流程控制方向；2、流程图：即用一组标准的图形符号来描述算法。开始结束连接点，表示算法中的连接。流程图描述开始N被3、5、7整除余数为1、3、4(N100)N=N+1结束NYN=1输出N值用伪代码描述算法ForI=1toNifn能被3、5、7整除余数为2、3、2then输出nexitforendifnext13、伪代码：伪代码是一种非正式代码，常用自然语言、数学语言和符号来描述算法的操作步骤。完整的源程序PrivateSubCommand1_Click()'算法:使用穷举法确立一个范围[1,100]然后从自然数1开始尝试,找到满足条件的数即输出DimiAsIntegerFori=1To100IfiMod3=1AndiMod5=2AndiMod7=4ThenMsgBox答案是:&iEndIfNextEndSub课堂练习：分别用自然语言和流程图描述求解1、所有水仙花数的问题。水仙花数是指一个三位数，它的各位数的立方和正好等于该数本身。如153=13+53+33。2、设计统计前1000个自然数中的奇数的个数的流程图3、设计算法：找出乘积为840的两个相邻偶数水仙花数自然语言描述1、将N的初始值赋为1002、如果N的个位数的三次方加上N的十位数的三次方再加上N的百位数的三次方等于N,输出N值,否则转入第3步3、如果N=999,将N的值加1，转到第2步,否则转入第4步4、输出运算结果，结束程序水仙花数流程图描述开始N=N+1结束NYN的个位数的三次方+N的十位数的三次方+N的百位数的三次方=NN=100输出N值N=999YND=1?输出MBeginM=1D=5M=2*(M+1)D=D-1ENDYNP12实践：用伪代码描述水仙花数算法ForN=100to999ifN的个位数的三次方+N的十位数的三次方+N的百位数的三次方=Nthen输出nendifNextNPrivateSubCommand1_Click()DimiAsIntegerFori=100To999IfInt((i/100))^3+(Int((i/10))Mod10)^3+(iMod10)^3=iThenPrintiEndIfNextiEndSub水仙花数源程序第二题源程序PrivateSubCommand1_Click()DimI,RAsIntegercount=0ForI=1To1000Step2IfiMod20ThenR=R+1EndIfNextIPrintREndSub设计统计前1000个自然数中的奇数的个数的流程图PrivateSubCommand1_Click()DimiAsSingleFori=2To30Step2Ifi*(i+2)=840ThenPrint这两个数是:“;i;和;i+2EndIfNextiEndSub第三题源程序找出乘积为840的两个相邻偶数小结自然语言描述算法算法的描述流程图描述算法伪代码描述算法一个问题可能有多种算法，应该通过分析、比较、挑选一种最优算法，一个好的算法必须用到科学的方法，应该好好学习各学科处理问题的科学方法。有三个装有的瓶子大瓶可装1L中瓶可装0.7L小瓶可装0.3L有1L的油装在大瓶中，利用三个瓶子分出0.5L的油.①先将1升油倒满0.7L的桶，剩下的倒入1L的桶（这时1L的桶里有0.3升油）；②从0.7L的桶里用0.3L的空桶装满倒入1L的桶里，然后再装满再倒入（这时1L的桶里有0.9升，0.7L的桶里有0.1升）；③把0.7L的桶里有0.1升倒入0.3L的桶里（这时1L的桶里有0.9升，0.3L的桶里有0.1升）；④从1L的桶里倒满0.7L的桶（1L的桶里还剩0.2升），再从0.7L的桶里倒出0.2生倒入0.3L的桶里，0.3L的桶正好满。这时1L的桶里有0.2升，0.7L的桶里有0.5升，0.3L的桶里有0.3升；⑤把0.3L的桶里的油倒入1L的桶里。此时，1L和0.7L的桶里各有0.5升油.