大学计算机-计算思维与人工智能（第2版）课件 第3章 算法与Raptor程序设计

第3章算法与Raptor程序设计content重点难点重点：1.算法的概念及特征2.算法表示3.Raptor程序设计难点：1.Raptor程序设计Contents目录3.1程序设计概述3.2算法3.3Raptor程序设计3.1程序设计概述

想一想，你了解什么样的程序设计语言？程序设计概述程序设计的定义：

◦

程序设计是计算机科学与技术的基础，指通过编程语言，按逻辑结构编写程序解决问题或实现功能的过程。

◦

不仅是写代码，涵盖问题理解分析、思路设计、框架构建、调试优化等步骤。

◦

需应用计算机科学基本概念，注重程序可维护性、可扩展性和性能。

程序设计基础——定义、目标与步骤程序设计的目标提高效率简化操作解决实际问题目标·通过合理的需求分析和系统设计，程序员可以将问题分解为具体的任务，并通过编写代码逐步实现问题的解决。·通过设计合理的算法和数据结构，程序能够比人工操作更快、更准确地完成任务。·注重前端界面的友好性和易用性，使得用户能够在最短的时间内掌握操作方法。程序设计的目标健壮性与稳定性可维护性和可扩展性目标·程序设计不仅要关注当前需求的实现，还要考虑到未来可能的变化。·一个成功的程序应该具备在未来添加新功能、处理更大数据量或支持更多用户的能力。·程序应考虑到可能的错误，并采取措施进行处理。·通过合理的异常处理机制，程序能够在遇到错误时及时报告或进行自我修复，避免程序崩溃或造成系统不稳定。总

结复杂工程未来挑战程序设计是集分析、设计、实现、调试和优化于一体的复杂工程。不仅是编写代码，重要的是通过合理的设计和实现，解决实际问题、提高效率、简化操作、保证可维护性与可扩展性，并确保程序的健壮性和稳定性。未来的程序设计不仅仅是技术的挑战，更是对创造力和逻辑思维的全面考验。程序设计的基本步骤1.问题分析程序设计步骤4．编码实现3．系统设计与结构设计2．设计算法5．测试与调试6．维护与优化1.问题分析程序设计步骤4．编码实现2．设算法5．测试与调试程序员需要与用户或需求方进行沟通，明确需求的细节、限制条件和期望目标。此时的任务是提炼出问题的核心，确定需要解决的关键点。此阶段的成果是问题的定义和需求说明，通常通过文档记录下来，确保所有参与开发的人员对问题有统一的理解。2．设计算法程序设计步骤4．编码实现2．设算法5．测试与调试算法是解决问题的步骤和方法，是程序的核心。算法的设计的原则：•正确性：算法必须能够正确地解决问题，返回正确的结果。•高效性：在计算资源有限的情况下，算法的时间和空间复杂度应尽量小，能够快速处理大量数据。•可读性：算法应易于理解和实现，避免过于复杂的设计。•鲁棒性：算法需要考虑到各种异常情况，如输入数据的合法性、系统资源的约束等，能够应对各种可能的错误或异常。3．系统设计与结构设计程序设计步骤4．编码实现2．设算法5．测试与调试此阶段的目标是将问题和算法转化为具体的程序架构，并规划程序的模块和数据流。通常涉及以下内容：•模块划分：将整个程序分解成多个相对独立的模块，每个模块负责完成特定的功能。模块之间通过接口进行数据交换和通信。•数据结构设计：根据问题的需求选择合适的数据结构，以便在程序中高效地存储和操作数据。数据结构的选择直接影响程序的执行效率。•界面设计：如果程序需要与用户进行交互，那么用户界面的设计是必须考虑的部分。界面设计要考虑到用户体验，使得操作简单直观。4．编码实现程序设计步骤4．编码实现2．设算法5．测试与调试此阶段的目标是将设计转化为机器能够执行的程序。需要遵循编程规范：•命名规范：变量名、函数名和类名等应具备明确的意义，并符合团队的命名约定。•注释和文档：代码应包含适当的注释，说明代码的作用和使用方法。良好的注释能够提高代码的可维护性，帮助后续的开发和调试。•代码结构：代码应清晰、简洁、模块化，避免冗余和重复的代码。合适的代码结构可以提升程序的可读性和可扩展性。5．测试与调试程序设计步骤4．编码实现2．设算法5．测试与调试测试和调试的目的：确保程序的正确性和稳定性，并解决在开发过程中出现的各种错误或异常。•单元测试：测试程序的每个模块或函数是否按照预期工作。•集成测试：将多个模块组合在一起进行测试，确保模块之间的协作和数据传输没有问题。•性能测试：对程序的性能进行测试，评估程序在高负载、高并发等情况下的表现，确保其效率满足需求。•异常测试：测试程序在遇到异常情况时的表现，如输入数据不合法、系统资源不足等，确保程序能够稳定运行。6．维护与优化程序设计步骤4．编码实现2．设算法5．测试与调试维护通常包括：修复bug、更新功能、处理用户反馈等；而优化则是提升程序性能和效率，使其能够更好地应对增长的负载和数据量。程序优化的内容包括代码优化、算法优化、数据结构优化等。3.2算法1.什么是算法算法是按照一定的方法和步骤解决问题的过程。

