程序的设计实习课程-PPT课件.ppt

1、程序设计实习课程 (C+Programming Practice)学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY,DAY DAY UP 1程序设计实习第八讲 搜索主讲教师：田永鸿yhtianpku.eduai.pku.edu/cpp2019/tyh/tyh.htmidm.pku.edu/jiaoxue-CPP/cpp08.htm2019年3月19日北京大学程序设计实习课程2内容提要o搜索n广度优先搜索n深度优先搜索o影响搜索效率的因素oPOJ 1011 木棍问题o作业北京大学程序设计实习课程3搜索o搜索：高级枚举n有顺序有策略地枚举状态空间中的结点，寻找问题的解北京大

2、学程序设计实习课程4搜索oPOJ1077八数码问题：经典搜索问题n有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态1 2 34 5 67 8 0到达目标状态步数最少的解？1 2 34 5 67 88 2 31 4 65 7北京大学程序设计实习课程5搜索o状态空间82341657823415768234165 7824135768234157682341657北京大学程序设计实习课程6广度优先搜索o广度优先搜索n优先扩展浅层结点，逐渐深入第一层第二层第三层82341657823415768234165782413576823415768234165

3、7北京大学程序设计实习课程7广度优先搜索o广度优先搜索n用队列保存待扩展的结点，从队首队取出结点，扩展出的新结点放入队尾，直到找到目标结点（问题的解）8234165782341576824135768234157682341657北京大学程序设计实习课程8广度优先搜索o广度优先搜索的代码框架BFS()初始化队列初始化队列while(队列不为空且未找到目标结点队列不为空且未找到目标结点)取队首结点扩展，并将扩展出的结点放入队尾取队首结点扩展，并将扩展出的结点放入队尾北京大学程序设计实习课程9深度优先搜索o深度优先搜索n优先深入遍历靠前的结点8234165782341576823416507824

4、135768234157682341657北京大学程序设计实习课程10深度优先搜索o深度优先搜索n可以用栈实现，在栈中保存从起始结点到当前结点的路径上的所有结点n一般用递归实现北京大学程序设计实习课程11深度优先搜索o深度优先搜索的非递归框架DFS()初始化栈初始化栈while(栈不为空栈不为空 且且 未找到目标结点未找到目标结点)取栈顶结点扩展，扩展出的结点放回栈顶取栈顶结点扩展，扩展出的结点放回栈顶北京大学程序设计实习课程12深度优先搜索o深度优先搜索的递归框架DFS(type cur_node,int depth)for(cur_node的每个子结点的每个子结点child_node)DF

5、S(child_node,depth+1)o问题：在深度优先搜索中，若状态空间的图结构不要显式的存下来，该如何处理？北京大学程序设计实习课程13深度优先搜索o深度优先搜索的递归框架n在深度优先搜索中，状态空间的图结构并不一定需要显式的存下来。type node;void DFS(int depth)for(node的每一个可行变化的每一个可行变化)改变改变node;DFS(depth+1);恢复恢复node;此种做法需要一个全局数需要一个全局数组组array来存放每个走过来存放每个走过的的node，arraydepth就就是进入是进入DFS函数时需要扩函数时需要扩展的节点展的节点北京大学程序设

6、计实习课程14判重o判重n新扩展出的结点如果和以前扩展出的结点相同，则则个新节点就不必再考虑n如何判重？重复?8234165782341576823416507824135768234157682341657北京大学程序设计实习课程15判重o需要考虑的问题n状态数目巨大，如何存储？n怎样才能较快的找到重复结点？时间空间北京大学程序设计实习课程16判重o合理编码，减小存储代价n不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个结点对应于一个九进制数，则4个字节就能表示一个结点。（99=387,420,489）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0

7、表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8 个字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8)北京大学程序设计实习课程17判重o合理编码，减小存储代价n不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。北京大学程序设计实习课程18判重o合理编码，减小存储代价n不同的编码方式所需要的存储空间会

