专题4-算法思维（2021版）

计算思维导论大学计算机公共基础教学部4算法思维算法Raptor可视化程序设计（重难点）常用算法：统计、查找、排序（重难点）4.1算法计算机求解问题的步骤(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)

；(3)使用某种程序设计语言描述该算法(编程),并编译成目标程序和进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序1.什么是算法？算法是解决问题的方法与步骤例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何人均可仿照进行(共享智能)开始C是伪币B是伪币A是伪币A＝B？A＝C？是否否是ABC关于算法的三方面问题如何确定算法（算法设计）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？2.算法设计举例典型问题：如何对数据进行排序问题：任给一组(n个)整数，将它们从小到大进行排序“选择排序”算法的思路：①从所有整数中选一个最小数，作为已排序的第一个数②从剩下未排序整数中选最小的数，添加到已排序整数的后面③反复执行步骤②，直到所有整数都处理完毕“选择排序”算法举例2345789第6次循环后，排序结束2937845与首元素交换，第1次循环结束4937825数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置2397845与首元素交换，第2次循环结束2937845在未排序元素中确定最小数位置2347895与首元素交换，第3次循环结束2397845在未排序元素中确定最小数位置3.算法的表示流程图表示伪代码描述算法的流程图表示流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误端点符处理判断预定义功能原始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始用流程图表示选择排序算法算法控制结构——顺序结构一种简单的程序设计结构自始至终严格按照程序中语句的先后顺序逐条执行最基本最常用的结构形式根据条件表达式真假性执行不同的语句算法的控制结构——选择(分支)结构根据给定的条件，判断是否需要重复执行某一相同功能的程序段（循环体）。当型循环：先判断条件，条件成立执行循环体直到型循环：先执行循环体后判断条件算法的控制结构——循环结构将原始数据放在数组A中；设置i的初值为1，循环执行下列操作，直到i=n：{确定A[i]到A[n]中最小整数的位置，设为j；交换A[i]和[j]；i=i+1}使用伪代码描述“选择排序”算法使用伪代码描述算法伪代码(Pseudocode)是用来描述算法的一种语言，它既类似于自然语言，又使用与程序设计语言相似的方法描述算法优点：结构清晰，代码简单，可读性好，可以容易地以任何一种编程语言(Pascal,C,Java等)实现每个整数是A的一个元素：A[1],A[2],···,A[n]4.算法的分析算法分析的基本内容正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单时间复杂性(TimeComplexity)

：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示空间复杂性(SpaceComplexity)：除原始数据之外，额外占用的存储空间的大小S(n)＝O(f(n))，其中，n为问题的规模（1）时间复杂度指执行算法所需要的计算工作量算法的时间复杂度=T(n)，n为问题的规模。

常用量级相同的函数f(n)来表示，并记为T(n)=O(f(n))。常见的f(n)函数有1、log2n、n、nlog2n、n2、n3和2n等量级关系如下：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)O(1)表示常量时间，与问题规模n无关。时间复杂度选讲：

选择排序算法的时间复杂性假设参加排序的整数有n个（1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0

最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性为O(n2)设置i的初值为1，循环执行下列操作，直到I=n：{确定A[i]到A[n]中最小的整数元素的位置，设为j；交换A[i]和[j]；i=i+1}(2)算法的空间复杂度度量空间的复杂性，即执行算法的程序在计算机中运行时所占用的内存空间的大小。关于算法的小结计算机中处处是算法！例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档的表格中如何将表格内容排序？例3：如何把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如何在硬盘中找到用户指定的文件？例5：媒体播放器如何把MP3文件转换成动听的音乐？例6：搜索引擎如何在WWW网中找到用户需要的网页？计算机算法的4个特点目的：完成某个特定的信息处理任务必须满足的性质：①确定性：算法中每一步操作的含义必须清楚明确，无二义性②可行性：算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内③有穷性：算法在执行了有限步操作后必须结束④拥有足够的情报通用算法实际问题算法思想4.2Raptor可视化程序设计程序的基本编写方法Raptor基础控制结构常用函数和数组常用算法（统计\最值\闰年\素数）程序的基本编写方法IPOI（Input输入）-键盘接收用户输入的初始数据-也有其他输入方式，如文件输入等P（

