资源描述
C语言基础，简单数据结构，ACM入门讲座搜索部分,Bjut：mark0632010.10.30,1,C语言是什么,forwhileifelseswitch,case函数调用变量，数组，结构体声明,2,ACM/ICPC,ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成。每位队员必须是在校学生，有一定的年龄限制，并且最多可以参加2次全球总决赛和5次区域选拔赛。比赛期间，每队使用1台电脑需要在5个小时内使用C、C+或Java中的一种编写程序解决7到10个问题。程序完成之后提交裁判运行，运行的结果会判定为正确或错误两种,3,其他比赛,Topcoder，Codeforces平均每周一次，还定期有其他形式的比赛，要求快速准确的构造算法写代码能力有道难题，百度之星，每年5，6月份数学建模，校内赛4，5月，全国9月,4,参考书目,图书馆有关acm的书网上OJ,5,天津赛区,哈尔滨赛区,6,POJ2027NoBrainerTimeLimit:1000MSMemoryLimit:30000KTotalSubmissions:15196Accepted:10314DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:AsingledatasetconsistsofalineXY,whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.ThislinewillbeMMMBRAINSifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbeNOBRAINS.SampleInput3453343SampleOutputNOBRAINSMMMBRAINSMMMBRAINS,7,DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:AsingledatasetconsistsofalineXY,whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.ThislinewillbeMMMBRAINSifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbeNOBRAINS.,8,ACM题型分类,1，基本算法2，图算法3，数据结构4，搜索5，动态规划6，贪心7，数学8，计算几何9，模拟,9,10,搜索概论,搜索被称为“通用解题法”，在算法和人工智能中占据重要地位。但由于它巨大的局限性和自身灵活性，也被认为是最难学难用的算法之一。本节目标：希望同学们对于任意一个问题，1.很快建立状态空间2.提出一个合理算法3.简单估计时空性能,11,搜索分类,盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向发展，加速问题的求解过程并找到最优解。,12,搜索算法,盲目搜索：1.广度优先搜索（BreadthFirstSearch）2.深度优先搜索（DepthFirstSearch）3.纯随机搜索、重复式搜索、迭代加深搜索、迭代加宽搜索、柱型搜索启发式搜索：1.A*算法2.IDA*算法,13,DFSi=m;i+)/第k步中有m种可能处理第k步DFS(k+1)；/进入第k+1步,深度优先(DFS)模板：,19,帮助小明,小明参加一个抢东西的电视节目。这个节目很有意思，一共有n个东西可以拿(n50)每个参加活动的人不能拿重量超过m(m2000)的东西，而每个东西都有它的价值v，有的高有的低，帮助小明安排要拿的东西，使总价值最高。,输入5123546538910800,样例输出：15,20,帮助小明,这是一个0-1背包问题。对于每件物品，有两种选择：1）拿这件物品（条件是最大重量不超过m）2）不拿这件物品下面程序给出0-1背包的dfs解法，效率无法忍受，但是理解简单。下一次会介绍动态规划的0-1背包解法效率会提升很大（备注中给出0-1背包动态规划解法）。,21,22,POJ1088滑雪,Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。事实上，这是最长的一条。,23,POJ1088滑雪,Input输入的第一行表示区域的行数R和列数C(1=R,C=100)。下面是R行，每行有C个整数，代表高度h，0=h判断是否有值，除以k的余数为零。计算中间值取余，不影响结果。(a+b)%k=(a%k+b%k)%k,因此只需记录对k的余数。2=k=100，每层结点最多100个，不是指数级增加。,38,47175-2115,每层最多7个结点(定义数组)：,首先加入起点，17%7=3,扩展第2层结点(3+5)%7=1(35+7)%7=5,+,-,扩展第3层结点(1+-21)%7=1(1-21)%7=1(5+-21)%7=5(5-21)%7=5,扩展第4层结点(1+15)%7=2(115)%7=0(5+15)%7=6(515)%7=4,39,例3HoledoxMoving,一条长度为L“贪吃蛇”在n*m的迷宫中，求它走到出口（1，1）的最少步数。(2L8;1n,m20),输入：564414232313233334000,输出：Case1:9,40,蛇头在上、下、左、右四方向上的探索过程注意：蛇不能出界，不能撞自己，不能撞石头。,41,例4：Eight,八数码游戏,42,八数码问题的广度优先搜索,43,分析：所给输入为初始状态，终态是12345678x。将x当作9，开一个数组a9！，存每种状态采取双向BFS，前后搜同时进行。初始时每种状态标记为0.在数组a里查找从前边搜到的状态，标记是0，则置标记为1；标记是-1，则说明这是个前后搜重合状态，同时说明input有解。在数组a里查找从后边搜到的状态，标记是0，则置为-1；标记是1，则也说明这是个前后搜重合状态，同时说明input有解。,谢谢观看,44,
展开阅读全文