《大学计算机-计算思维视角》 课件 第4章 算法与程序设计

算法概念及表示方法算法与程序设计章名：节名：算法的定义及特征算法实例算法的表示方法算法的评价1234是一种逐步解决问题或完成任务的方法。求解问题或完成任务的步骤方法输入数据输出数据算法算法的五个基本特征：(1)有穷性(2)确定性(3)可行性(4)有零个或多个输入(5)有一个或多个输出算法的定义及特征第一步

将第1个整数12当做当前的最大值Largest第二步Largest(12)和第2个整数(8)比较，发现Largest值不需要改变第三步

第3个整数(13)与Largest进行比较，将Largest的值由13代替第四步

当前Largest(13)比第4个整数(9)大，Largest值不变第五步

当前Largest(13)比第5个整数(11)大，Largest值不变第六步没有其他数需要处理，输出Largest值是13例：在以下数中（12813911）寻找最大值。算法实例算法实例（12813911）输入数据（13）输出数据自然语言描述方便、通俗，比较习惯和容易接受；易产生歧义，语句繁琐、冗长。流程图描述

形象、直观，易于理解；

占用篇幅大、画图费时、不易修改。N-S图描述对流程图的改进，节省空间。伪代码描述无固定、严格的语法规则，便于转换成计算机程序。计算机语言描述算法中步骤可通过已实现的基本运算执行有限次实现。算法的表示方法美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：起止框判断框处理框输入/输出框注释框流向线连接点用流程图表示算法N-S流程图（也叫盒图）表示算法的三种基本结构：用N-S图表示算法目的选择合适算法改进算法评价指标时间复杂度空间复杂度(1)时间复杂度时间复杂度是指计算机执行一个算法在时间上的消耗度量。(2)空间复杂度空间复杂度是指在—个算法的运行过程中，对临时耗费的存储空间的度量。算法的评价编写程序前，必须先设计算法算法是程序设计的灵魂算法当中的三类基本单元算法需要通过一些方法表示典型算法举例算法与程序设计章名：节名：穷举法递归123排序为了提高计算机的工作效率，人们通过长时间的研究开发，总结了一些典型算法，在应用中非常普遍。穷举水仙花数破译密码百元买百鸡递归汉诺塔求阶乘排序插入排序冒泡排序选择排序快速排序堆排序……典型算法举例穷举法（又称“枚举法”）基本思想是：按问题本身的性质，通过多重循环，一一列举各种可能的情况，并判断哪一种可能是符合要求的解（不能遗漏，也不能重复），并在逐一列举的过程中，检验每个可能的解是否是问题的真正解，若是，我们采用这个解，否则抛弃它。

穷举法例：鸡翁一，值钱五、鸡母一，值钱三、鸡雏三，值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几个?分析:设鸡翁、鸡母、鸡雏的数量分别为cocks、hens、chicks，则可得如下模型：5*cocks+3*hens+chicks/3.0=100cocks+hens+chicks=100穷举法举例-百元买百鸡百鸡问题算法描述:公鸡的数目从0遍历到20母鸡的数目从0遍历到33小鸡的数目从0遍历到100如果5*cocks+3*hens+chicks/3.0=100并且cocks+hens+chicks=100则输出公鸡的数目、母鸡的数目、小鸡的数目。穷举法举例-百元买百鸡用自身的结构来描述自身，称为递归。是利用问题本身所具有的某种递推关系求解问题的一种方法。思考：什么时候需要采用递归方法？问题分解递归递归举例——阶乘问题递归举例——阶乘问题递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，返回次序正好相反。排序含义：按数据队列的某个关键字，重新按一定规律排列其队列（升序/降序）。实现排序的方法：选择法冒泡法（气泡上浮法）插入法……排序在一组数中，自前而后对相邻的两个数依次进行比较和调整，让需要的数往后冒，不需要的数往下沉。关键：每当相邻的两数比较，发现它们的排序与要求相反时，就将它们互换。算法名字由来:越大的元素会经过交换慢慢“浮”到数列的顶端。排序举例-冒泡排序比较、判断--交换--不交换①第1个数与第2个数比较，冒出一个大数放到第2个位置；当前数与它后面的数比较，再冒出一个大数放到后面位置；②依次进行，从1～9，直到产生了第1个大数；③重复①②步，从1～8；④依次类推，直至找到第9个高分排在第2位。排序举例-冒泡排序穷举法利用计算机高速运算的优点，列举所有可能情况递归并不是简单的自己调用自己，而是在于问题分解算法还有很多，后续课程会学习到冒泡排序每次比较两个元素，调整顺序程序设计语言概述算法与程序设计章名：节名：程序设计语言的发展编程语言的执行方式程序设计语言的分类123程序设计语言，即编程语言，主要用于人类和计算机之间的交互。-编程语言种类很多，但生命力强的却不多-编程语言有600多种，大部分都不再被使用程序设计语言的发展通常情况下，分为低级语言和高级语言。编程语言和普通英语越相似，它就越高级。低级语言较难使用，但它们通常能编写出更小更快的程序。最低级的语言是“机器语言”，它是一系列由数字0和1组成的代码构成，用于直接与PC的微处理器中的内部命令进行交换。

