计算机第9章-计算机思维与程序算法(VB方向)课件.pptx

1、计算思维与程序算法计算思维与程序算法第第 9 9 章章主主 要要 内内 容容9.2 9.2 算法设计算法设计9.3 9.3 程序设计基础程序设计基础9.1 9.1 计算思维计算思维9.1.1 9.1.1 计算思维的提出计算思维的提出 9.1.2 9.1.2 科学方法与科学思维科学方法与科学思维 9.1.3 9.1.3 计算思维的内容计算思维的内容 9.1 9.1 计算思维计算思维9.1.4 9.1.4 计算思维能力的培养计算思维能力的培养 计算计算思维不是今天才有的，从我国古代的算筹、算盘，到近代的加法思维不是今天才有的，从我国古代的算筹、算盘，到近代的加法器、计算器以及现代的电子计算机，直至

2、目前风靡全球的互联网和云计算，器、计算器以及现代的电子计算机，直至目前风靡全球的互联网和云计算，无不体现着计算思维的思想。无不体现着计算思维的思想。然而然而，在相当长的时期，计算思维并没有得，在相当长的时期，计算思维并没有得到系统的整理和总结，也没有得到应有的重视。直到到系统的整理和总结，也没有得到应有的重视。直到2006年，周以真教授年，周以真教授对计算思维进行了清晰系统的阐述，这一概念才得到人们极大的关注。对计算思维进行了清晰系统的阐述，这一概念才得到人们极大的关注。到到目前为止，都没有一个统一的、获得广泛认可的关于计算思维的定目前为止，都没有一个统一的、获得广泛认可的关于计算思维的定义。

3、所有的讨论和研究大致可分为两个方向：其一，将义。所有的讨论和研究大致可分为两个方向：其一，将“计算思维计算思维”作为作为计算机及其相关领域中的一个专业概念，对其原理内涵等方面进行探究，计算机及其相关领域中的一个专业概念，对其原理内涵等方面进行探究，称为理论研究；其二，将称为理论研究；其二，将“计算思维计算思维”作为教育培训中的一个概念，研究作为教育培训中的一个概念，研究其在大众教育中的意义、地位、培养方式等，称为应用研究。理论研究对其在大众教育中的意义、地位、培养方式等，称为应用研究。理论研究对应用研究起到指导和支撑的作用，应用研究是理论研究的成果转化，并丰应用研究起到指导和支撑的作用，应用研

4、究是理论研究的成果转化，并丰富其体系，两者相辅相成，形成对计算思维的完整阐述。富其体系，两者相辅相成，形成对计算思维的完整阐述。9.1.1 9.1.1 计算思维的提出计算思维的提出 科学科学是反映人们对自然、社是反映人们对自然、社会、思维等现实世界各种现象的会、思维等现实世界各种现象的客观规律的知识体系，而科学发客观规律的知识体系，而科学发现则是在科学活动中对未知事物现则是在科学活动中对未知事物或规律的揭示，主要包括事实的或规律的揭示，主要包括事实的发现和理论的提出。达尔文说过，发现和理论的提出。达尔文说过，科学就是整理事实，从中发现规科学就是整理事实，从中发现规律，做出结论律，做出结论。9.

5、1.2 9.1.2 科学方法与科学思维科学方法与科学思维 科技科技创新创新（科学发现与技术创新）（科学发现与技术创新）科科 学学 知知 识识计算思维计算思维理论思维理论思维实验思维实验思维 科学界科学界一般认为，科学方法分为理论、实验和计算三大类。与三一般认为，科学方法分为理论、实验和计算三大类。与三大科学方法相对的是三大科学思维，理论思维以数学为基础，实验思大科学方法相对的是三大科学思维，理论思维以数学为基础，实验思维以物理等学科为基础，计算思维以计算机科学为基础。三大科学思维以物理等学科为基础，计算思维以计算机科学为基础。三大科学思维构成了科技创新的三大维构成了科技创新的三大支拄。支拄。作

6、为三大科学思维支柱之一，并具有作为三大科学思维支柱之一，并具有鲜明时代特征的计算思维，正在引起我们国家的高度重视。鲜明时代特征的计算思维，正在引起我们国家的高度重视。1 1计算思维计算思维的的概念性定义概念性定义 计算计算思维的概念性定义主要包含以下两个方面：思维的概念性定义主要包含以下两个方面：（1）计算思维的）计算思维的内涵内涵 按照按照周以真教授的观点，计算思维是指运用计算机科学的基础概念进周以真教授的观点，计算思维是指运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算

