算法及其实现.pptx

高中高中信息技术基础信息技术基础（必修）（必修）算法及其实现算法及其实现农夫过河农夫过河 一个农夫带着一条狼、一头山羊和一篮一个农夫带着一条狼、一头山羊和一篮蔬菜要过河，但只有一条船。乘船时，农夫蔬菜要过河，但只有一条船。乘船时，农夫只能带一样东西。农夫在场的时候，这三样只能带一样东西。农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊，东西相安无事。一旦农夫不在，狼会吃羊，羊会吃菜。请设计一个算法，使农夫能安全羊会吃菜。请设计一个算法，使农夫能安全的将这三样东西带过河。的将这三样东西带过河。农夫带狼、山羊、蔬菜过河步骤农夫带狼、山羊、蔬菜过河步骤解一：解一：1、农夫带羊过河、农夫带羊过河2、农夫回来、农夫回来3、把狼带过河、把狼带过河4、把羊带回来、把羊带回来5、带蔬菜过河、带蔬菜过河6、农夫回来、农夫回来7、把羊带过河、把羊带过河解二：解二：1、农夫带羊过河、农夫带羊过河2、农夫回来、农夫回来3、带蔬菜过河、带蔬菜过河4、把羊带回来、把羊带回来5、把狼带过河、把狼带过河6、农夫回来、农夫回来7、把羊带过河、把羊带过河算法的定义：算法的定义：所谓“算法”（algorithm）就是解题方法的精确描述。算法的特点算法的特点:算法的特点是求解步骤必须是有限的,而且每个环节都必须是明确和可行的。问：问：如何判断一个算法的好坏如何判断一个算法的好坏？数学家华罗庚的统筹方法中著名的”泡泡茶算法茶算法”：灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水灌凉水洗茶壶拿茶叶泡茶喝洗茶杯洗开水壶烧开水方法甲方法丙方法乙t(请同学们对这几种算法进行评价请同学们对这几种算法进行评价!)!)算法的表示：算法的表示：为了表示一个算法，常用的算法表示形式有：自然语言、流程图自然语言、流程图和和计算机语言计算机语言。常用的计算机语言有：C C、C+C+、Basic Basic、VBVB 和javajava等。自然语言表示法自然语言表示法 自自然然语语言言就就是是人人们们日日常常使使用用的的语语言言,可可以以是是汉汉语语、英英语语或或数数学学语语言言等等.用用自自然然语语言言描描述述算算法法的的优优点点是是通通俗俗易易懂懂,当当算算法法中中的的操操作作步步骤骤都都是是顺顺序序执执行行时时比比较较容容易易理理解解.缺缺点点是是通通常常所所用用文文字字会会比比较较冗冗长长，还还容容易易出出现现“歧义性歧义性”.流程图流程图是人们经常用来描述算法的工具，流程图用图框及流程线来表示算法形象直观。美国国家标准化协会（ANSI）规定了流程图符号。1.处理框（）：框中指出要处理的内容，有出口和入口。2.输入、输出框（）：表示输入和输出数据。3.判断框（）：表示条件判断及产生分支的情况。4.连接框（）：连接因页面写不下而断开的流程线。5.流程线（）：有向线段，控制流程方向。6.开始、结束框（）：表示本段算法的开始或结束。例1：要设计一个算法，对任意输入的三个整数x、y和z，找出并输出其中的最大值。按照它的思想，我们只需要先比较x和y，得到一个较大的值max，再用max与y比较，将两者中较大的值作为结果输出即可。用自然语言，可以将这个算法描述为：用自然语言，可以将这个算法描述为：（1 1）输入变量）输入变量x x、y y和和z z的值。的值。（2 2）比较）比较x x和和y y。如果。如果xyxy，则，则x x存入以存入以maxmax命名命名的存储单元中；否则，的存储单元中；否则，y y送送maxmax。（3 3）比较）比较z z和和maxmax。如果。如果zmaxzmax，则，则z z送送maxmax。（4 4）输出结果）输出结果maxmax。这个算法也可以用下面的流程图来描述。图这个算法也可以用下面的流程图来描述。图中的中的Y Y表示表示YesYes，N N表示表示NoNo。开始开始输入变量输入变量x、y和和z的值的值x yz maxmax xmax ymax z输出变量输出变量max的值的值结束结束图框内的符号图框内的符号“”是赋值号，是赋值号，表示将赋值号右表示将赋值号右边的表达式运算边的表达式运算的结果值存入左的结果值存入左边的变量。例如，边的变量。例如，“max xmax x”、i i+1i i+1YN练习1:画出“我们走路时躲避障碍”这个过程的流程图YN有障碍吗?往前直走开始结束躲避障碍观察道路情况开始输入变量n的值输出变量f的值结束i n？Nf 1i 1f f*ii i+1Y 程序设计实例程序设计实例例2：求n阶乘（n!=123n）首先输入变量n的值，变量f和i被赋以初值1，然后判断in是否成立，如果成立，执行赋值语句ff*i和i i+1，并回到判断处，否则结束循环，最后输出f的值。练习练习2 2在抽屉中寻找东西的过程。在抽屉中寻找东西的过程。NY寻找开始结束找到了吗?拿东西循环结构循环结构循环结构循环结构分支结构和循环结构的异同:YN条件?执行a执行b开始结束开始YN执行a条件?执行b开始 谢谢！