3.2 算法及其描述 课件（15张ppt）

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