3.2 算法及其描述 学案

算法及其描述 学习目标 1.理解和概述算法的概念与特征; 2.运用恰当的描述方法和控制结构表示简单算法。 学习内容 算法 算法是指在有限步骤内求解某一问题所使用的一 组定义明确的规则。通俗地说,算法就是用计算机求解某一问题的方法,是能被机械地执行的动作或指令的有穷集合。 例如,若要求方程6x+ 5y+ 4z= 50的正整数解的个数,则解决问题的算法步骤如下: ①t=0 ; ②x=1; ③y=1; ④z=1; ⑤如果满足式子6x +5y+4z= 50 ,则解的个数加1(即t=t+1 ,示右边式子的值赋值给左边式子),并输出这个解(即输出t , x, y , z的值) ; ⑥z=Z+1 ; ⑦如果z≤12则转步骤⑤,否则继续步骤⑧; ⑧y=y+1 ; ⑨如果y≤10则转步骤④,否则继续步骤四; ◎x=x+1; 如果x≤8则转步骤③,则继续步骤;结束。 算法的特征 算法作为能确实解决某个问题的策略,具有五个方面的重要特征: (1)有穷性。一个算法在执行有穷步之后必须结束,即一个算法所包含的计算步骤是有限的。例如，在上面的算法中, x的值从1开始穷举,重复执行语句,直到x> 8时终止执行。 (2)确定性。算法执行的每一个步骤必须有 确切的定义,不能出现模棱两可的情况。例如，上面算法步骤⑤就明确规定:当满足式子6x+ 5y+4z= 50时,则解的个数加1(即t=t+1) ,并输出这个解。 (3)数据输入。一个算法必须有零个或多个数据输入,以刻画运算对象的初始情况。例如,在上面的算法中,就没有数据输入。 (4)数据输出。一个算法有 一个或多个数据输出,以反映对输入数据加工后的结果,没有输出的算法是毫无意义的。例如，在上面的算法中,有两个输出,即步骤⑤的个数t和具体解(x, y , z的值)。 (5)可行性。算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成。例如，上面的算法中每一步都是可以在有限时间内完成的。 算法的描述 算法是对解题过程的精确描述,且需要使用某种方法将其表示出来。 1.描述算法的常用方法 描述算法的常用方法有自然语言描述算法、流程图描述算法和伪代码描述算法。 (1)用自然语言描述算法。 用自然语言描述算法,就是用人们日常所用的语言, 如汉语、英语等来描述算法。例如,从A市 到B市耗时最少的旅行路线问题的算法描述,即使用了自然语言。 使用自然语言描述算法比较容易掌握,但也存在明显的缺点。例如，当算法中含有多分支或循环操作较多时,使用自然语言很难将其清晰地表示出来;且由于自然语言的歧义性,也容易导致算法执行的不确定性。 (2)用流程图描述算法 用流程图捕述算法是用程序框图来描述算法的一种表示方法。使用流程描述算法，可使算法的流程描述得清晰、简洁。 例如,用流程图描述求方程6x+ 5y+4z= 50的正整数解的算法。 (3)用伪代码描述算法。 用伪代码描述算法就是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不图形符号,泻方便,格式紧凑,易于理解,便于向计算机程序设计语言过渡。 例如,用伪代码描述求解方程6x+5y+4z= 50的算法如下: 在《几何原本》一书中,欧几里得阐述了关于求两个正整数的最大公约数的过程,这就是著名的欧几里得算法 辗转相除法,具体过程如下: 设给定的两个正整数为m和n ,求它们的最大公约数的步骤为: ①以m除以n ,令所得的余数为R。 ②若R=0 ,则输出结果n ,算法结束;否则,继续步骤③。 ③令m=n , n=R ,并返回步骤①继续进行。 用流程图将上述算法表示出来,试探索欧几里得算法在现实生活中有哪些应用,举出两个应用实例。 2.三种基本控制结构 前面的算法描述中, 我们用到了顺序结构,选择结构和循环结构这三种基本控制结构,而任何复杂的算法都可以用这三种基本控制结构组合来表示。 这三种基本控制结构的主要作用是: (1)顺序结构表示程序中的各步操作按出现的先后顺序执行。 (2)选择结构表示程序的处理步骤 ... ...