Process处理）-包含各种运算与赋值操作，负责将初始数据加工成为运算结果-处理方法统称为算法，它是程序的灵魂O（Output输出）-显示计算结果Raptor基础Raptor环境基本符号常量和变量数据类型算术运算符输入操作输出操作赋值操作Raptor环境基于流程图的可视化程序设计环境工作区工具栏菜单栏编写区符号区主工作区即：程序编写区变量观察区RaptorRaptor程序是一组连接的符号，表示要执行的一系列动作符号间的连接箭头确定所有操作的执行顺序Raptor程序执行时，从开始（Start）符号起步，并按照箭头所指方向执行程序，Raptor程序执行到结束（End）符号时停止Raptor的基本符号常量和变量常量：在程序运行过程中，其值不能改变的量例如：14，“hello，world”，3.14，‘A’Raptor预定义了四个符号常量pi（圆周率）定义为3.1416e（自然对数的底）定义为2.7183true/yes(布尔值:真)定义为1false/no(布尔值：假)定义为0变量：在程序运行过程中，其值可以改变的量

例如：a,b,z,name标识符命名规则：以英文字母开头的英文字母、数字和下划线组成的字符串数据类型决定了数据所属的值的范围，以及能够对该类数据进行的操作和在内存中的存储方式Raptor数据类型：数值（Number）类型，数字型数据如：12，567，-4，3.1415，0.000371字符串（String）类型，多个字符组成的数据如：“Helloworld”，“JamesBond”字符（Character）类型，单个字符数据如：’A’，’8’，’!’算术运算符Raptor的输入操作把输入符号拖到程序编写区双击之后将弹出一个窗口第一个文本框填入输入提示注意：提示信息要加双引号第二个文本框填入将要被赋值的变量演示：Raptor的输入操作Raptor的输出操作把输出符号拖入编写区双击弹出窗口填入想要输出的内容可以是具体的值也可以是变量Raptor输出操作演示Raptor的赋值操作插入赋值符号双击该符号弹出窗口在“Set”输入框填入要赋值的变量在“to”输入框填入要赋值的值表达式演示：Raptor的赋值操作Raptor的控制结构顺序结构选择结构循环结构控制结构——顺序结构例题：从键盘输入两个数输出它们的和

控制结构——选择结构插入选择符号后，双击该符号，在弹出的窗口中输入框中输入决策表达式。决策表达式是一组值（常量或变量）和关系运算符的结合,

期望得到YES/NO这样的结果。表达式语句真（非0）假（0）表达式语句1语句2

非0

0关系运算符与布尔运算符运算符说明例=等于3=

4结果为

No(false)!=/=不等于3!=

4结果为Yes(true)3/=

4结果为

Yes(true)<小于3<

4结果为Yes(true)<=小于或等于3<=

4结果为Yes(true)>大于3>

4结果为No(false)>=大于或等于3>=4结果为No(false)and与(3<4)

and(10<

20)，结果为Yes(true)or或(3<4)

or(10

>20)，结果为Yes(true)not非not(3<

4)，结果为No(false)演示：Raptor的选择结构例题：从键盘输入两个数输出两个数中较大值练习：Raptor的选择结构从键盘输入一个数，输出其绝对值分析：1.键盘输入数据2.判断数的正负3.正数或0直接输出4.负数输出其相反数思考题：输出三个数的最大值分析：从键盘输入3个数比较2次输出最大值Raptor操作演示控制结构——循环结构指在程序中需要反复执行某个功能而设置的一种程序结构。三要素：循环变量初始值循环结束的条件循环变量的改变量在Raptor中一个椭圆和一个菱形符号被用来表示一个循环循环执行的次数，由菱形符号中的表达式来控制要重复执行的语句可以放在菱形符号上方或下方。演示：Raptor的循环结构编程实现：1+2+3+…+100输出结果练习：Raptor的循环结构编程实现5！分析：1.使用循环结构2.循环变量从1增加到53.结果变量初始化为14.循环一次进行一次乘法运算思考：如果要计算10！，如何修改程序？Raptor演示10！Raptor的常用函数与数组常用函数三角函数数组Raptor的常用函数函数形式功能举例abs(x)计算x的绝对值abs(-23)=23max(x,y)计算x,y的最大值max(23,43)=43min(x,y)计算x,y的最小值min(23,43)=23floor(x)计算不大于x的最大整数floor(15.9)=15ceiling(x)计算不小于x的最小整数ceiling(15.9)=16random计算[0.0,1.0)之间的随机数floor(random*6+1)log自然对数(以e为底)log(e)=1sqrt平方根sqrt(4)=2length_of对数组变量，返回数组元素的个数；对字符串变量，则返回字符个数str←”Sellnow”length_of(str)=8Raptor的三角函数演示：Raptor的常用函数输出max(2,-3)输出floor(13.7)输出floor(-13.7)输出ceiling(13.7)输出ceiling(-13.7)Raptor演示练习：随机函数生成[a，b](a>b)之间的随机整数分析：1.使用random生成[0.0,1.0)之间的随机数2.random*(b-a+1)+a生成[a，b]之间的随机数3.使用floor取整函数:floor(random*(b-a+1)+a)思考：如何获得[1，1000]之间的随机整数？floor(random*(1000-1+1)+1)Raptor演示练习：函数的应用随机生成两个[64,512]之间的整数，输出这两个数中较大的数。分析：1.使用两次floor(random*(512-64+1)+64)生成[64,512]之间的2个随机整数2.使用max()函数输出两个随机整数的较大值

