3.4算法及其实现 (2).ppt

1、算法及其实现（一）算法及其表示,广东省仁化中学伍才华,问题,一个农夫带着一条狼、一头山羊和一蓝蔬菜要过河，但只有一条小船。乘船时，农夫只能带一样东西。当农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊，羊会吃菜。请你帮助农夫设计一个方案能安全地将这三样东西带过河。,过河方案,农夫带山羊过河 农夫回去带狼过河 农夫带山羊回去 农夫带蔬菜过河 农夫回去带山羊过河,计算机解决问题的过程,算法概念,算法是解题方法的精确描述。 （解题的方法和步骤）,算法特征,算法描述是有穷的动作序列（有限个步骤组成）有穷性 算法中的每个动作应当是明确的，没有二义性的确定性 算法设计完成后应选择合适的计算机编程

2、语言编制相应的程序可行性,从广义角度来看，生活中处处有算法，并不只有数学中存在算法。如乐谱、菜谱、广播操图解等。,问题：有同学做过饭菜没有？ 你是怎样操作的？,假设煮饭、炒菜为同一个锅，需通过洗菜和切菜、做饭、炒菜三个环节来完成一顿饭菜，你会选择下面哪种方法来操作？为什么？,面对同一个问题，通常有很多解决问题的方法和步骤，我们一般尽可能采用简单省时的和步骤最少的方法来解决问题。,算法表示,为了表示一个算法，可以用不同的形式，常用的算法表示形式有：自然语言、流程图和计算机语言（第二课时学习）等。,1、自然语言,前面我们帮“农夫过河”设计的方案就是算法，是采用自然语言来表示的。用自然语言能够表示一

3、些简单的算法，但对于一些复杂的算法，用自然语言来描述容易出现“二义性”，或者必须用冗长的语言才能说清楚。,例如：“老王对老张说他儿子去西部支教了”。,老王对老张说：“我儿子去西部支教了”。,这句话存在二义性。请问是谁的儿子去支教了，是老王的，还是老张的，还是其他人的儿子去支教了？我们不清楚，所以要用详细的语言来描述。,老王对老张说：“你儿子去西部支教了”。,老王对老张说：“李四儿子去西部支教了”。,2、流程图,流程图符号及其功能：,用自然语言和流程图来设计同一问题的算法：,任意输入的三个整数x、y、z，找出并输出其中的最大值。,用自然语言描述算法：,输入变量x、y和z的值； 比较x和y。如果x

4、y，则x存入以max命名的存储单元中；否则，y送max。 比较z和max。如果zmax，则将z送max。 输出结果max。,练习：输入a、b的值，输出a、b之和。请自然语言描述算法。,用流程图描述算法：,练习：输入a、b的值，输出a、b之和。请用流程图描述算法。,巩固练习,课本 、有两个瓶子和，分别盛放醋和酱油，如果要将它们所盛的内容互换，即瓶原来盛醋，现改为盛酱油，瓶则相反。请用自然语言来描述实现这一转换的算法。 、输入三个数，判断它们是否能成为一个三角形的三条边的长度，若能则输出“能”，否则输出“不能”。请用流程图描述本题的算法。（提示：形成三角形的条件是两边之和大于第三边，两边之差小于第三边。）,答案,1、借用瓶子C；把A瓶中的醋倒入C瓶中；把B瓶中的酱油倒入A瓶中；再把C瓶中的醋倒入B瓶中。,、,总结,算法是解题方法的精确描述。同一个