信息学奥赛NOIP贪心深度优先搜索课件.ppt

《信息学奥赛NOIP贪心深度优先搜索课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、深度优先搜索1搜索搜索（search）算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。路漫漫其修远兮，吾将上下而求索。--战国（楚）屈原《离骚》借问酒家何处有？牧童遥指杏花村。--唐杜牧《清明》松下问童子，言师采药去。只在此山中，云深不知处。--唐贾岛《寻隐者不遇》众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。--宋辛弃疾《青玉案·元夕》古人的搜索黑夜给了我黑色的眼睛，我却用它寻找光明。顾城《一代人》撑着油纸伞，独自彷徨在悠长、悠长又寂寥的雨巷我希望逢着一个丁香一样地结着愁怨的姑娘...--戴望舒《雨巷》今人的搜索搜

2、索不是万能的，没有搜索是万万不能的。鸡兔同笼（NOI题库1752）【问题描述】一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。【输入格式】一行，一个正整数a(a<32768)。【输出格式】一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0，中间用一个空格分开。【样例输入】20【样例输出】510那些4位数(oj.jzxx.net)题目描述那些4位数，只由1,2,3,4这4个数字组成。请编写程序，输出这些4位数

3、，先小后大，每行一个。输入无输出11111112...4444那些N位数题目描述那些N位数只由1，2，3，....p这p个数字组成（p<=9）。请编写程序输出这些4位数。先小后大，每行一个。输入：二个整数N（1＜＝N＜＝8）和p(p＜＝9)输出：若干个N位数，每行一个．样例输入：43样例输出：11111112...3333走迷宫（maze.in/out/pas/cpp）【问题描述】一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。【

4、输入格式】第一行是两个整数，Ｒ和Ｃ（1<=R，C<=40)，代表迷宫的长和宽。走迷宫（maze.in/out/pas/cpp）接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。空地格子用'.'表示，有障碍物的格子用'#'表示。迷宫左上角和右下角都是'.'。【输出格式】输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。走迷宫（maze.in/out/pas/cpp）【输入样例】55..####....#.#.##.#.##.#..【输出样例】9走迷宫（maze.in/out/pas/cpp）状态分析：1.初始状态2.目标状态3.状态转移走

5、迷宫（maze.in/out/pas/cpp）实现：1.深搜2.宽搜程序结构voidSearch(intk){for（所有的选择i）if（满足条件）{保存结果;if（到目的地）输出解；elseSearch(k+1);恢复：保存结果之前的状态；//回溯一步}}程序结构voidSearch(intk){if(到目的地)输出解;elsefor(所有的选择i)if(满足条件){保存结果;Search(k+1,参数表);恢复：保存结果之前的状态；//回溯一步}}搜索是计算机程序设计中最基本、最常用的算法。搜索是基于计算机高速运算的特点而使用的求解方法。搜索可以用来求一个解、所有解、最

6、优解。搜索的思想就是从问题的初始状态出发，根据问题的约束条件，按照一定的控制策略，有序推进，不断深入，对于生成的所有目标状态，一一验证，从而获得符合条件的可行解，或根据评价函数选择出最优解。搜索算法的思想一个状态空间：状态的表示、状态集合、初始状态、目标状态举例：分油（10，7，3）：（10，0，0）（5，5，0）一个产生式系统：包括一个综合数据库（表示问题状态的数据结构）、一组产生式规则（if…else…语句）、一个控制系统（实现状态的有序转移，BFS/DFS等）搜索算法的核心输出N的全排列给定N（n<=10)，输出N的全排列。如N=3时，输出：1231322132313

7、12321组合给定m,n（1<=n<=m<=20)，输出从m个数中选n个数的情况。如m=4,n=2时，输出：121314232434THANKS