7、思维建立在计算过程的能力和限制之上，由人或机器执列思维活动。计算思维建立在计算过程的能力和限制之上，由人或机器执行。计算思维的本质是抽象（行。计算思维的本质是抽象（Abstraction）和自动化（）和自动化（Automation）。）。（2）计算思维的要素）计算思维的要素 计算计算思维补充并结合了数学思维和工程思维，在其研究中提出体现计思维补充并结合了数学思维和工程思维，在其研究中提出体现计算思维的重点是抽象的过程，而计算抽象包括（并不限于）：算法、数法算思维的重点是抽象的过程，而计算抽象包括（并不限于）：算法、数法结构、状态机、语言、逻辑和语义、启发式、控制结构、通信、结构结构、状态机、语

8、言、逻辑和语义、启发式、控制结构、通信、结构。9.1.3 9.1.3 计算思维的内容计算思维的内容2 2计算思维计算思维的的操作性定义操作性定义 计算计算思维的操作性定义来源于应用研究，主要讨论计算思维在跨学科思维的操作性定义来源于应用研究，主要讨论计算思维在跨学科领域中的具体表现、如何应用以及如何培养等问题领域中的具体表现、如何应用以及如何培养等问题。计算。计算思维的操作性定思维的操作性定义主要包括以下几个方面义主要包括以下几个方面:（1）计算思维是问题解决的）计算思维是问题解决的过程过程（2）计算思维要素的具体体现）计算思维要素的具体体现（3）计算思维体现出的素质）计算思维体现出的素质 以

9、上以上三个方面共同构成了计算思维的操作性定义。操作性定义明确了三个方面共同构成了计算思维的操作性定义。操作性定义明确了计算思维这个抽象概念在实际活动中现实而具体的体现（包括能力和品计算思维这个抽象概念在实际活动中现实而具体的体现（包括能力和品质），使这一概念可观测、可评价，从而直接为教育质），使这一概念可观测、可评价，从而直接为教育培养过程提供有效的培养过程提供有效的参考。参考。9.1.3 9.1.3 计算思维的内容计算思维的内容3 3计算思维计算思维的的完整定义完整定义 计算计算思维的理论研究与应用研究密切相关、相辅相成，共同构成了对思维的理论研究与应用研究密切相关、相辅相成，共同构成了对计

10、算思维的完整研究计算思维的完整研究。计算。计算思维的概念性定义植根于计算科学学科领域，思维的概念性定义植根于计算科学学科领域，同时与思维科学、哲学交叉，从计算科学出发形成对计算思维的理解和认同时与思维科学、哲学交叉，从计算科学出发形成对计算思维的理解和认识，适用于指导对计算思维本身进行的理论研究。计算思维的操作性定义识，适用于指导对计算思维本身进行的理论研究。计算思维的操作性定义适用于对计算思维能力的培养以及计算思维的应用适用于对计算思维能力的培养以及计算思维的应用研究。研究。因此计算思维的因此计算思维的概念性定义和操作性定义彼此支撑和互补，共同构成计算思维的完整定义。概念性定义和操作性定义彼

11、此支撑和互补，共同构成计算思维的完整定义。计算思维的完整定义指导了计算思维在计算科学学科领域及跨学科领域中计算思维的完整定义指导了计算思维在计算科学学科领域及跨学科领域中的研究、发展和实践的研究、发展和实践。9.1.3 9.1.3 计算思维的内容计算思维的内容4 4计算思维的方法与特征计算思维的方法与特征 周以真周以真教授教授将将计算计算思维归纳思维归纳为如下七类方法为如下七类方法。计算计算思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难思维是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法；的问题重新阐释成一个我们知道问题怎样解决的思维

12、方法；计算计算思维是一种递归思维，是一种并行处理，是一种把代码译成数思维是一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法；据又能把数据译成代码，是一种多维分析推广的类型检查方法；计算计算思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂思维是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是基于关注点分离的方法（系统设计的方法，是基于关注点分离的方法（SoC方法）；方法）；计算计算思维是一种选择合适的方式去陈述一个问题，或对一个问题的思维是一种选择合适的方式去陈述一个问题，或对一个问题的相关方面建模使其易于处理的思维方

13、法；相关方面建模使其易于处理的思维方法；计算计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法；最坏情况进行系统恢复的一种思维方法；计算计算思维是利用启发式推理寻求解答，也即在不确定情况下的规划、思维是利用启发式推理寻求解答，也即在不确定情况下的规划、学习和调度的思维方法；学习和调度的思维方法；计算计算思维是利用海量数据来加快计算，在时间和空间之间，在处理思维是利用海量数据来加快计算，在时间和空间之间，在处理能力和存储容量之间进行折衷的思维方法能力和存储容量之间进行折衷的思维方法。6.3.3 6.3