算法是一系列解决问题的清晰指令，能够对一定规范的输入，在有限时间内获得所要求的输出。广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法。通俗理解：算法就是解决一个问题的方法。据此而论，编写程序解决的任何一个问题都可以叫做算法。

2.算法举例3.算法在计算机科学中的应用（1）计算机算法的引入算法（Algorithm）理论处于计算机科学的核心地位。想要使用计算机解决问题，就要设计该问题的算法，要给出解决该问题所需的一系列解题步骤。算法有什么用？提高计算机i运行的效率，节约内存空间没有好算法，计算机完成一件工作可能需要1年；有好算法，计算机完成同样的工作可能只要几秒。（1）计算机算法的引入计算机软件的重要内容之一是程序，程序是计算机指令的序列，计算机一步一步地执行这个指令序列，就完成了希望它所做的事情。程序设计就是按照一定的要求编排一个合理的指令序列。程序设计主要包含两个方面:行为特性设计和结构特性设计。结构特性设计是指确定合适的数据结构，将程序处理的数据在计算机内部表示和存放。行为特性设计是确定要解决的实际问题的具体步骤，把全部解题过程完整地描述出来，这一过程就是算法设计。这就引出来一个很重要的公式：

著名计算机科学家沃思提出一个公式:数据结构+算法=程序（Algorithm+DataStructures=Programs）对数据的描述：数据结构(datastructure)对操作的描述：算法(algorithm)一个程序应包括两个方面的内容:凭借一句话获得图灵奖的Pascal之父.这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的“E=MC2”——一个公式展示出了程序的本质。以上的公式表明：1、算法与数据结构是密切相关的，算法的设计要与数据结构相适应。2、算法不等于程序，它不需考虑具体的机器，算法也不等于计算方法，它比计算方法更具体。算法与数据结构:程序员想拔高一个层次，数据结构和算法只是很小一部分，但却是很重要的一部分。判断一段程序的好坏，基于什么呢？其实很多方面，比如说可读性，可扩展性等，但还有一个可以量化的标准，就是空间和时间复杂度的分析。这是算法的内容。（2）算法的特征著名计算机科学家Knuth把算法的特征归纳以下5点：1974年度图灵奖。（2）算法的特征:著名计算机科学家Knuth把算法的特征归纳以下5点：一、有穷性（finiteness）

一个算法必须在有限个步骤之后结束。换句话说，一个算法必须在有限时间内完成，否则，该算法就失去了实际价值。因此，在算法中不能出现无限循环。数学中的无穷级数在计算时只能取有限项。二、确定性（definiteness）

算法中的每一个步骤都必须有明确的定义，不允许存在多义性和摸棱两可的解释。如“将X，Y两个数进行加减运算”，是做加法运算还是做减法运算,没有说清；再如“给变量X增加一个值”，增加一个值，具体是多少，没有说清。在算法中，这样含糊不清的步骤不允许出现。（2）算法的特征:三、能行性（effectiveness）

算法中的每一个步骤都是可以实现的，或可以分解为可执行的基本操作。例如

在算法中不能出现零做除数、在实数范围内对一个负数求平方根等情况。四、输入（input）

算法允许有零个或多个输入量。五、输出（output）

算法必须有一个或多个输出。根据以上讨论，我们对算法有了进一步的认识：算法是精确定义的一系列规则，这些规则指定了一系列的操作，经过有限步骤产生所求问题的解。（3）算法解决问题的类型计算机科学领域的问题大致可分为以下三种类型：一、判定性问题：这类问题给出的是与否的判别。例如

连通性问题（在计算机网络中判断两台主机是否连通、在社交网络中判断两个用户是否存在间接社交关系等，都可以抽象成连通性问题。）回路问题(网络回路、运输回路)，查找与排序问题，字符匹配问题等。二、最优化问题：这类问题是在所有可能的解中求出最优解。例如求函数的极值，最短路径问题，最小生成数问题等。三、函数计算问题：这类问题是在一定约束条件下求数值解。例如方程求根，矩阵运算，函数求值等。（4）一些重要的算法：A*搜寻算法BeamSearch二分取中查找算法Branchandbound数据压缩

Diffie–Hellman密钥协商Dijkstra’s算法动态规划欧几里得算法

最大期望（EM）算法快速傅里叶变换(FFT)哈希函数

