大学计算机教程-计算与人工智能导论（第4版）课件 第3章 算法和数据结构

第3章算法和数据结构3.1算法的相关概念3.2穷举算法3.3查找算法3.4排序算法3.5递归算法3.6数据结构3.1算法的相关概念算法概念：算法&程序算法特点:确定性、有穷性、可行性、输入、输出算法性能:正确性、可读性、健壮性、时间复杂度、空间复杂度算法描述自然语言描述流程图描述伪代码描述程序设计语言描述起始或结束处理输入或输出判断连接点预定义过程不同的执行方向语句1语句2语句3三种基本结构的流程图描述条件语句1语句2YN条件语句1语句2NYa.顺序结构b.分支结构b.循环结构第1步：将数值1给变量t。第2步：将数值2给变量i。第3步：使变量t和变量i相乘，将结果存放到变量t中。第4步：将变量i的值加1。第5步：如果变量i的值不大于6，则重新执行第3步到第5步。如果变量i的值大于6，则算法结束。6!算法自然语言描述计算6!算法的流程图描述开始1=>ti>62=>it*i=>ti+1=>i结束Y输出tNBegin1=>t2=>iDo{t*i=>t;i+1=>i}untili>6;PrinttEnd

计算6!算法的伪代码描述#include"stdio.h"intmain(){ inti,t; t=1; i=2; do{

t=t*i;

i=i+1;

}while(i<=6); printf("t=%d",t);}计算6!的C语言程序3.2穷举算法算法思想步骤确定枚举对象及范围明确问题解答具体要求罗列所有可能的情况，逐一求解筛选答案，直到找到所有解常见的穷举算法：顺序、排列、组合例鸡兔同笼是在1500年前《孙子算经》中提出的数学问题：“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”。其大意是：有若干只鸡兔同在一个笼子里，从上面数，有35个头，从下面数，有94只脚。问笼中各有多少只鸡和多少只兔？开始1=>aa>3535-a=>ba*2+b*4=94输出a,ba+1=>a结束YYNN鸡兔同笼穷举算法流程图Step1:初始化鸡的数量1=>a。Step2:判断鸡的数量a是否大于35，若大于35转Step7。Step3:计算兔的数量35-a=>b。Step4:计算腿的数量a*2+b*4=9是否成立，若不成立，转Step6。Step5:输出鸡和兔的数量a和b。Step6:更新鸡的数量a+1=>a。转Step2。Step7:算法结束。例输入一个大于2的整数，判断其是否为质数。用穷举法求解算法用自然语言描述如下。Step1:输入数据到n。Step2:初始化数据2=>i。Step3:判断i是否等于n。若是，则转Step6。Step4:判断n除i的余数是否为0。若是，转Step6。Step5:更新数据i+1=>i，转Step3。Step6:判断i是否等于n。若是，输出“n是质数”，否则输出“n不是质数”。Step7:程序结束。开始i=n?N除i余数为0?输出”该数不是质数”i+1=>i结束YYNN输出”该数是质数”输入数到ni=n？YN质数判断穷举算法流程图3.3查找算法算法思想步骤顺序查找步骤从待查找序列中顺序选择一个元素，比较目标与当前元素如果相等，则查找成功，返回元素位置如果不相等，继续查找，直到找到目标或遍历完整个序列二分查找步骤：有序序列中查找①初始化：0=>low,len-1=>high②如果low>high，转⑤③mid=(low+high)/2④比较mid位置元素a[mid]与目标k。若k=a[mid]，返回mid，查找成功。若k>a[mid],mid+1=>low。

