算法和算法的描述

.,算法与程序设计,信息技术（选修1）,1.2算法和算法的描述,.,导入新课,我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？,计算机解决问题的步骤,分析问题,设计算法,编写程序,调试程序,得出答案,具体问题,.,思考,有一个牧羊人带着一头羊，一只狼和一棵大白菜准备过河，他找到一只很小的船，每次只能带一样东西过去，如果狼和羊单独在一起，狼会吃羊，让羊和白菜单独在一起，羊会吃白菜，牧羊人应如何过河？,新课导入,要求：现在请同学们设计个方案，把3样东西安然无恙的度过河,.,步骤1：,步骤2：,步骤3：,步骤4：,人和羊过河，人返回，留下羊,人和狼过河，人和羊返回，留下狼,人和菜过河，人返回，留下菜,人和羊过河,新课导入,.,一、算法,1、算法的概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是求解某一问题的方法，是能被机械地执行的动作或指令的集合。,.,一、算法,2、算法的特征,（1）输入。一个算法有零个或多个输入。,零个输入的例子：Privatesubcommand1_click()a=3:b=4Printa*bEndsub,（2）确定性。算法的每一个步骤必须要确切地定义。,例1：这个人好说话。,例2：健美操中一个动作：“手举过头顶”。,.,一、算法,2、算法的特征,（3）有穷性。一个算法在执行有穷步之后必须结束。,反例：S1:sum=0S2:I=1S3:sum=sum+IS4:I=I+1S5:若sum=0，返回s3;否则，算法结束。,（4）输出。算法有一个或多个输出。,（5）能行性。,.,二、算法的描述,表示算法的语言有哪几种？,表示算法的语言有自然语言、流程图、伪代码。,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，则返回第；结束。,.,二、算法的描述,1、用自然语言描述算法,用自然语言描述算法,优点：描述的算法通俗易懂。,缺点：,自然语言具有歧义性，容易导致算法执行的不确定性。,自然语言描述的算法太长。,当算法中循环和分支较多时，很难清晰地表示出来。,自然语言表示的算法不便翻译成计算机程序设计语言。,.,二、算法的描述,2、用流程图描述算法,.,二、算法的描述,2、用流程图描述算法,例:求200-500能被5整除的所有正整数。,开始,I=200,I能被5整除,输出I的值,I=I+1,I=500,结束,是,否,否,是,.,二、算法的描述,2、用流程图描述算法,用流程图描述算法,优点：描述清晰简洁，不依赖计算机和计算机程序设计语言。,缺点：画起来费事，难以阅读，难以修改。,.,二、算法的描述,3、用伪代码描述算法,Inputm,nr=mmodnDowhiler0m=nn=rr=mmodnLoopPrintn,例：用辗转相除法求两个数的最大公约数的伪代码。,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。,.,二、算法的描述,3、用伪代码描述算法,用伪代码描述算法,优点：书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过度。,缺点：由于语言的种类繁多，伪代码的语句不容易规范。,.,三、算法在解决问题中的地位和作用,探究：运