8、有较大差别82341657方案二：为结点编号把每个结点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个结点判重用的标志数组只需要362880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。北京大学程序设计实习课程19判重o时间与空间的权衡n对于状态数较小的问题，可以用最直接的方式编码以空间换时间n对于状态数太大的问题，需要利用好的编码方法以时间换空间n具体问题具体分析北京大学程序设计实习课程20广搜与深搜的比较o广搜一般用于状态

9、表示比较简单、求最优策略的问题n需要保存所有扩展出的状态，占用的空间大n每次扩展出结点时所走过的路径均是最短路o深搜几乎可以用于任何问题n只需要保存从起始状态到当前状态路径上的结点o根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择北京大学程序设计实习课程21影响搜索效率的因素o影响搜索效率的因素n搜索对象(枚举什么）n搜索顺序（先枚举什么，后枚举什么）n剪枝(及早判断出不符合要求的情况）北京大学程序设计实习课程22搜索o一种解决问题的方法，与枚举的思想类似。例如：求从北大到北京站的最短行车距离，假设只能走北京市五环以及五环以内的道路。n有很多种走法p从北大东门出来，有三条路：城府路、沿

10、白颐路向南、沿白颐路向北p沿白颐路向南走到北四环路口又有三种选择：继续往南、沿北四环向东、沿北四环向西。p北京大学程序设计实习课程23搜索o从北大到北京站的最短行车距离n假设的条件表明，只有有限种可能的走法n解决方法：p 列出每一种可能的路径：确定了搜索的空间p 对每一种可能的路径，分别计算行车距离p 从中找到最短的行车距离北京大学程序设计实习课程24北京大学程序设计实习课程25搜索的思想：遍历o根据所知道的知识知识，依次猜测各个可能的答案。o对每个可能的答案进行评估，确定所需要的答案o进行新新的猜测时：从两个方面利用已经完成的猜测的结果n将正在进行的猜测与已经完成的猜测进行比较，及早结束“无

11、用”的猜测。从北大出发，所走的车程已经超过已经发现的路径的长度n利用已经完成的猜测，快速生成新的猜测。已经找到一条从北大到北京站的路径，改变该路径上某个叉路口的选择可以得到新的路径。新路径与原路径的开始一段是相同的，包括从北大到该叉路口北京大学程序设计实习课程26程序设计练习1：城堡问题(POJ1164)o问题描述：图1是一个城堡的地形图。请你编写一个程序，计算n城堡一共有多少房间n最大的房间有多大o城堡被分割成mn(m50，n50)个方块，每个方块可以有04面墙北京大学程序设计实习课程27POJ1164o输入：程序从标准输入设备读入数据。n第一行是两个整数，分别是南北向、东西向的方块数。n在

12、接下来的输入行里，每个方块用一个数字(0p50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。n每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。n输入的数据保证城堡至少有两个房间o输出：城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。北京大学程序设计实习课程28POJ1164o样例输入4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 o样例输出59北京大学程序设计实习课程29解题

13、思想o对任意的方块(i,j)，在输入描述中用p表示np8p (i,j)没有南墙,(i+1,j)与(i,j)属于同一房间p 所有与(i+1,j)属于同一房间的方块也与(i,j)属于同一房间np%84p (i,j)没有东墙，(i,j+1)与(i,j)属于同一房间p 所有与(i,j+1)属于同一房间的方块也与(i,j)属于同一房间np%42p(i,j)没有北墙，(i-1,j)与(i,j)属于同一房间p 所有与(i-1,j)属于同一房间的方块也与(i,j)属于同一房间np%2=0p (i,j)没有西墙，(i,j-1)与(i,j)属于同一房间p 所有与(i,j-1)属于同一房间的方块也与(i,j)属于同

14、一房间北京大学程序设计实习课程30参考程序#include int r,c,p5050,rooms,max,modules;/r,c：南北向、东西向的方块数 /p5050：输入的每个方块的数字/rooms：城堡的房间数/max：最大房间的面积/modules：当前房间的面积bool visit5050;/标识房间是否被访问过void markRoom(int x,int y);/搜寻与(x,y)属于同一房间的方块北京大学程序设计实习课程31问题o如何设计void markRoom(int x,int y)函数？o算法的复杂度是多少？32int main()while(scanf(%d%d,&r

15、,&c)=2)rooms=max=0;int i,j;for(i=0;ir;i+)for(j=0;jc;j+)scanf(%d,&pij);visitij=false;for(i=0;ir;i+)for(j=0;jmax)max=modules;printf(%dn%dn,rooms,max);return 0;33void markRoom(int x,int y)if(visitxy)return;else visitxy=true;modules+;if(pxy8)markRoom(x+1,y);elsepxy=pxy%8;if(pxy4)markRoom(x,y+1);elsepxy=

16、pxy%4;if(pxy2)markRoom(x-1,y);elsepxy=pxy%2;if(pxy=0)markRoom(x,y-1);北京大学程序设计实习课程34程序设计练习2：木棒问题(POJ1011)o问题描述：乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过50个长度单位。然后他又想把这些木棒恢复到为裁截前的状态，但忘记了木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度都用大于零的整数表示o输入：由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度

17、。在最后一个案例之后，是零。o输出：为每个案例，分别输出木棒的可能最小长度。每个案例占一行。北京大学程序设计实习课程35解题思路o初始状态：有N节木棒o最终状态：这N节木棒恰好被拼接成若干根等长的木棒o从初始状态到最终状态最多有多少条不同的“路径”？nSum maxParts。其中Sum是全部N节木棒的长度之和，maxParts是最长一节木棒的长度o每条“路径”对应一个木棒的长度。从木棒长度最小的那条可能“路径”开始，如果成功地的找到了这条“路径”，就解决了问题北京大学程序设计实习课程36解题思路o构造一条木棒长度为L的“路径”：拼接木棒o在未被拼接的木棒中，找出一节最长的，开始拼接o从未拼接

18、的木棒中，选择一个长度合适的木棒，使得拼接后的木棒长度Ln找到了p 在前面的拼接过程中曾试图用过相同长度的一节其他木棒，但发现这样拼接不成功，继续寻找能够进行拼接的木棒p 把找到的那节木棒拼接上去。继续进行拼接n继续拼接成功，找到了“路径”n继续拼接不成功，把刚拼接的那节木棒拿下来，继续找下一个合适的未拼接木帮n没有找到：拼接失败37已拼接部分未拼接部分长度为L的木棒长度为L1的未拼接木棒，共有N1根长度为L2的未拼接木棒，共有N2根长度为L3的未拼接木棒，共有N3根o在已拼接部分未用长度为L1的木棒，则表明用长度为L1的木棒来拼接时是不成功的o下次拼接时也不能选择长度为L1的木棒，而应该选择

19、长度为L2或L3的木棒o如果长度为L2或L3的木棒也不能选择，则需要替换已拼接部分的最后一节木棒北京大学程序设计实习课程38程序实现bool Dfs(int nUnusedSticks,int nLeft);表示:当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft,那么在这种情况下能全部否拼成功。北京大学程序设计实习课程39程序实现Dfs的基本递推关系：bool Dfs(int nUnusedSticks,int nLeft).找一根长度不超过nLeft的木棒(假设长为len，拼在当前棍子上，然后return Dfs(nUnusedSticks

20、1,nLeft len);北京大学程序设计实习课程40程序实现Dfs的终止条件：boolDfs(int nUnusedSticks,int nLeft)if(nUnusedSticks=0&nLeft=0)return true;拼接尝试处理return false;北京大学程序设计实习课程41程序实现Dfs的剪枝处理：bool Dfs(int nUnusedSticks,int nLeft)for(int i=0;i S;i+)if(!anUsedi&anLengthi 0)if(anUsedi-1=false&anLengthi=anLengthi-1)continue;/剪枝剪枝3anU

21、sedi=1;if(Dfs(nUnusedSticks-1,nLeft-anLengthi)return true;else anUsedi=0;/说明不能用说明不能用i作为第条，那么要拆以前作为第条，那么要拆以前 /的棍子，的棍子，i还可能用在以前的棍子里，还可能用在以前的棍子里，/因此要因此要anUsedi=0;if(anLengthi=nLeft|nLeft=L)return false;/剪枝剪枝2、1.第一次剪枝处理第二次剪枝处理42#include#include#include int T,S;int L;int anLength65;int anUsed65;int i,j,k

22、;int Dfs(int nUnusedSticks,int nLeft);int MyCompare(const void*e1,const void*e2)int*p1,*p2;p1=(int*)e1;p2=(int*)e2;return*p2-*p1;43main()while(1)cin S;if(S=0)break;int nTotalLen=0;for(int i=0;i anLengthi;nTotalLen+=anLengthi;qsort(anLength,S,sizeof(int),MyCompare);44 for(L=anLength0;L=nTotalLen/2;L+

23、)if(nTotalLen%L)continue;memset(anUsed,0,sizeof(anUsed);if(Dfs(S,L)cout L nTotalLen/2)cout nTotalLen endl;/while45int Dfs(int nUnusedSticks,int nLeft)/nLeft表示当前正在拼的棍子和 L 比还缺的长度if(nUnusedSticks=0&nLeft=0)return true;if(nLeft=0)/一根刚刚拼完nLeft=L;/开始拼新的一根for(int i=0;i S;i+)if(!anUsedi&anLengthi 0)if(anUse

24、di-1=false&anLengthi=anLengthi-1)continue;/剪枝3anUsedi=1;46if(Dfs(nUnusedSticks-1,nLeft-anLengthi)return true;else anUsedi=0;/说明不能用i作为/第条，/那么要拆以前的/棍子，i还可能用/在以前的棍子里，/因此要anUsedi=0;if(anLengthi=nLeft|nLeft=L)return false;/剪枝2、1return false;北京大学程序设计实习课程47作业：平板上色问题(POJ1691)o问题描述：一个平板被一组大小不等的长方形覆盖，现在需要为每个长

25、方形上一种颜色。每个长方形需要上的颜色是预先确定的。每种画笔上一种颜色。但为了避免画笔将涂料滴到已经上好色的、且颜色不同的长方形上，在对一个长方形A上色前，要求：位于A正上方的其它长方形都已上好色。每取一次画笔，可以为多个长方形上色。o任务：请编写一个程序，计算为了完成一个平板的全部上色，最少需要取多少次画笔。北京大学程序设计实习课程48北京大学程序设计实习课程49o输入：第一行是整数M(1M15)，表示要测试的案例数。每个案例的第一行是整数N，表示有多少个长方形，接下来的N行分别描述一个长方形。每个长方形R用5个整数描述：左上角的X、Y坐标；右下角的X、Y坐标；R的颜色。n每种颜色的代码是一

26、个120的整数n平板的左上角坐标总是(0,0)n坐标的变化范围是099nN的变化范围是115o输出：每个测试案例占一行，输出需要取画笔的最少次数北京大学程序设计实习课程50o样例输入1 7 0 0 2 2 1 0 2 1 6 2 2 0 4 2 1 1 2 4 4 2 1 4 3 6 1 4 0 6 4 1 3 4 6 6 2 o样例输出3北京大学程序设计实习课程51关于校长基金申请o预计近期发布，感兴趣的同学请关注o数字媒体所两项：n在线直播体育视频的内容分析与增强技术研究及系统开发导师：田永鸿n数字动漫中动漫元素的获取技术研究导师：王亦洲o关于校长基金申请规定，请参见dean.pku.edu/bksky/bksky_main.htm