14、.3 计算思维的内容计算思维的内容4 4计算思维的方法与特征计算思维的方法与特征 周以真周以真教授以计算思维是什么和不是什么的描述形式对计算思教授以计算思维是什么和不是什么的描述形式对计算思维的特征进行了维的特征进行了总结总结。9.1.3 9.1.3 计算思维的内容计算思维的内容 计算思维是什么计算思维是什么计算思维不是什么计算思维不是什么（1）是概念化 不是程序化（2）是根本的 不是刻板的技能（3）是人的思维 不是计算机的思维（4）是思想 不是人造物（5）是数学与工程思维的互补与融合 不是空穴来风（6）面向所有的人，所有的地方 不局限于计算学科 1 1社会的发展要求培养计算思维社会的发展要求

15、培养计算思维能力能力 在在当今社会，计算思维成为人们认识和解决问题的重当今社会，计算思维成为人们认识和解决问题的重要基本能力之一，一个人若不具备计算思维的能力，将在要基本能力之一，一个人若不具备计算思维的能力，将在就业竞争中处于劣势；一个国家若不使广大受教育者得到就业竞争中处于劣势；一个国家若不使广大受教育者得到计算思维能力的培养，在激烈竞争的国际环境中将处于落计算思维能力的培养，在激烈竞争的国际环境中将处于落后地位。计算思维，不仅是计算机专业人员应该具备的能后地位。计算思维，不仅是计算机专业人员应该具备的能力，而且也是所有受教育者应该具备的能力，它蕴含着一力，而且也是所有受教育者应该具备的能

16、力，它蕴含着一整套解决一般问题的方法与技术。为此需要大力推动计算整套解决一般问题的方法与技术。为此需要大力推动计算思维观念的普及，在教育中应该提倡并注重计算思维的培思维观念的普及，在教育中应该提倡并注重计算思维的培养，促进在教育过程中对学生计算思维能力的培养，使学养，促进在教育过程中对学生计算思维能力的培养，使学习者具备较好的计算思维能力，以此来提高在未来国际环习者具备较好的计算思维能力，以此来提高在未来国际环境中的竞争力境中的竞争力。9.1.4 9.1.4 计算思维能力的培养计算思维能力的培养 2 2大学要重视运用计算思维解决问题的大学要重视运用计算思维解决问题的能力能力 大学大学计算机基础

17、教育的本质仍然是计算机应用的教育。为此，需要计算机基础教育的本质仍然是计算机应用的教育。为此，需要在目前的基础上强调计算思维的培养，通过计算机基础教育与计算思维在目前的基础上强调计算思维的培养，通过计算机基础教育与计算思维相融合，在进行计算机应用教育的同时，可以培养学生的计算思维意识，相融合，在进行计算机应用教育的同时，可以培养学生的计算思维意识，帮助学习者获得更有效的应用计算机的思维方式。其目的是通过提升计帮助学习者获得更有效的应用计算机的思维方式。其目的是通过提升计算思维能力更好地解决日常问题，更好地解决本专业问题。计算思维培算思维能力更好地解决日常问题，更好地解决本专业问题。计算思维培养

18、的目的应该满足这一要求。养的目的应该满足这一要求。从从计算思维的概念性定义和操作性定义的属性可知，计算思维在大计算思维的概念性定义和操作性定义的属性可知，计算思维在大学阶段应该正确处理计算机基础教育面向应用与计算思维的关系。对于学阶段应该正确处理计算机基础教育面向应用与计算思维的关系。对于所有接受计算机基础教育的学习者，应以计算机应用为目标，通过计算所有接受计算机基础教育的学习者，应以计算机应用为目标，通过计算思维能力的培养更好地服务于其专业领域的研究；对于以研究计算思维思维能力的培养更好地服务于其专业领域的研究；对于以研究计算思维为目标的学习者（如计算机专业、哲学类专业研究人员），需要更深入

19、为目标的学习者（如计算机专业、哲学类专业研究人员），需要更深入地进行计算思维相关理论和实践的研究地进行计算思维相关理论和实践的研究。9.1.4 9.1.4 计算思维能力的培养计算思维能力的培养 9.2.1 9.2.1 算法的基本概念算法的基本概念9.2.2 9.2.2 算法的表示方法算法的表示方法9.2.3 9.2.3 算法设计的基本方法算法设计的基本方法9.2 9.2 算法设计算法设计1算法的基本算法的基本特征特征（1）确定性确定性。在在算法的设计中，算法的每个步骤必须要有确切的含义，不允算法的设计中，算法的每个步骤必须要有确切的含义，不允许有模糊的解释，也不能有多义性许有模糊的解释，也不能