Raptor演示Raptor的数组数组是有序数据的集合。数组中的每一个元素都属于同一个数据类型（数值、字符、字符串）。数组的优势：用一个统一的数组名和下标（index）来唯一地确定数组变量中的元素。下标可以参与计算，因而可以动态遍历数组元素数组名下标演示：Raptor的数组初始化初始化一个具有10个数组元素的全0数组，输出该数组。分析：初始化数组输出数组Raptor演示分析：输出语句使用了字符串连接运算练习：Raptor的数组初始化初始化一个具有10个数组元素的一维数组，使数组元素的值等于其下标值的平方，输出该数组。分析：如何修改刚才的程序？Raptor演示练习：Raptor的数组元素求和初始化一个具有10个数组元素的一维数组，使数组元素的值等于其下标值的平方，输出该数组和元素之和。分析：如何修改刚才的程序？Raptor演示存放元素之和变量初始为0求和常用算法统计最值问题闰年素数统计算法在给定的范围内求出符合设定条件的记录个数基本思想：用一个条件语句判断当前记录是否符合给定条件，符合则统计个数加一，用循环实现对所有记录的操作求解步骤：定义代表所有统计要求的计数器变量令所有计数器变量的初值为0构建循环体，当满足指定的计数要求时，就将相应的计数器的值加1（执行类似于n=n+1的操作）构建循环条件，根据问题的具体要求，选用相应的循环语句输出所有计数器的值统计实例：求三位正整数中能够被3和5整除的数字的个数分析：定义计数器count，初值为0构建循环体：若循环变量n能被3和5整除，则计数器加1循环条件：n从100到999如何判断整除：取余运算

