the Searching _25.ppt

theSearchingMethod AlfredYuan 2006 Info RUC 搜索的本质 一句话的解释 在所有的情况中寻找符合要求的情况类比的说法 搜索即一种特殊枚举辨别 搜索是有选择的 有一定效率的 枚举是无选择的 低效率的 题目引入 傻大木买军火 要求 1 傻大木共购买了三种武器 2万美元一个的木瓜手雷 6万美元一支的啊卡卡47型冲锋枪和1万美元一个的大杀器 2 三种武器的数量各不相同 3 傻大木购买的木瓜手雷的个数在大杀器个数和冲锋枪支数之间 4 木瓜手雷必须成对购买 5 为了图吉利 傻大木购买的大杀器个数的尾数是8 如8 48等 6 如果冲锋枪的支数是一位数 那么木瓜手雷的个数一定是两位数 但如果冲锋枪的支数不是一位数 那么木瓜手雷的个数可能是任何数 7 傻大木的n万元可能恰好花完了 也可能没花完 但一定花了九成以上 题目的简单思路 forsize bomb min possibletomax possibleforsize kaka min possibletomax possibleforsize bigkiller min possibletomax possibleIfAccept size bomb size kaka size bigkiller Output size bomb size kaka size bigkiller 总结基本思路 枚举所有可能的情况 再在所有可能的情况中寻找符合要求的情况同时我们可以发现 这道题目的变量数目是3 炸弹 咔咔 大杀器 是一个常量 也就是说 三层循环就可以枚举出所有可能的情况 那么对于变量数目为一个变量n的情况呢 不妨看下一道题目 深入 计算正行列式项 由键盘输入n 和一个n n的矩阵 输出所有计算行列式时要用到的正项之和 Forexample Input 21234Output 4 其中p1 p2 pn是1 2 n的排列 t是排列p1 p2 pn的逆序数 表示对1 2 n的所有排列 共n 个 求和 在n个数的1 2 n的一个全排列中 若两个数的前后次序和标准排列 1 2 n 为标准排列 不一致 则称这两个数构成一个逆序 一个排列中逆序的总的个数称为这个排列的逆序数 记为t 解题思路 生成所有排列 即确定n个变量 j1 j2 jn的值对于每一组j1 jn 计算对应逆序数用求得的逆序数结合输入的矩阵计算出该项的值t若t 0加到和sum中若t 0不做任何处理最后输出sum 总结大概的代码 forj1 1tondoforj2 1tondo forjn 1tondoif任意两个ji jk互不相等 t calc j1 j2 jn 计算逆序数 并返回 1 tt t a 1 j1 a 2 j2 a n jn if t 0 sum sum t cout sum 我们发现 要使用n层循环 也就是说 循环的个数是动态的如何解决这个问题 使用递归的方法 n层循环转化成n层递归具体方法 看如下的程序 boolused MAXN 用来实现j1 jn互不相同intj MAXN intt intsum voidSearch intk if k n t calc 对于储存在数组j中的n个变量计算逆序数inti for i 1 i0 sum t sum sum treturn for j k 1 j k n j k if used j k 判断j k 是否能取 used j k true Search k 1 used j k false 解决了这个问题我们就可以给出搜索问题的模版程序 intj MAXN MAXN是可能的参数个数voidSearch intk if k n k个参数的值已经确定了 验证是否符合条件 if Accpet 如果满足条件 做相应操作return 退出 forj k eachpossiblecase 对于第k个变量jk 枚举所有可能的值if available j k 如果jk可以取这个值 完成相应操作 譬如used j k true Search k 1 搜索下一个变量j k 1 完成相应操作 譬如used j k false 解决实际问题 案例1 寻宝 有一个n m的棋盘 如图所示 骑士X最开始站在方格 1 1 中 目的地是方格 n m 他的每次都只能移动到上 左 右相邻的任意一个方格 每个方格中都有一定数量的宝物k 可能为负 对于任意方格 骑士X能且只能经过最多1次 因此从 1 1 点出发后就不能再回到该点了 你的任务是 帮助骑士X从 1 1 点移动到 n m 点 且使得他获得的宝物数最多 按照一般的思路进行分析 枚举所有的情况 即枚举所有可能的路径Search的参数由两个变量构成 intx ySearch函数枚举在 x y 点处可能的走法 即 上 左 右边界条件为 x n y m 当达到边界是 如果这条路径上的值大于已经发现的最大值 则更新最大宝藏值 intd 3 2 1 0 0 1 0 1 存储3种行走方式对应的坐标变化值intdata MAXN 1 MAXM 1 储存 x y 中的宝藏价值intmax boolused MAXN 1 MAXM 1 用来辅助判断 x y 是否走到过voidSearch intx inty intsum 三个参数表示状态 if x n 搜索这个格子 案例2 滑雪 小袁非常喜欢滑雪 因为滑雪很刺激 为了获得速度 滑的区域必须向下倾斜 而且当你滑到坡底 你不得不再次走上坡或者等待升降机来载你 小袁想知道在某个区域中最长的一个滑坡 区域由一个二维数组给出 数组的每个数字代表点的高度 如下 一个人可以从某个点滑向上下左右相邻四个点之一 当且仅当高度减小 在上面的例子中 一条可滑行的滑坡为24 17 16 1 当然25 24 23 3 2 1更长 事实上 这是最长的一条 你的任务就是找到最长的一条滑坡 并且将滑坡的长度输出 滑坡的长度定义为经过点的个数 例如滑坡24 17 16 1的长度是4 继续按一般的思路分析 由于这个题目中间起点有多种可能 1 1 到 n m 都有可能 故要考虑从多个起点开始进行搜索对每个点枚举可能的情况 上下左右四个方向如果从某个起点 x0 y0 走到某个点 x y 时 发现经过的路径长度length max 则更新max最后输出max的值 boolavail intx1 inty1 inty1 inty2 avail函数判断是否 x1 y1 的高度大于 x2 y2 的高度intmax 记录最大值voidSearch intx inty intlength if length max max length 如果到达 x y 点时走过的路径已经大于max 更新max的值if avail x y x 1 y Search x 1 y length 1 if avail x y x 1 y Search x 1 y length 1 if avail x y x y 1 Search x y 1 length 1 if avail x y x y 1 Search x y 1 length 1 分别判断 x y 的四个方向是否可走 如果可走 搜索这个方向 intmain inti j max 1 for i 1 i n i for j 1 j n j Search i j 1 分别把每个点作为起点展开搜索cout max main函数的处理 最后 我们总结搜索题的一般特性 题目涉及的情况多规律不明显 无法推到出题目的规律或者找到一个绝对可行的数学公式一般要求是求出符合条件的解 求最大 最小值 求某种路径符合以上特征的题目是多的 大家相信已经有一些感受 搜索是一种相当重要的算法 解决搜索题目的一般方法 1 分析题目中的所有可能情况 即搜索的对象 如傻大木为所有军火组合 行列式那道题目为所有的1 n组合 藏宝是所有的 1 1 到 n m 的路径 滑雪是所有的递减型滑道 分析题目搜索的目标 即傻大木中符合条件的军火搭配 行列式中的正项 藏宝中的最大价值路径 滑雪中的最长滑道 解决搜索题目的一般方法 2 分析为了实现搜索目的 而要用的表示状态的方法具体而言 即对应的函数的头部 行列式 voidsearch intk 寻宝 voidsearch intx inty intsum 滑雪 voidsearch intx inty intlength 要保证参数变量准确 完备的表示出每个状态的情况 解决搜索题目的一般方法 3 确定每个状态中状态转移的方式即搜索中的主程序部分voidSearch intx inty intlength if length max max length if avail x y x 1 y Search x 1 y length 1 if avail x y x 1 y Search x 1 y length 1 if avail x y x y 1