20、有多义性。即每个操作都应当是清晰的、无二义性即每个操作都应当是清晰的、无二义性的的。（2）有有穷穷性性。算法算法的有穷性是指在一定的时间内能够完成，即一个算法应包的有穷性是指在一定的时间内能够完成，即一个算法应包含有限的操作步骤且在有限的时间内能够执行完毕含有限的操作步骤且在有限的时间内能够执行完毕。（3）有效性有效性。算法算法中的每个步骤都应当能有效地执行，并得到确定的结果中的每个步骤都应当能有效地执行，并得到确定的结果。（4）有零有零个或多个个或多个输入输入。在在算法执行的过程中需要从外界取得必要的信息，算法执行的过程中需要从外界取得必要的信息，即输入必要的数据，并以此为基础解决某个特定问

21、题即输入必要的数据，并以此为基础解决某个特定问题。所谓。所谓零个输入是指算零个输入是指算法也可以没有输入，此时就需要算法本身给出必要的初始条件（初值）法也可以没有输入，此时就需要算法本身给出必要的初始条件（初值）。（5）有有一个或多个一个或多个输出输出。设计设计算法的目的就是要解决问题，算法的计算结果算法的目的就是要解决问题，算法的计算结果就是输出。没有输出的算法是毫无意义的。一个就是输出。没有输出的算法是毫无意义的。一个算法算法可以有可以有一一个或多个个或多个输出输出。输出结果的输出结果的形式形式也也可以可以有有多种多种形式。形式。9.2.1 9.2.1 算法的基本概念算法的基本概念 2 2

22、算法的基本要素算法的基本要素 算法算法由由操作操作和和控制结构控制结构两个要素组成。两个要素组成。（1）对对数据对象的运算和操作数据对象的运算和操作 计算机计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。计算机程序就是按解执行的所有指令的集合称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列题要求从计算机指令系统中选择合适的指令所组成的指令序列。在在一般的计算机系统中，对数据对象基本的运算和操作有以下四类。一般的计算机系统中，对

23、数据对象基本的运算和操作有以下四类。算术运算：算术运算：主要包括主要包括“加加”、“减减”、“乘乘”、“除除”、“求余求余”等等算术运算。算术运算。关系运算：关系运算：主要包括主要包括“大于大于”、“大于等于大于等于”、“小于小于”、“小于等小于等于于”、“等于等于”、“不等于不等于”等关系运算。等关系运算。逻辑运算：逻辑运算：主要包括主要包括“与与”、“或或”、“非非”等逻辑运算。等逻辑运算。数据传输：数据传输：主要包括输入、输出、赋值等数据传送操作主要包括输入、输出、赋值等数据传送操作。9.2.1 9.2.1 算法的基本概念算法的基本概念 （2）控制结构控制结构 算法算法的功能不仅取决于所

24、选用的操作，还与各操作之间的顺的功能不仅取决于所选用的操作，还与各操作之间的顺序有关。在算法中，各操作之间的执行顺序又称算法的控制结构。序有关。在算法中，各操作之间的执行顺序又称算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，也直接反映了算法的设计是否符合结构化原则。操作的执行顺序，也直接反映了算法的设计是否符合结构化原则。一般一般的算法控制结构有三种：的算法控制结构有三种：顺序结构顺序结构、选择结构选择结构和和循环结循环结构构。描述算法的工具通常有传统。描述算法的工具通常有传统流程图流程图、N-S

25、结构图结构图和和算法描述算法描述语言语言等等。9.2.1 9.2.1 算法的基本概念算法的基本概念3 3算法的分类算法的分类 根据根据待解决问题的形式模型和求解要求，算法分为数值运算算法待解决问题的形式模型和求解要求，算法分为数值运算算法和非数值运算算法两大类。和非数值运算算法两大类。（1）数值数值运算算法运算算法 数值数值运算算法是以数学方式表示的问题求数值解的方法。例如，运算算法是以数学方式表示的问题求数值解的方法。例如，代数方程计算、线性方程组求解、矩阵计算、数值积分、微分方程求代数方程计算、线性方程组求解、矩阵计算、数值积分、微分方程求解等。通常，数值运算有现成的模型，这方面的现有算法

26、比较成熟。解等。通常，数值运算有现成的模型，这方面的现有算法比较成熟。（2）非非数值运算算法数值运算算法 非非数值运算算法通常为求非数值解的方法。例如，排序、查找、数值运算算法通常为求非数值解的方法。例如，排序、查找、表格处理、文字处理、人事管理、车辆调度等。非数值运算算法种类表格处理、文字处理、人事管理、车辆调度等。非数值运算算法种类繁多，要求各自不同，难以规范化繁多，要求各自不同，难以规范化。9.2.1 9.2.1 算法的基本概念算法的基本概念1 1自然语言表示自然语言表示 自然语言自然语言（Natural Language）就是人们日常生活中使用的语言，如）就是人们日常生活中使用的语言，