若k<a[mid],mid-1=>high。转②。⑤查找失败，返回失败标记-1。例在有序数组A=[9，11，18，21，25，31，45，55，68]中查找数字33的位置并输出。若找不到，输出“该元素找不到”。911182125314555689111821253145556891118212531455568leftmidrightleftrightmidleftrightmid91118212531455568leftright二分查找算法查找目标元素过程开始Low>high?33=A[mid]?找到，输出mid0=>low,8=>high结束YYNN输出”未找到目标”33>A[mid]?(low+high)/2=>midmid+1=>lowmid-1=>highNY3.4排序算法冒泡排序算法思想步骤初始化待排序序列为整个数组。按从前往后的顺序，将待排序序列中相邻两元素两两进行比较，若前面元素大于后面元素则交换相邻两元素的位置。缩小待排序范围，将当前待排序序列最后一个元素剔除。重复步骤②直到待排序序列只包含1个元素。例:用冒泡排序算法对数组A=[5,7,8,9,3,1]进行升序排序。A[0]A[1]A[2]A[3]A[4]A[5]578931578931578931578931578391578319(a)第1轮比较A[0]A[1]A[2]A[3]A[4]A[5]578319578319578319573819573189(b)第2轮比较A[0]A[1]A[2]A[3]A[4]A[5]573189573189537189531789(c)第3轮比较A[0]A[1]A[2]A[3]A[4]A[5]531789351789315789(d)第4轮比较A[0]A[1]A[2]A[3]A[4]A[5]315789135789(e)第5轮比较图3-17冒泡排序过程示意图Step1:初始化0=>i。Step2:判断i是否小于5。若否，则转Step9。Step3:初始化0=>j。Step4:判断j是否小于5-i。若否，则转Step8。Step5:判断A[j]是否大于A[j+1]。若否，则转Step7。Step6:交换A[j]和A[j+1]，即A[j]=>tmp,A[j+1]=>A[j],tmp=>A[j+1]。Step7:j+1=>i。转Step4。Step8:i+1=>i。转Step2。Step9:算法结束。选择排序算法思想步骤初始化当前交换位置为待排序序列第一个元素位置。在剩余待排序元素中，选择最小元素，与当前交换位置元素交换。排除已排序元素，重复步骤②，直到所有元素都被排序。例:用选择排序算法对数组A=[5,7,8,9,3,1]进行升序排序。578910311789103513891075min13591078第1次交换选择排序算法排序过程第2次交换第3次交换第4次交换iiminiminimin1357109813578910第5次交换第6次交换iiminminStep1:初始化待排序序列首元素位置0=>i和元素个数7=>n。Step2:判断i是否小于n-1。若否，转Step9。Step3:初始化待排序最小元素位置i=>min和当前位置i+1=>j。Step4:判断j是否小于n。若否，转Step7。Step5:判断A[min]是否大于A[j]。若是，则j=>min。Step6:j+1=>j，转Step4。Step7:交换A[min]和A[i]，即A[min]=>tmp，A[i]=>A[min]，tmp=>A[i]。Step8:i+1=>i，转Step2。Step9:算法结束。插入排序算法思想步骤初始化将待排序序列的第一个元素作为有序序列。选择待排序序列第一个元素，将其插入到有序序列中。缩小待排序序列范围，重复步骤②直到完成所有元素插入。例:用插入排序算法对数组A=[5,7,8,9,3,1]进行升序排序。578931A[0]A[1]A[2]A[3]A[4]A[5](a)第1次插入d=7(b)第2次插入A[0]A[1]A[2]A[3]A[4]A[5]578931d=8578931A[0]A[1]A[2]A[3]A[4]A[5]d=9(c)第3次插入插入排序过程示意图A[0]A[1]A[2]A[3]A[4]A[5]578931578991578891577891(d)第4次插入557891d=3357891A[0]A[1]A[2]A[3]A[4]A[5]357891357899357889357789(e)第5次插入355789d=1335789135789Step1:6=>n，0=>i。Step2:若i=n-1，转Step7。Step3:A[i+1]=>d,i=>j。Step4:若d>=A[j]或j<0，转Step6。Step5:A[j]=>A[j+1]，j-1=>j，转Step4。Step6:d=>A[j+1]，i+1=>i，转Step2。Step7:算法结束。3.5递归算法算法思想递推算法步骤确定递推的变量；建立递推关系式；确定递推的初始（边界）条件；明确递推终止的条件，控制递推过程，实现问题求解;递归算法步骤确定递归对象；建立递归关系式；明确递归终止条件，控制递归过程，实现问题求解;例：如果每对兔子（一雄一雌）每月能生一对小兔子（也是一雄一雌，下同），每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子。假设这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12个月以后会有多少对兔子？

用递推算法求解斐波那契数列问题的自然语言描述如下。Step1:设置初始条件1=>F1,1=>F2，3=>n。Step2:若n>12，转Step4。Step2:根据递推公式计算F=F1+F2。Step3:n+1=>n，F2=>F1，F=>F2，转Step2。Step4:输出F。Step5:算法结束。开始1=>F1,1=>F2,3=>nn>12?F1+F2=>F输出Fn+1=>n结束YN用递归算法求解斐波那契数列问题的自然语言描述如下。Step1:定义斐波那契数列问题求解过程F，参数为月份n。Step2:若n<3，返回1。Step3:返回当前n月兔子对数为F(n-1)+F(n-2)。F(n-1)和F(n-2)为过程F的递归调用。Step4:过程F结束Step5:调用过程F，月份参数n=12。Step6:输出过程F返回的值。Step7:算法结束。开始F(12)=>t输出t结束开始F(n)n<3?返回F(n-1)+F(n-2)返回1结束FYN(a)预定义过程F(n),n为月份(b)主模块(a)移动前(b)将n-1个盘子移动B后(c)将最下面盘子移动C后(d)将B上的n-1个盘子移动到CABCABCABCABC汉诺塔问题递归移动方法示意图例：汉诺塔问题源于印度一个古老传说。大梵天创造世界时做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？Step1:定义汉诺塔求解过程F，参数为盘子个数n，源位置标识S，辅助位置标识H，目标位置标识T。Step2:若n=1，输出一个盘子的移动路径S

T。转Step6。Step3:递归调用过程F(n-1,S,T,H)，将n-1个盘子移动从源位置S经过目标位置T移动到辅助位置H。Step4:输出最下面盘子移动路径S

T。Step5:递归调用过程F(n-1,H,S,T)，将n-1个盘子移动从辅助位置H