高级语言编写的程序代码虽然容易被人们读懂，但想要计算机知道该如何去做，还是要将这些普通的英文单词转换成一串串0、1组成的代码，翻译或编写机器语言代码是极其复杂的工作，好在有“解释器”和“编译器”程序将高级语言编写的命令翻译成机器语言来执行。程序设计语言的发展机器语言汇编语言高级语言面向过程面向对象由0、1序列构成的指令码组成如：10000000加

10010000减用助记符号描述的指令系统如ADDA,B>>接近人类的自然语言，更严谨，更精确如：x=a+b程序设计语言的发展（1）

机器语言在计算机发展的早期，唯一的程序设计语言是机器语言。每台计算机有自己的机器语言，这种机器语言的指令是由“0”和“1”的字符串组成。计算机唯一能理解的语言是机器语言。例如：完成两个整数相加的机器语言代码00011111111011110010010000001111000111111110111100100100000111110001000001000000000100010100000100110010000000010010010000101101000111110100001000101111111111110000000000000000程序设计语言的发展（2）

汇编语言用与代码指令实际含义相近的英文缩写词、字母和数字等符号取代指令代码，例如，用ADD代表加法，用MOV代表数据传递汇编语言：是用助记符号编写程序的语言。汇编语言源程序：是用汇编语言编出的程序。汇编程序:是将汇编语言源程序翻译成机器语言程序的程序。例如：完成两个整数相加的机器语言代码LOADRFKeyboardSTORENumberlRFLOADRFKeyboardSTORENumber2RFLOADRONumberlLOADR1Number2ADDIR2R0R1StoreResultR2LOADRFResultSTOREMonitorRFHALT程序设计语言的发展（3）

高级语言

与人类自然语言相接近且能为计算机所接受的通用易学的计算机语言。编程语言的发展：Result=15+15ReturnLOADRFKeyboardSTORENumberlRFLOADRFKeyboardSTORENumber2RFLOADRONumberlLOADR1Number2ADDIR2R0R1StoreResultR2LOADRFResultSTOREMonitorRFHALT00011111111011110010010000001111000111111110111100100100000111110001000001000000000100010100000100110010000000010010010000101101000111110100001000101111111111110000000000000000程序设计语言的发展计算机执行源程序的两种方式：编译和解释。-源代码：采用某种编程语言编写的计算机程序，人类可读例如：result=2+3-目标代码：计算机可直接执行，人类不可读(专家除外)例如：1101001000111011编程语言的执行方式编程语言的执行方式编译将源代码一次性转换成目标代码的过程源代码编译器目标代码程序执行结果输出程序输入执行编译过程的程序叫做编译器编程语言的执行方式解释将源代码逐条转换程目标代码同时逐条运行的过程源代码编译器程序输入结果输出执行解释过程的程序叫做解释器静态语言和脚本语言根据执行方式不同，编程语言分为两类：静态语言：使用编译执行的编程语言C/C++语言、Java语言脚本语言：使用解释执行的编程语言Python语言、JavaScript语言、PHP语言程序设计语言的分类静态语言和脚本语言执行方式不同，优势各有不同静态语言：编译器一次性生成目标代码，优化更充分，程序运行速度更快脚本语言：执行程序时需要源代码，维护更灵活，源代码维护灵活、可跨多个操作系统平台程序设计语言的分类Apr2019Apr2018ProgrammingLanguageRatingsChange11Java15.035%-0.74%22C14.076%+0.49%33C++8.838%+1.62%44Python8.166%+2.36%56VisualBasic.NET5.795%+0.85%65C#3.515%-1.75%78JavaScript2.507%-0.99%89SQL2.272%-0.38%97PHP2.239%-1.98%1014Assemblylanguage1.710%+0.05%1118Objective-C1.505%+0.25%1217MATLAB1.285%-0.17%1310Ruby1.277%-0.74%1416Perl1.269%-0.26%1511Delphi/ObjectPascal1.264%-0.70%1612R1.181%-0.63%1713VisualBasic1.060%-0.74%1819Go1.009%-0.17%1915Swift0.978%-0.56%2068Groovy0.932%+0.82%程序设计语言的分类编程语言是用于人和计算机交流的语言编程语言比自然语言更简单、更严谨、更精确编译器/解释器读入源代码，把程序员意图转换成可执行程序，供他人使用程序员按照该语言的语法编写程序源代码，把自己的意图融入到代码中程序设计方法与过程算法与程序设计章名：节名：程序设计方法程序设计过程12程序设计包括面向过程(也叫结构化设计)和面向对象两种不同设计方法。面向过程顺序结构选择结构循环结构面向对象对象类封装继承消息多态性程序设计方法设计方法的产生结构化程序设计最早在20世纪60年代中期由荷兰科学家E.W.Dijikstra提出，程序应以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，这样使完成每一个模块的工作变得单纯而明确，为设计一些较大的软件打下了良好的基础。代表语言：C，Fortran，Pascal……结构化程序设计设计方法特点：1.采用自顶向下，逐步细化的模块化设计原则。2.