堆排序归并排序RANSAC算法RSA加密演算法并查集Union-findViterbialgorithm4.程序设计语言ProgrammingLanguage程序设计语言的产生与发展思考：什么是计算机语言？计算机语言通常是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机工作的“符号系统”。计算机语言包括：机器语言、汇编语言、高级语言三类高级语言有：BASIC、C、C++、PASCAL、FORTRAN、智能化语言（LISP、Prolog、CLIPS、OpenCyc、Fazzy）、动态语言(Python、PHP、Ruby、Lua)等。程序设计语言的产生与发展随着计算机的发展，程序设计语言经历了从机器语言到高级语言的发展历程。高级语言的发展历程1、机器语言

机器语言：由一串“0”和“1”构成二进制代码，能够被计算机直接接受和执行的语言。优点：能够直接在计算机上执行。缺点：程序难以理解，程序设计任务繁重，效率低下，而且要求程序员必须经过专门的训练。00001101十进制的13 程序设计语言的产生与发展

2、汇编语言汇编语言：是一种类似英语缩略词且带有助记性符号的语言，每条汇编指令都和一条机器指令相对应，只是指令码和操作数都采用符号形式。这种语言与特定的机器和特定的微处理器有关，不能被机器直接接受，必须用一种语言翻译器将程序中的每条语句翻译成机器语言才能执行。

优点：程序更易理解。缺点：程序不能被机器直接接受，要经过翻译器翻译成机器语言。程序设计语言的产生与发展3、高级语言高级语言：不能被电脑直接识别，用高级语言编写的程序必须经过翻译器将其翻译成机器语言，才能在计算机上执行。第一个高级语言是Fortran。

优点：易于理解，移植性好。缺点：高级语言编写的程序要经过翻译器翻译成机器语言，才能在计算机上执行。程序设计语言的发展历史机器语言汇编语言高级语言面向过程面向对象CPU指令系统，由0、1序列构成的指令码组成如：10000000加

10010000减用助记符号描述的指令系统如ADDA,B程序设计是数据被加工的过程客观世界可以分类，对象是类的实例对象是数据和方法的封装对象间通过发送和接受消息发生联系程序设计关键是定义类，并由类派生对象冯.诺依曼结构：计算机运算器控制器存储器主机：I/O设备：键盘、显示器等中央处理器CPU面向机器的语言5.程序流程图FlowChart程序流程图的画法1为什么使用流程图2流程图的组成和画法3流程图的改进：N-S盒图（1）为什么使用流程图自然语言就是日常使用的语言，汉语或英语或其它语言。自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”自然语言表示的含义不严格，要根据上下文才能判断其正确含义。描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，程序设计一般不用自然语言描述算法。（1）为什么使用流程图例1：有两个存储单元a和b，要求将它们的值互换。

分析：按存储器的性质，如果将单元a的值直接送到单元b中，那么就会覆盖掉b原来的内容，因此，需要借助一个临时单元c来交换。

具体算法用自然语言表述如下：步骤1：将单元a的值送给单元c；步骤2：将单元b的值送给单元a；步骤3：将单元c的值送给单元b。（1）为什么使用流程图流程图通常采用一些几何图形来代表各种类型的操作，在图形内标明文字或符号来表示操作的内容，并用箭头来表示操作的顺序。用流程图表示算法，直观形象，易于理解.（2）流程图的组成和画法起止框输入/输出框判断框处理框流程线连接点（2）流程图的组成和画法算法三种基本结构的流程图画法（2）流程图的组成和画法（2）流程图的组成和画法（2）流程图的组成和画法例：求1+2+3+4+…+10用流程图进行描述。n+1=>n1=>ns+n=>s0=>sn≤10输出s是否针对流程图存在的缺点，I.Nassi和B.Shneiderman提出了结构化程序设计的流程图，称为N-S图，更能体现结构化程序设计的思想。推荐使用N-S图。

N-S图完全去掉了流程线，算法的所有处理步骤都写在一个大矩形框内（表示简单、符合结构化思想）（象堆积木）（3）流程图的改进:N-S盒图由于流程图允许使用箭头随意跳转，对表示算法的层次结构非常不利，且流程图占的篇幅较大，作图工作量也很大。

（3）流程图的改进:N-S盒图顺序结构：从前向后顺序执行程序选择结构：根据判断条件的结果选择执行程序。循环结构：根据条件反复的执行某一段程序若干次。0

s1nn≤10n+ssn+1n

输出s（3）流程图的改进:N-S盒图n+1=>n1=>ns+n=>s0=>sn≤10输出s是否例：求1+2+3+4+…+10用流程图进行描述。流程图例：求10个任意整数中的最大数用N-S图进行描述输入max

1

n

n<10

输入x

T

x>max?F