27、如中文、或其他语言等，用自然语言来描述算法就是算法的自然语言表示。中文、或其他语言等，用自然语言来描述算法就是算法的自然语言表示。【例【例9-1】用自然语言来描述输入矩形的两个边，求矩形的面积和周长的】用自然语言来描述输入矩形的两个边，求矩形的面积和周长的算法，其中假设算法，其中假设a、b代表矩形的两个边；代表矩形的两个边；s、l分别代表矩形的面积和周长。分别代表矩形的面积和周长。Step1：分别输入：分别输入2个边给个边给a、b；Step2：计算矩形面积：计算矩形面积s=a*b；Step3：计算矩形周长：计算矩形周长l=2*(a+b)；Step4：依次输出面积：依次输出面积s和周长和周长l。

28、使用使用自然语言描述算法的优点是通俗易懂，没有学过算法相关知识的自然语言描述算法的优点是通俗易懂，没有学过算法相关知识的人也能够看懂算法的执行过程。但是，自然语言本身所固有的不严密性使人也能够看懂算法的执行过程。但是，自然语言本身所固有的不严密性使得这种描述方法存在以下缺陷：得这种描述方法存在以下缺陷：文字冗长，容易产生歧义性，往往需要根据上下文才能判别其含义。文字冗长，容易产生歧义性，往往需要根据上下文才能判别其含义。难以描述算法中的分支和循环等结构，不够方便直观难以描述算法中的分支和循环等结构，不够方便直观。9.2.2 9.2.2 算法的表示方法算法的表示方法2 2流程图流程图 流程图流程

29、图（Flow Chart）是一种传统的、广泛应用的算法描）是一种传统的、广泛应用的算法描述工具，也是最常见的算法图形化表达工具。流程图利用几何述工具，也是最常见的算法图形化表达工具。流程图利用几何图形的图框来代表各种不同的操作，用流程线来指示算法的执图形的图框来代表各种不同的操作，用流程线来指示算法的执行方向，它行方向，它使用规定使用规定的一些图框、线条来形象、直观地描述算的一些图框、线条来形象、直观地描述算法处理过程。与自然语言相比，流程图可以清晰、直观、形象法处理过程。与自然语言相比，流程图可以清晰、直观、形象地反应控制结构的过程地反应控制结构的过程。9.2.2 9.2.2 算法的表示方法

30、算法的表示方法符号名称图形功能起止框表示算法的开始或结束处理框表示一般的处理操作，如计算、赋值等判断框表示对一个给定的条件进判断流程线或 用流程线连接各种符号，表示算法的执行顺序输入/输出框表示算法的输入/输出操作连接点成对出现，同一对连接点内标注相同的数字或文字，用于将不同位置的流程线连接起来，避免流程线的交叉或过长注释框对当前步骤进行必要的注释、说明常见常见流程图符号流程图符号9.2.2 9.2.2 算法的表示方法算法的表示方法 2 2流程图流程图 【例例9-2】使用流程图来描述输入矩形的两个边，】使用流程图来描述输入矩形的两个边，求矩形的面积和周长的算法，其中假设求矩形的面积和周长的算法

31、，其中假设a、b代表矩代表矩形的两个边；形的两个边；s、l分别代表矩形的面积和周长。分别代表矩形的面积和周长。分析分析：这个算法首先要输入矩形的两个边：这个算法首先要输入矩形的两个边a、b，然后根据求矩形面积和周长的计算公式，计算面积然后根据求矩形面积和周长的计算公式，计算面积a和周长和周长l，最后将结果输出。具体流程图如，最后将结果输出。具体流程图如图所图所示示。从从本例可以看出，使用流程图描述算法，简单、本例可以看出，使用流程图描述算法，简单、直观，流程清晰，易看易懂，能够比较清楚地显示直观，流程清晰，易看易懂，能够比较清楚地显示出各个符号之间的逻辑关系，因此流程图是一种描出各个符号之间的

32、逻辑关系，因此流程图是一种描述算法的好工具。述算法的好工具。9.2.2 9.2.2 算法的表示方法算法的表示方法 为了为了提高算法的质量，便于阅读理解，应限制流程的随意提高算法的质量，便于阅读理解，应限制流程的随意转向。为了达到这个目的，人们规定了转向。为了达到这个目的，人们规定了3种基本结构，由这些种基本结构，由这些基本结构按一定规律组成一个算法基本结构按一定规律组成一个算法结构结构。（1）顺序顺序结构结构 顺序顺序结构是最简单、最常用的一结构是最简单、最常用的一种结构，如种结构，如图所图所示。图中操作示。图中操作A和操作和操作B按照出现的先后顺序依次执行。按照出现的先后顺序依次执行。上面例

