(
课件网) 3.4 算法及其实现 阿克苏地区二中 吴园园 案例一： 一个农夫带着一条狼、一头山羊和一篮蔬菜要过河。当他来到渡口时发现过河的小船除了能装下自己之外，只能再带1样东西过河。这使他有点犯愁了，因为如果农夫不在场的情况下，狼会吃羊，羊会吃蔬菜。请同学们帮助农夫解决安全过河问题。 步骤一：农夫先带着羊乘船过河。 步骤二：农夫回来后再将狼乘船过河。 步骤三：将狼渡完河时，把羊再带回来。 步骤四：把羊放下将蔬菜乘船过河 步骤五：最后农夫回来再带着羊乘船过河。 步骤一：农夫先带着羊乘船过河。 步骤二：农夫回来后再将蔬菜乘船过河。 步骤三：将蔬菜渡完河时，把羊再带回来。 步骤四：把羊放下将狼乘船过河 步骤五：最后农夫回来再带着羊乘船过河。 所谓算法，就是解题方法的精确描述。是指在使用计算机解题前，需要将解题方法转换成一系列具体的在计算机上可执行的步骤，这些步骤能够清楚的反映解题方法一步步“怎么做”的过程，这个过程就是通常所说的算法。 案例二： 泡 茶 洗开水壶 灌凉水 洗茶壶 洗茶杯 拿茶叶 泡茶喝 洗开水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝 拿茶叶 洗茶壶 洗茶杯 泡茶喝 烧开水 洗开水壶 洗开水壶 洗开水壶 洗茶壶 洗茶杯 拿茶叶 灌凉水 烧开水 泡茶喝 洗开水壶 灌凉水 拿茶叶 洗茶壶 洗茶杯 泡茶喝 烧开水 烧开水 最剩时间 洗开水壶 洗开水壶 对同一个问题，有时可以有不同的解题方法和步骤。有的方法只需要较少的步骤,而有些方法则可能需要较多的步骤。一般情况下,尽可能采用简单省时的和步骤少的方法去解决问题。因此，为了有效地解决问题，不仅需要保证算法正确，还要考虑算法的质量，这就要求人们设计或选择合适的算法。 1、有穷性（有限性）。任何一种提出的解题方法都是在有限的操作步骤内可以完成的，哪怕是失败的解题方法。 2、确定性（唯一性）。解题方法中的任何一个操作步骤都是清晰无误的，不会使人产生歧义或者误解。 3、可行性（能行性）。解题方法中的任何一个操作步骤在现有计算机软硬件条件下和逻辑思维中都能够实施实现。 4、有0到多个输入。解题算法中可以没有数据输入，也可以同时输入多个需要算法处理的数据。 5、有1到多个输出。一个算法执行结束之后必须有数据处理结果输出，哪怕是输出错误的数据结果，没有输出的算法使毫无意义的。 一、使用自然语言描述算法 二、使用流程图描述算法 三、使用伪代码（计算机语言）描述算法 例1： 要设计一个算法，对任意输入的三个整数x、y和z，找出并输出其中的最大值。这个算法比较简单，只要先比较x和y，得到一个较大的值max，再用max与z比较，将两者中较大的值作为结果输出即可。 第一种：用自然语言描述： （1）输入变量X、Y和Z的值。 （2）比较X和Y。如果X>Y，则X存入以max命名的存储单元中，否则，Y送max。 （3）比较z和max。如果z>max，则将z送max。 （4）输出结果max。 从上面的这个描述的求解过程中，我们不难发现，使用自然语言描述算法的方法虽然比较容易掌握，但是存在着很大的缺陷。例如，当算法中含有多分支或循环操作时很难表述清楚。另外，使用自然语言描述算法还很容易造成歧义（称之为二义性），譬如有这样一句话———武松打死老虎”，我们既可以理解为“武松/打死老虎”，又可以理解为“武松/打/死老虎”。自然语言中的语气和停顿不同，就可能使他人对相同的一句话产生不同的理解。又如“你输他赢”这句话，使用不同的语气说，可以产生3种截然不同的意思，同学们不妨试试看。为了解决自然语言描述算法中存在着可能的二义性，我们提出了第2种描述算法的方法———流程图。 第二种：用流程图描述 开 始 输入变量X、Y和Z的值 ... ...