xmaxn+1n输出max（3）流程图的改进:N-S盒图3.3Raptor程序设计为什么要学习程序设计？由于计算思维的核心之一是算法思维，同时算法思维也是计算机科学的精髓。而算法思维的实现离不开程序设计，所以对于计算思维的学习和认识，必须从程序设计开始。为什么要使用RAPTOR？RAPTOR（theRapidAlgorithmicPrototypingToolforOrderedReasoning--用于有序推理的快速算法原型工具），是一种基于流程图的可视化程序设计环境，为程序和算法设计的基础课程教学提供实验环境。使用RAPTOR设计的程序和算法可以直接转换成为C++、C#、Java等高级程序语言，这就为程序和算法的初学者铺就了一条平缓、自然的学习阶梯。使用RAPTOR的理由可以在最大限度地减少语法要求的情形下，帮助用户编写正确的程序指令程序就是流程图，可以逐个执行图形符号，以便帮助用户跟踪指令流执行过程容易掌握用RAPTOR可以进行算法设计和验证，从而使初学者有可能理解和真正掌握“计算思维”Raptor的特点（1）Raptor语言简洁灵活。（2）Raptor具有基本的数据结构、数据类型和运算功能。（3）Raptor具有结构化控制语句。（4）Raptor语法限制较宽松。（5）Raptor可以实现计算过程的图形表达及图形输出。（6）Raptor对常量、变量及函数名中所涉及的英文字母不区分大小写，但只支持英文字符。（7）Raptor设计的程序可移植性较好。Raptor的使用——工作环境简介F5：运行流程图F10：单步执行显示执行结果。Raptor的使用——六种基本符号5518:16Raptor的使用——流程图编程Raptor程序是一个有向图(DirectedGraph)必须要有「Start」和「End」。程序会由「Start」开始,运行至「End」才完成。在「Start」和「End」之间插入其他部件，便可制作一个较有意义的程序。输入

把数据及指令

输入计算机处理

计算机对输入的

数据进行运算输出

计算机显示处理

数据的结果用一用Raptor！画一个左图所示的流程图：从工具窗口选择赋值控件，在主窗口的流程图中单击，添加控件；双击赋值控件，在弹出的“Enterstatement”窗口中的set处输入变量名wh，在to处输入值“Hello,world!”,按回车;用同样的方法画一个输出控件；流程图画好后保存文件命名为myfirst.rap；然后单击(按F5)运行流程图。观察运行过程及结果。Raptor编程基础——什么是变量？在主存储器的一个存贮位置。内存存储单元一个符号名。通过引用符号名来访问其所对应的存储单元。存储单元大小视定义类型而定。程序运行时，变量的值是可改变的。主存储器名称:x类型:数字名称:myname类型:文字59

Raptor编程基础——变量变量的值的来源通常来自用户输入计算机加载(赋值存入内存单元)一般来说，变量在程序运行前,其数值是未定的。第一个被赋予的值为初始值(initializingavariable)。如使用未定初始值的变量，或会引发运行时错误。在程序运行的过程中，变量的数值会有所变化。能够处理不同的输入，才是一个较具意义的程序。何谓赋值？

Raptor编程基础——变量使用变量时须注意的地方命名限制：起首字符必须为英文字母。其后的字符可以是英文字母、数字或下划线，但不可以是其他符号或空格键。对：Hello,send2you,it_a_nice_day错：2myfriend,iamveryangry!名字不可与一些内定的预留字(Reservedword)相同。编程的良好习惯有意义的命名(e.g.exam_mark)

Raptor编程基础——数据类型Raptor的数据类型数值型(Number)：如456、-9、3.14159、0.000156字符串型（String）：如“Iamaboy”、“Helloworld”字符型(Character)：如‘B’、‘#’使用变量时常见的错误1.变量无值，也就是没有给变量赋值就直接使用。2.变量名拼写错误。18:16这个程序x的最终值是什么？在x←x＊2下方加上x←x/3,x的最终值是什么？动手做！演示Raptor-控制结构ControlStructure64控制结构ControlStructure顺序结构“and-then”按指令排列先后顺序执行。从前向后执行，必须按先后顺序执行。顺序结构左图是一个计算由华氏温度转化为摄氏温度的温度转换程序。思考：把题1的程序改为一个计算由摄氏温度转化为华氏温度的程序。F=

(提示：你需要哪些变量？已知哪些变量？求哪些变量？)字符串：用双引号括起来字符：用单引号括起来左图是一个计算圆面积程序的一小部分，试参考它的算法，把它改写成一个计算圆形周长的程序。(提示：你需要哪些变量？已知哪些变量？求哪些变量？)动手做！分支结构“if-then”按条件判断，分流执行由条件句判别True或False条件条件不符合(False)条件符合(True)分支结构——例子条件条件不符合(False)条件符合(True)成绩评定69分支结构算式結果密码正确