33、上面例9-2就是一个顺序结构的算就是一个顺序结构的算法，操作按照算法的流程，自上而下，法，操作按照算法的流程，自上而下，依次执行。依次执行。9.2.2 9.2.2 算法的表示方法算法的表示方法 （2）选择选择结构结构 选择选择结构又称为分支结构，如结构又称为分支结构，如图所图所示。这种结构在处理问题时根据条示。这种结构在处理问题时根据条件进行判断和选择。图件进行判断和选择。图(a)是一个是一个“双分支双分支”选择结构，如果条件选择结构，如果条件p成立则成立则执行处理框执行处理框A，否则执行处理框，否则执行处理框B。图。图(b)是一个是一个单分支单分支选择结构，如果选择结构，如果条件条件p成立则

34、执行处理框成立则执行处理框A，否则直接退出结构，否则直接退出结构。（a）“双分支双分支”选择结构选择结构 （b）单分支单分支选择选择结构结构选择结构流程图选择结构流程图9.2.2 9.2.2 算法的表示方法算法的表示方法9.2.2 9.2.2 算法的表示方法算法的表示方法 （3）循环循环结构结构 循环循环结构又称为重复结构，在处理问题时根据给定条件重复执行某一结构又称为重复结构，在处理问题时根据给定条件重复执行某一部分的操作。循环结构有当型和直到型两种类型。部分的操作。循环结构有当型和直到型两种类型。当当型循环结构如型循环结构如图（图（a）所示）所示，其表达的算法含义是：当条件，其表达的算法含

35、义是：当条件p成立时，成立时，执行处理框执行处理框A，执行完处理框，执行完处理框A后，再判断条件后，再判断条件p是否成立，若条件是否成立，若条件p仍然仍然成立，则再次执行处理框成立，则再次执行处理框A，如此反复，直至条件，如此反复，直至条件p不成立才结束循环。不成立才结束循环。直到直到型循环结构如型循环结构如图（图（b）所示。其表达的算法含义是：先执行处理）所示。其表达的算法含义是：先执行处理框框A，再判断条件，再判断条件p是否成立，如果条件不成立，则再次执行处理框是否成立，如果条件不成立，则再次执行处理框A，如，如此反复，直至条件此反复，直至条件p成立才结束循环成立才结束循环。比较项目比较项

36、目当型循环结构当型循环结构直到型循环结构直到型循环结构何时判断条件是否成立何时判断条件是否成立先判断，后执行先执行，后判断何时执行循环何时执行循环条件成立条件不成立循环至少执行次数循环至少执行次数0次1次当型循环结构与直到型循环结构的当型循环结构与直到型循环结构的比较比较9.2.2 9.2.2 算法的表示方法算法的表示方法循环循环结构结构流程图流程图（a）当当型循环结构型循环结构 （b）直到型循环直到型循环结构结构9.2.2 9.2.2 算法的表示方法算法的表示方法 【例例9-4】输出输出30以内的奇数。使用流程以内的奇数。使用流程图描述其算法。图描述其算法。分析分析：输出：输出30以内的奇数

37、，即以内的奇数，即1、3、5、7等。可以看出数字的规律是每次增加等。可以看出数字的规律是每次增加2，可以先将可以先将1赋给一个数赋给一个数i，称为赋初值，然后，称为赋初值，然后每次给每次给i这个数增加这个数增加2，并输出，由此得到，并输出，由此得到1、3、5、7等的输出。由于要反复做同一个等的输出。由于要反复做同一个操作（每次操作（每次i加加2并输出），可以利用循环结并输出），可以利用循环结构，并设置循环条件为构，并设置循环条件为i30。具体流程图如。具体流程图如图所图所示示。9.2.2 9.2.2 算法的表示方法算法的表示方法三三种基本种基本结构结构的说明的说明 从从上述三种基本结构的介绍可

38、以看出，三种基本结构都是上述三种基本结构的介绍可以看出，三种基本结构都是只有一个入口、一个出口，这种单入口、单出口的基本结构，只有一个入口、一个出口，这种单入口、单出口的基本结构，限制了无规则的转向流程，保证了算法的限制了无规则的转向流程，保证了算法的“结构化结构化”。计算机。计算机科学家已经证明，使用以上科学家已经证明，使用以上3种基本结构顺序组合而成的算法种基本结构顺序组合而成的算法结构，可以解决任意复杂的问题，而由这三种基本结构所构成结构，可以解决任意复杂的问题，而由这三种基本结构所构成的算法就是所谓的的算法就是所谓的结构化结构化的算法的算法 在在实际问题的处理过程中，只要根据解题的实际

