程序设计实习课程程序设计实习.ppt

程序设计实习第八讲 有哪些信誉好的足球投注网站 内容提要 有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站 深度优先有哪些信誉好的足球投注网站 影响有哪些信誉好的足球投注网站效率的因素 POJ 1011 木棍问题 作业 有哪些信誉好的足球投注网站 有哪些信誉好的足球投注网站：高级枚举 有顺序有策略地枚举状态空间中的结点，寻找问题的解 有哪些信誉好的足球投注网站 POJ1077八数码问题：经典有哪些信誉好的足球投注网站问题 有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态　　1 2 3　　4 5 6　　7 8 0到达目标状态步数最少的解？ 有哪些信誉好的足球投注网站 状态空间 广度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站 优先扩展浅层结点，逐渐深入 判重 判重 新扩展出的结点如果和以前扩展出的结点相同，则则个新节点就不必再考虑 如何判重？ 判重 需要考虑的问题 状态数目巨大，如何存储？ 怎样才能较快的找到重复结点？ 判重 合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别 判重 合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别 判重 合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别 判重 时间与空间的权衡 对于状态数较小的问题，可以用最直接的方式编码以空间换时间 对于状态数太大的问题，需要利用好的编码方法以时间换空间 具体问题具体分析 广搜与深搜的比较 广搜一般用于状态表示比较简单、求最优策略的问题 需要保存所有扩展出的状态，占用的空间大 每次扩展出结点时所走过的路径均是最短路 深搜几乎可以用于任何问题 只需要保存从起始状态到当前状态路径上的结点 根据题目要求凭借自己的经验和对两个有哪些信誉好的足球投注网站的熟练程度做出选择 有哪些信誉好的足球投注网站 一种解决问题的方法，与枚举的思想类似。例如：求从北大到北京站的最短行车距离，假设只能走北京市五环以及五环以内的道路。 有很多种走法 从北大东门出来，有三条路：城府路、沿白颐路向南、沿白颐路向北 沿白颐路向南走到北四环路口又有三种选择：继续往南、沿北四环向东、沿北四环向西。 …… 有哪些信誉好的足球投注网站 从北大到北京站的最短行车距离 假设的条件表明，只有有限种可能的走法 解决方法： 列出每一种可能的路径：确定了有哪些信誉好的足球投注网站的空间 对每一种可能的路径，分别计算行车距离 从中找到最短的行车距离 有哪些信誉好的足球投注网站的思想：遍历 根据所知道的知识，依次猜测各个可能的答案。 对每个可能的答案进行评估，确定所需要的答案 进行新的猜测时：从两个方面利用已经完成的猜测的结果 将正在进行的猜测与已经完成的猜测进行比较，及早结束“无用”的猜测。从北大出发，所走的车程已经超过已经发现的路径的长度 利用已经完成的猜测，快速生成新的猜测。已经找到一条从北大到北京站的路径，改变该路径上某个叉路口的选择可以得到新的路径。新路径与原路径的开始一段是相同的，包括从北大到该叉路口 程序设计练习1：城堡问题(POJ1164) 问题描述：图1是一个城堡的地形图。请你编写一个程序，计算 城堡一共有多少房间 最大的房间有多大 城堡被分割成m?n(m≤50，n≤50)个方块，每个方块可以有0~4面墙 POJ1164 输入：程序从标准输入设备读入数据。 第一行是两个整数，分别是南北向、东西向的方块数。 在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。 每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。 输入的数据保证城堡至少有两个房间 输出：城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。 POJ1164 样例输入 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 样例输出 5 9 解题思想 对任意的方块(i,j)，在输入描述中用p表示 p8 (i,j)没有南墙,(i+1,j)与(i,j)属于同一房间 所有与(i+1,j) 属于同一房间的方块也与(i,j)属于同一房间 p%84 (i,j)没有东墙， (i,j+1)与(i,j)属于同一房间 所有与(i,j+1)属于同一房间的方块也与(i,j)属于同一房间 p%42 (i,j) 没有北墙 ，(i-1,j)与(i,j)属于同一房间 所有与(i-1,j)属于同一房间的方块也与(i,j)属于同一房间 p%2=0 (i,j)没有西墙，(i,j-1)与(i,j)属于同一房间 所有与(i,j-1)属于同一房间的方块也与(i,j)属于同一房间 参考程序 #include stdio.h int r, c, p[50][50], rooms, max, modules; //r,c：南北向、东西向的方块数 //p[50][50]：输入的每个方块的数字 //rooms：城堡的房