算法和算法的描述.ppt

算法与程序设计,信息技术（选修1）,1.2 算法和算法的描述,导入新课,我们上节课通过“韩信点兵”的例子探讨了计算机解决问题的步骤，你们还记得计算机解决问题的步骤吗？,计算机解决问题的步骤,分析问题,设计算法,编写程序,调试程序,得出答案,具体问题,思考,有一个牧羊人带着一头羊，一只狼和一棵大白菜准备过河， 他找到一只很小的船，每次只能带一样东西过去，如果狼 和羊单独在一起，狼会吃羊，让羊和白菜单独在一起，羊 会吃白菜，牧羊人应如何过河？,新课导入,要求：现在请同学们设计个方案，把3样 东西安然无恙的度过河,步骤1：,步骤2：,步骤3：,步骤4：,人和羊过河，人返回，留下羊,人和狼过河，人和羊返回，留下狼,人和菜过河，人返回，留下菜,人和羊过河,新课导入,一、算法,1、算法的概念,算法是在有限步骤内求解某一问题所使用的一组定义 明确的规则。通俗地说，算法就是求解某一问题的方法， 是能被机械地执行的动作或指令的集合。,一、算法,2、算法的特征,（1）输入。一个算法有零个或多个输入。,零个输入的例子： Private sub command1_click() a=3:b=4 Print a*b End sub,（2）确定性。算法的每一个步骤必须要确切地定义。,例1：这个人好说话。,例2：健美操中一个动作：“手举过头顶”。,一、算法,2、算法的特征,（3）有穷性。一个算法在执行有穷步之后必须结束。,反例： S1: sum=0 S2: I=1 S3: sum=sum+I S4: I=I+1 S5: 若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、用伪代码描述算法,Input m, n r= m mod n Do while r0 m=n n=r r=m mod n Loop Print n,例：用辗转相除法求两个数的最大公约数的伪代码。,伪代码是用介于自然语言和计算机语言之间的 文字和符号来描述算法的工具。,二、算法的描述,3、用伪代码描述算法,用伪代码描述算法,优点：书写方便，格式紧凑，易于理解，便于向计算机 程序设计语言过度。,缺点：由于语言的种类繁多，伪代码的语句不容易规范。,三、算法在解决问题中的地位和作用,探究：运行