39、需要，将实际问题的处理过程中，只要根据解题的实际需要，将完成各项子功能的各种基本结构顺序组合，构造完整的算法；完成各项子功能的各种基本结构顺序组合，构造完整的算法；在操作时，按照算法的流程，自上而下，依次执行，即可完成在操作时，按照算法的流程，自上而下，依次执行，即可完成问题的处理过程问题的处理过程。9.2.2 9.2.2 算法的表示方法算法的表示方法3 3N-SN-S流程图流程图 流程图流程图通过一些特定意义的图形、流程线及简要的文字说通过一些特定意义的图形、流程线及简要的文字说明，能清晰明确地表示程序的运行过程。但在使用过程中人们明，能清晰明确地表示程序的运行过程。但在使用过程中人们也发现

40、，由于采用了结构化的算法设计，可以用三种基本结构也发现，由于采用了结构化的算法设计，可以用三种基本结构组成的构件顺序组合成各种复杂的算法结构，这样程序流程线组成的构件顺序组合成各种复杂的算法结构，这样程序流程线就不一定是必需的了。就不一定是必需的了。于是美国学者于是美国学者Nassi和和Shneiderman提出提出了一种新的程序控制流程图的表示方法，使用矩形框来表示顺了一种新的程序控制流程图的表示方法，使用矩形框来表示顺序、选择和循环这三种基本结构。在设计一个算法时，它把整序、选择和循环这三种基本结构。在设计一个算法时，它把整个算法写在一个大框图内，这个大框图由若干个基本结构的框个算法写在一

41、个大框图内，这个大框图由若干个基本结构的框图构成，通过基本结构的矩形框嵌套，可以表示各种复杂的程图构成，通过基本结构的矩形框嵌套，可以表示各种复杂的程序算法。这样的流程图表示方法称为序算法。这样的流程图表示方法称为N-S流程图。流程图。9.2.2 9.2.2 算法的表示方法算法的表示方法N-SN-S流程图流程图的三种基本的三种基本结构结构（a）顺序结构顺序结构 （b）选择选择结构结构程序命令组程序命令组A 程序命令组程序命令组B条件条件成立成立不成立不成立程序命令组程序命令组A程序命令组程序命令组B（a）当当型循环结构型循环结构 （b）直到型循环直到型循环结构结构当型循环条件成立当型循环条件成

42、立循环体循环体直到型循环条件不成立直到型循环条件不成立循环体循环体9.2.2 9.2.2 算法的表示方法算法的表示方法 N-S流程图有如下的优点：流程图有如下的优点：它它强制设计人员按结构化程序设计方法进行思考并描述强制设计人员按结构化程序设计方法进行思考并描述他的设计方案他的设计方案。这。这就有效地保证了设计的质量，从而也保就有效地保证了设计的质量，从而也保证了程序的质量证了程序的质量。N-S图形象直观图形象直观，容易，容易理解设计意图，为编程、复查、理解设计意图，为编程、复查、选择测试用例、维护都带来了方便选择测试用例、维护都带来了方便。N-S图简单、易学易用，可用于软件教育和其他方面。图

43、简单、易学易用，可用于软件教育和其他方面。N-S图的控制转移不能任意规定，必须遵守结构化程序图的控制转移不能任意规定，必须遵守结构化程序设计的要求，由此，避免了算法的随意转向。设计的要求，由此，避免了算法的随意转向。N-S图很容易表现嵌套关系，也可以表示模块的层次结图很容易表现嵌套关系，也可以表示模块的层次结构构。9.2.2 9.2.2 算法的表示方法算法的表示方法4 4伪代码伪代码 伪代码伪代码（Pseudocode）是一种介于自然语言和程序设计语言之间，以）是一种介于自然语言和程序设计语言之间，以编程语言的书写形式描述算法的工具。使用伪码的目的是使被描述的算法编程语言的书写形式描述算法的工

44、具。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言（可以容易地以任何一种编程语言（C+、VB、Java等）实现。等）实现。使用使用伪代码，往往将程序设计语言中与算法关联度小的部分省略（如伪代码，往往将程序设计语言中与算法关联度小的部分省略（如变量的定义等），而更关注于算法本身的描述。相比于程序设计语言变量的定义等），而更关注于算法本身的描述。相比于程序设计语言（C+、VB、Java等），它更类似自然语言，可以将整个算法运行过程的等），它更类似自然语言，可以将整个算法运行过程的结构用接近自然语言的形式描述出来。结构用接近自然语言的形式描述出来。伪代码伪代码结构清晰、代码简单、可读性好