modnmod3==0andnmod5==0Raptor演示练习：统计一个字符串中数字的个数分析：定义计数器count，初值为0构建循环体：若当前元素是数字，则计数器加1循环条件：n从1到length_of(str)如何判断字符是数字：str[i]>=’0’andstr[i]<=‘9’Raptor演示最值问题算法最大最小最多最少最长最短等问题称之为“最值问题”求解步骤：定义x代表N个数中的一个数。分别定义存放最大值和最小值的变量maxN和minN。令maxN=所有数据中的第1个数，minN=所有数据中的第1个数。构建循环体，然后将x与maxN比较，如果x比maxN大，令maxN=x；将x与minN比较，如果x比minN小，令minN=x。构建循环条件，根据问题的具体要求，选用相应的循环语句。输出maxN和minN的值。最值问题实例：求五个数中的最大值最小值分析：数组a存放5个随机整数（0-100）maxN=a[1]minN=a[1]构建循环体：若a[i]>maxN,则maxN=a[i]若a[i]<minN,则minN=a[i]循环条件：i从2到length_of(a)输出maxN和minNRaptor演示部分截图练习：输出一个字符串中码值最大的字符及其下标分析：变量a存放字符串maxi=1构建循环体：若a[i]>a[maxi],则maxi=i循环条件：i从2到length_of(a)输出a[maxi]和maxiRaptor演示闰年问题：判断一个年份是否是闰年分析：闰年判断标准：能被4整除且不能被100整除或者能被400整除Raptor演示练习：输出1900~2021之间所有的闰年年份分析：year从1900~2021循环,若year是闰年，则输出Raptor演示素数判断：判断一个大于2的自然数是否是素数分析：若n不能被2-根号n之间的整数整除，则是素数，否则不是素数设置一个flag为1循环变量从2到根号n，若n能被循环变量整除，则flag=0，结束循环根据flag的值确定自然数是否是素数。Raptor演示练习：输出3-100之间的所有素数分析：双重循环外层循环n从3-100内层循环从2到根号n，判断n是否是素数Raptor演示练习：输出3-100之间的所有素数，使用子图分析：判断素数保存为子图prime主程序中循环n从3-100调用primeRaptor演示4.3查找与排序查找排序交换类排序插入类排序选择类排序概述查找和排序是数据处理领域中的重要内容，算法的效率将直接影响到数据处理的效率。查找是在一个给定的数据结构中查找某个指定的元素。排序是将一个无序的元素序列处理成有序序列。不同的数据结构、不同的方法，算法效率不同。应根据应用问题场景选择合适的数据结构、算法。查找(1)顺序查找(2)二分法查找viewview(1)顺序查找顺序查找一般指在线性表中查找指定的元素。方法：从线性表的第1个元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等，则表示查找成功；若线性表中所有元素都与被查找元素进行了比较，但均不相等，则表示查找失败。示例:在线性表中查找元素60123458172886397元素无序只能采用顺序查找的方法由过程可见，每比较1次，查找范围仅减少1个60查找失败(1)顺序查找顺序查找演示分析：数据存放数组中设置一个flag，初始0，查到赋值1构建循环体：从第一个元素开始依次比较，直到找到或者比较完数组所有元素Raptor演示(2)二分法查找二分查找也称「折半查找」。是一种高效的查找算法。使用二分查找，须满足两个条件：①顺序存储；②元素有序。方法：将待查找元素x与有序线性表的中间项元素进行比较:（设有序线性表是递增的）若x=中间项元素，则表示找到;若x<中间项元素，则在线性表前半部分以二分法继续;若x>中间项元素，则在线性表后半部分以二分法继续示例:在线性表中查找元素60顺序表且元素有序123455361728490959767891①中间元素:8460<84→在[53,61,72]中找②中间元素:6160<61→在[53]中找③中间元素:5360>53→没找到由过程可见，每比较1次，查找范围缩小一半折半查找算法步骤数据存放数组a中，升序排列设置一个flag，初始0，查到赋值1top=1,bottom=length_of(a)循环比较：mid=floor((top+bottom)/2)如果key==a[mid],则flag=1，循环结束如果key>a[mid],则到下半部查找，top=mid+1如果key<a[mid],则到上半部查找，bottom=mid-1循环结束条件：flag=1（已找到）或top>bottom（已找完）折半查找Raptor实现key=60Raptor演示key=84Raptor演示交换类排序(1)冒泡排序法(2)快速排序法viewview(1)冒泡排序法①算法描述②示例③小结viewviewview①算法描述——冒泡排序法（设由小→大排序）算法思想:将相邻两个数比较，较大的数放到后面第1遍:对n个数进行第1遍扫描

比较第1个数与第2个数，若a1>a2，则交换；

比较第2个数与第3个数，若a2>a3，则交换；

依次类推…

比较第n-1个数和第n个数，若an-1>an

，则交换；经过(n-1)次比较后，最大的数被放在an第2遍:

对前n-1个数进行第2遍扫描:

经过(n-2)次比较后，第2大的数被放在an-1……第n-1遍:

对前2个数进行第n-1遍扫描:

经过1次比较后，第2小的数被放a2

至此，排序过程结束。总结:用冒泡法对n个数小→大排序,共需扫描(n-1)遍，第i遍扫描时需要比较(n-i)次②示例——使用冒泡排序法由小→大排序初始序列:4 2 3 1(n=4)第1遍:第2遍:第3遍:比较1:2

4

3 1比较2:2

3 4

1比较3:2 3 1

42 3 1 比较1:比较2:2 1

3

比较1:1

