1、3.2 算法及其描述 3.2.1算法 l1.1.算法算法 l算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。 通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地 执行的动作或指令的有穷集合。执行的动作或指令的有穷集合。 l探究活动探究活动 l观察观察 若要求方程6x+5y+4=50的正整数解的个数t，则解决问题的算法步骤如下: t=0; x=1; y=1; z=1; 如果满足式子6x+5y+42=50，则解的个数加t (即t=t+1,表示右边式子的值赋值給左
2、边式子)，并输出这个解(即输出 t，x，y，z的值) ; z=z+1; 如果z12则转步骤，否则继续步骤; Y=y+1; 如果y10则转步骤，否则继续步骤; x=x+1; 如果x8则转步骤，否则继续步骤 ; 结束。 l2.2.算法的特征算法的特征 l算法作为能确实解决某个问题的策略，具有五个方面的重要特征算法作为能确实解决某个问题的策略，具有五个方面的重要特征: : l(1)(1)有穷性。有穷性。 一个算法在执行有穷步之后必须结束，即一 个算法所包含的计算步骤是有限的。例如，在上面的算法中，x的值从1开始穷举，重 复执行语句，直到8时终止执行。 l(2)(2)确定性。确定性。 算法执行的每一个
3、步骤必须有确切的定义，不能出现模棱两可的情况。例如，上面算法步骤就明确规定:当满足式于6+5y+4-50时， 则解的个数加1 (即1=1+1)，并输出这个解。 l(3)(3)数据输人。数据输人。 一个算法必须有零个或多个数据输人，以刻画运算对象的初始情况。例如，在上面的算法中，就没有数据输人。 l(4)(4)数据输出。数据输出。 一个算法有一个或多个数据输出，以反映对输人数据加工后的结果，没有输出的算法是毫无意义的。例如，在上面的算法中，有两 个输出，即步骤的个数和具体解(x，y, z的值)。 l(5)(5)可行性。可行性。 算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤，即每个
4、计算步骤都可以在有限时间内完成。例如，上面的算 法中每一步都是可以在有限时间内完成的。 l3.2.23.2.2算法的描述算法的描述 l算法是对解题过程的精确描述，且需要使用某种方法将其表示出来。算法是对解题过程的精确描述，且需要使用某种方法将其表示出来。 l1.1.描述算法的常用方法描述算法的常用方法 描述算法的常用方法有自然语言描述算法、流程图描述算法和伪代码描述算法。 l(1)(1)用自然语言描述算法。用自然语言描述算法。 用自然语言描述算法，就是用人们日常所用的语言，如汉语、英语等来描述算法。例如，从A市到B市耗 时最少的旅行路线问题的算法描述，即使用了自然语言。 使用自然语言描述算法比
5、较容易掌握，但也存在明显的缺点。例如，当算法中含有多分支或循环操作较 多时，使用自然语言很难将其清晰地表示出来:并且由于自然语言的歧义性，也容易导致算法执行的不确 定性。 l(2)(2)用流程图描述算法。用流程图描述算法。 用流程图描述算法是用程序枢图来描述算法的一种表示方法。 使用流程图描述算法。可使算法的流程描 述得清晰、简洁。流程图的基本图形及其功能如表3-4所示。 例如，用流程图描述 求方程6x+5y+4z=50 的正整数解的算法, 如图3-8所示。 l(3(3）用伪代码描述算法。）用伪代码描述算法。 l用伪代码描述算法就是用介于用伪代码描述算法就是用介于 自然语言和计算机语言之间的自
6、然语言和计算机语言之间的 文字和符号来描述算法。它不文字和符号来描述算法。它不 用图形符号，书写方便，格式用图形符号，书写方便，格式 紧凑，易于理解，便于向计算紧凑，易于理解，便于向计算 机程序设计语言过渡。机程序设计语言过渡。 例如,用伪代码描述求解方程6x+5y+4z=50的算 法如下: l交流交流 各小组交流三种算法描述方法的优势和不足，并完成表3-5。 l实践实践 在几何原本一书中，欧几里得阐述了关于求两个正整数的最大公约数的过程，这就是著名的欧几里 得算法辗转相除法，其具体过程如下: 设给定的两个正整数为m和n，求它们的最大公约数的步骤为: 以m除以n，令所得的余数为R。 若R=0，
7、则输出结果n，算法结束;否则，继续步骤。 令m=n，n=R，并返回步骤继续进行。 用流程图将上述算法表示出来，试探索欧几里得算法在现实生活中有哪些应用，举出两个应用实例。 l2.2.三种基本控制结构三种基本控制结构 l前面的算法描述中，我们用到前面的算法描述中，我们用到r r顺序结构、选择结构和循环结构这顺序结构、选择结构和循环结构这 三种基本控制结构三种基本控制结构( (其流程图如图其流程图如图3. -93. -9所示所示) )，而任何复杂的算法，而任何复杂的算法 都可以用这三种基本控制结构组合来表示。都可以用这三种基本控制结构组合来表示。 l这三种基本控制结构的主要作用是这三种基本控制结构
8、的主要作用是: : （1）顺序结构表示程序中的各步操作按出现的先后顺序执行。 （2）选择结构表示程序的处理步骤出现了分支,需要根据某一特定的条件选择其中的一个分支执行。选 择结构有单选择、双选择和多选择三种。 （3）循环结构表示程序反复执行某个或某些操作，直到判断条件为假（或为真)时才可终止循环。 l使用三种基本控制结构的组合来描述算法，可以改善算法的清晰度，使用三种基本控制结构的组合来描述算法，可以改善算法的清晰度， 提高算法的可读性提高算法的可读性, ,原因如下原因如下: : （1）以控制结构为单位，只有一个入口和一个出口，各单位之间接口简单，比较容易独立地理解每一单 位。 （2）缩小了算法的静态描述与动态执行过程之间的差异，使得两者容易对应，易于理解。 l项目实施项目实施 各小组根据项目选题及拟订的项目方案，结合本节所学知识，开展以下活动。 1完成相应问题的算法设计及其描述。 2.总结归纳所采用的方法和步骤。