45、，并且类似自然语言。伪代码结构清晰、代码简单、可读性好，并且类似自然语言。伪代码常常用来表达程序员开始编写代码前的想法，它常被用于在软件开发的实常常用来表达程序员开始编写代码前的想法，它常被用于在软件开发的实际编写代码过程之前表达程序的逻辑际编写代码过程之前表达程序的逻辑。9.2.2 9.2.2 算法的表示方法算法的表示方法【例【例9-5】使用伪代码来描述：输入使用伪代码来描述：输入3个数，打印输出其中最大的数。个数，打印输出其中最大的数。Begin（算法开始）（算法开始）输入输入 A，B，C IF AB 则则 AMax 否则否则 BMax IF CMax 则则 CMax Print Max

46、End（算法结束）（算法结束）在在上面的伪代码描述中，代码的部分与某些编程语言已经非常相似，上面的伪代码描述中，代码的部分与某些编程语言已经非常相似，再穿插着文字的描述，可以很清楚的表达程序的逻辑和编程的思路，由这再穿插着文字的描述，可以很清楚的表达程序的逻辑和编程的思路，由这个算法也可以很容易的转换为相应的程序个算法也可以很容易的转换为相应的程序。9.2.2 9.2.2 算法的表示方法算法的表示方法1 1基本算法基本算法 在在算法设计中，有一些算法比较典型，经常被使用到，如求和、累积算法设计中，有一些算法比较典型，经常被使用到，如求和、累积（连续相乘）、求最大或最小值等。（连续相乘）、求最大

47、或最小值等。（1）求和求和 在在解决实际问题时经常遇到求和解决实际问题时经常遇到求和问题问题：计算计算1+2+3+99+100的值。的值。统计统计100到到200之间能够被之间能够被11整除的数的个数。整除的数的个数。输入若干学生的成绩，计算总分和平均分。输入若干学生的成绩，计算总分和平均分。求和求和可能是一组数据序列求和、可能是对符合某些条件的计数（依次可能是一组数据序列求和、可能是对符合某些条件的计数（依次加加1求和）、还有可能是对一组数据的统计求和求和）、还有可能是对一组数据的统计求和。求和求和算法常用于以下几种情况：算法常用于以下几种情况：公式求数据序列的和。其中每两项之间由公式求数据

48、序列的和。其中每两项之间由+连接，且每项具有一连接，且每项具有一定规律。定规律。统计具有某种特征或满足某个条件的数据的个数，即计数。统计具有某种特征或满足某个条件的数据的个数，即计数。计算一组数据的和或平均值（计算平均值时，应先求数据的和）计算一组数据的和或平均值（计算平均值时，应先求数据的和）。9.2.3 9.2.3 算法设计的基本方法算法设计的基本方法求和算法求和算法的描述的描述：（sum表示求和的结果、表示求和的结果、xx表示需要加入表示需要加入的的数数）设置设置sum的初值；的初值；根据实际需要为加数根据实际需要为加数xx输入初值；输入初值；利用循环操作，将加数利用循环操作，将加数xx

49、依次加入到依次加入到和和sum中，中，sum=sum+xx；在每次循环后设定新的加数给在每次循环后设定新的加数给xx；循环结束后，循环结束后，sum中的值即为最终的中的值即为最终的结果。结果。求和算法求和算法的的流程图如图所流程图如图所示示。9.2.3 9.2.3 算法设计的基本方法算法设计的基本方法求和求和算法算法中中的关键点：的关键点：最最关键的操作是在循环中的关键的操作是在循环中的sum=sum+xx语句语句，该语句是将，该语句是将sum本身的值加上本身的值加上xx的值，又存入的值，又存入sum中，因此它会随着循环的进行，将加数中，因此它会随着循环的进行，将加数xx依次的累加到依次的累加

50、到sum中中。对于对于数据序列的求和（如数据序列的求和（如1+2+3+等），等），xx是按规律变化的数字，是按规律变化的数字，“设定设定xx新值新值”的操作可以利用这种规律，改变的操作可以利用这种规律，改变xx的值（如的值（如xx=xx+1）；对于对于计数类统计，计数类统计，xx值就是值就是1，随着循环的进行，每次，随着循环的进行，每次sum累加累加1，实，实现计数功能现计数功能；对于对于实际的一组数据的求和（如分数求和），实际的一组数据的求和（如分数求和），xx就是每次输入的分数就是每次输入的分数。求和求和算法中另一个重要的点是算法中另一个重要的点是sum和和xx的赋初值的赋初值，它要确保求