2用冒泡法对4个数排序，共需要扫描3次，第i遍扫描需要比较(4-i)次冒泡排序动图③小结——冒泡排序法使用冒泡排序法对n个数排序，最坏的情况下，需比较的次数：n(n-1)/2该算法的时间复杂度为:O(n2)(2)快速排序法①算法描述②示例③小结viewviewview①算法描述——快速排序法（设由小→大排序）算法思想:a)从线性表中选定一个元素t;b)然后，将线性表后面的元素与t比较，小于t的移至前面，而前面大于t的移至后面。经过一轮后，元素t的位置确定。c)对元素t之前的子表和元素t之后的子表进行同样的操作。直至，所有元素都有序。②示例——使用快速排序法由小→大排序初始序列:52,45,80,36,14,75,58,96,23,61(n=10)第1遍:选定元素52

×,45,80,36,14,75,58,96,23,6123,45,80,36,14,75,58,96,×,6123,45,×,36,14,75,58,96,80,6123,45,14,36,×,75,58,96,80,6123,45,14,36,52,75,58,96,80,61第3遍:…第2遍:子序列1选定元素23,子序列2选定元素75

23,45,14,36,52,75,58,96,80,6114,23,45,36,52,61,58,75,80,96×,45,14,36,14,45,×,36,14,×,45,36,×,58,96,80,6161,58,96,80,×61,58,×,80,96③小结——快速排序法快速排序本质上是对冒泡排序的一种改进。每次比较后将待排序序列分割成子序列。快速排序的时间主要耗费在子序列分割操作上。最坏的情况下，时间复杂度是O(n2)最好的情况下，时间复杂度是O(nlog2n)插入类排序(1)直接插入排序法(2)希尔排序法viewview(1)直接插入排序法①算法描述②示例③小结viewviewview①算法描述——直接插入排序法算法思想:a)将第1个元素视为已排好序；b)然后，将第2个元素插入到已排好序的序列中。依次类推，将第3个元素直至第n个元素插入到已排好序的序列中。②示例——使用直接插入排序法由小→大排序待排序序列:48,62,35,77,55,14,37,9848,62,35,77,55,14,37,98第1遍:48,62,35,77,55,14,37,98第2遍:35,48,62,77,55,14,37,98第3遍:35,48,62,77,55,14,37,98第4遍:35,48,55,62,77,14,37,98第5遍:14,35,48,55,62,77,37,98第6遍:14,35,37,48,55,62,77,98第7遍:14,35,37,48,55,62,77,98第8遍:插入排序动图③小结——直接插入排序法直接插入排序法，最坏的情况下需比较n(n-1)/2次，时间复杂度是O(n2)(2)希尔排序法①算法描述②示例③小结viewviewview①算法描述——希尔排序法算法思想:a)将待排序的序列分为若干组，在每组内进行直接插入排序。b)然后，再对整个序列进行直接插入排序。这一算法思想的关键在于分组。分组没有固定方式。通常做法是：将相隔某个增量r的元素分为一组；

然后，每次r减半，直到r为1②示例——使用希尔排序法由小→大排序待排序序列:51,45,80,36,14,75,58,96(n=8)第1遍:(r=4)51,45,80,36,14,75,58,9614,45,58,36,51,75,80,96第2遍:(r=2)14,45,58,36,51,75,80,9614,36,51,45,58,75,80,96第3遍:(r=1)14,36,51,45,58,75,80,96希尔排序动图③小结——希尔插入排序法希尔排序，属于插入类排序算法。对直接插入排序法进行了改进。最坏的情况下时间复杂度是O(n1.5)选择类排序(1)直接选择排序法(2)堆排序法viewview(1)直接选择排序法①算法描述②示例③小结viewviewview①算法描述——直接选择排序法（设由小→大排序）算法思想:选出n个数中最小的数与第1个数对换；选出次小的数与第2个数对换；依此类推，…；选出第2大的数与第(n-1)个数对换。②示例——使用直接选择排序法由小→大排序待排序序列:(n=8)52,45,80,36,14,75,58,96第1遍:14,45,80,36,52,75,58,96第2遍:14,36,80,45,52,75,58,96第3遍:14,36,45,80,52,75,58,96第4遍:14,36,45,52,80,75,58,96第5遍:14,36