采用三种基本控制结构：顺序、选择、循环。a.顺序方式，确定各部分的执行顺序。

b.选择方式，确定某个部分的执行条件。

c.循环方式，确定某个部分进行重复的开始和结束的条件。结构化程序设计设计方法的产生面向对象的程序设计是20世纪80年代初就提出的，起源于SmallTalk语言。用面向对象的方法解决问题，不再将问题分解为过程，而是将问题分解为对象。代表语言：python，C#，java,……面向对象程序设计基本概念

①对象：运行时的基本实体②类：同类型对象的抽象③封装：对象的数据和代码私有，不被外界访问。对象名1一组属性一组操作对象名2一组属性一组操作消息面向对象程序设计设计方法特点：系统中一切皆为对象；对象是属性及其操作的封装体；对象可按其性质划分为类，对象成为类的实例；实例关系和继承关系是对象之间的静态关系；消息传递是对象之间动态联系的唯一形式；面向对象程序设计分析问题设计算法编写程序测试运行编写程序文档抽象设计编程检测结果程序设计过程一般包括以下五个步骤：程序设计过程面向过程是一种以过程为中心的编程思想分析出解决问题的步骤，然后用函数把这些步骤一个一个实现与面向过程的明显不同是封装、继承、类。面向对象是一种以事物为中心的编程思想程序的控制结构算法与程序设计章名：节名：顺序结构选择结构循环结构12351程序设计按流程分为三类控制结构：

顺序结构选择结构循环结构可以组成各种复杂程序!表示一个良好算法的基本单元。程序的控制结构按程序语句或模块在执行流中的顺序逐个执行。顺序结构例：已知一个摄氏温度，求对应的华氏温度。C语言程序如下:

#include"stdio.h"voidmain(){

floatc,f;printf("输入摄氏温度:");scanf("%f",&c);f=5.0*c/9.0+32;printf("华氏温度为:%g",f);}顺序结构也叫分支结构，按设定的条件实现程序执行流的两路或多路分支开始条件成立否？是否条件成立时执行的语句结束条件不成立时执行的语句分支结构的流程图选择结构例：打印学生成绩，若成绩≥60分打印“Pass”，否则打印“Fail”：#include<stdio.h>voidmain(){floatscore;scanf(″%f″,&score);

if(score<60.0) printf(″Fail\n″);else

printf(″Pass\n);}选择结构按给定条件重复执行指定的程序段。循环结构的流程图初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句。即：循环体结束是否循环结束循环结构例：求从1到100的累加和。#include<stdio.h>voidmain(){inti,sum=0;for(i=1;i<=100;i++) sum+=i;printf(″sum=%d\n″,sum);}循环结构由这些基本结构按一定规律可组成程序，可解决任何复杂的问题选择结构程序的关键是理清条件和操作之间的逻辑关系循环结构中最主要的是什么情况下执行循环顺序结构属于直线性思维方式程序基本构成要素算法与程序设计章名：节名：程序构成要素分析常量和变量运算符和表达式语句和函数1234自然语言程序设计语言词常量、变量词组运算符、表达式