算法和算法描述

导入新课我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？计算机解决问题的步骤分析问题设计算法编写程序调试程序得出答案具体问题第一页，共15页。思考有一个牧羊人带着一头羊，一只狼和一棵大白菜准备过河，他找到一只很小的船，每次只能带一样东西过去，如果狼和羊单独在一起，狼会吃羊，让羊和白菜单独在一起，羊会吃白菜，牧羊人应如何过河？新课导入要求：现在请同学们设计个方案，把3样东西安然无恙的度过河第二页，共15页。步骤1：步骤2：步骤3：步骤4：人和羊过河，人返回，留下羊人和狼过河，人和羊返回，留下狼人和菜过河，人返回，留下菜人和羊过河新课导入第三页，共15页。一、算法1、算法的概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是求解某一问题的方法，是能被机械地执行的动作或指令的集合。第四页，共15页。一、算法2、算法的特征（1）输入。一个算法有零个或多个输入。零个输入的例子：Privatesubcommand1_click()a=3:b=4Printa*bEndsub（2）确定性。算法的每一个步骤必须要确切地定义。例1：这个人好说话。例2：健美操中一个动作：“手举过头顶”。第五页，共15页。一、算法2、算法的特征（3）有穷性。一个算法在执行有穷步之后必须结束。反例：S1:sum=0S2:I=1S3:sum=sum+IS4:I=I+1S5:若sum>=0，返回s3;否则，算法结束。（4）输出。算法有一个或多个输出。（5）能行性。第六页，共15页。二、算法的描述表示算法的语言有哪几种？表示算法的语言有自然语言、流程图、伪代码。1、用自然语言描述算法例:求200-500能被5整除的所有正整数。（1）分析问题。设能被5整除的数为I,令I=200,201,202，……，500，如果I是能被5整除的数，则输出I；否则，检查下一个I，直到I=500为止。（2）设计算法①令I=200;②如果I能被5整除，则输出I;③I=I+1;④如果I<=500，则返回第②；⑤结束。第七页，共15页。二、算法的描述1、用自然语言描述算法用自然语言描述算法优点：描述的算法通俗易懂。缺点：自然语言具有歧义性，容易导致算法执行的不确定性。自然语言描述的算法太长。当算法中循环和分支较多时，很难清晰地表示出来。自然语言表示的算法不便翻译成计算机程序设计语言。第八页，共15页。二、算法的描述2、用流程图描述算法图形名称功能起始/结束表示算法的开始或结束

输入/输出表示算法中变量的输入或输出

处理表示算法中变量的计算或赋值

判定表示算法中的判断

流程线表示算法中的流向

连接点表示算法流向出口或入口连接点第九页，共15页。二、算法的描述2、用流程图描述算法例:求200-500能被5整除的所有正整数。开始I=200I能被5整除输出I的值I=I+1I<=500结束是否否是第十页，共15页。二、算法的描述2、用流程图描述算法用流程图描述算法优点：描述清晰简洁，不依赖计算机和计算机程序设计语言。缺点：画起来费事，难以阅读，难以修改。第十一页，共15页。二、算法的描述3、用伪代码描述算法Inputm,nr=mmodnDowhiler<>0m=nn=rr=mmodnLoopPrintn例：用辗转相除法求两个数的最大公约数的伪代码。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。第十二页，共15页。二、算法的描述3、用伪代码描述算法用伪代码描述算法优点：书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过度。缺点：由于语言的种类繁多，伪代码的语句不容易规范。第十三页，共15页。三、算法在解决问题中的地位和作用探究：运行这两个程序，比较它们的效率，把你观察到的现象填在表1-6中。同学甲的算法：同学乙的算法：PrivateSubCommand1_Click()m=9147485n=5147480r=mModnDoWhiler<>0m=nn=rr=mModnLoopPrint"最大公约数=";nEndSubPrivateSubCommand1_Click()m=9147485n=5147480i=mDoWhilemModi<>0OrnModi<>0i=i-1LoopPrint"最大公约数=";iEnd