HNUSTC语言基础,简单数据结构,acm入门,第一讲,搜索

ACM 数据结构 ,搜索专题1

C语言基础，简单数据结构， ACM入门讲座 搜索部分Bjut:mark063 2010.10.30

ACM 数据结构 ,搜索专题1

C语言是什么 for while if…else… switch , case 函数调用 变量，数组，结构体声明 &,*,->,||,&&,==,++,+= 输入输出scanf, printf,freopen(“in.txt”,”r”,stdin);2

ACM 数据结构 ,搜索专题1

ACM/ICPC ACM-ICPC以团队的形式代表各学校参赛， 每队由3名队员组成。每位队员必须是在校 学生，有一定的年龄限制，并且最多可以 参加2次全球总决赛和5次区域选拔赛。 比赛期间，每队使用1台电脑需要在5 个小时内使用C、C++或Java中的一种编写程 序解决7到10个问题。程序完成之后提交裁 判运行，运行的结果会判定为正确或错误 两种3

ACM 数据结构 ,搜索专题1

其他比赛 Topcoder,Codeforces平均每周一次，还定 期有其他形式的比赛，要求快速准确的构 造算法写代码能力 有道难题，百度之星，每年5,6月份 数学建模，校内赛4,5月，全国9月

ACM 数据结构 ,搜索专题1

参考书目 图书馆有关 acm的书 网上OJ

ACM 数据结构 ,搜索专题1

天津赛区

哈尔滨赛区

ACM 数据结构 ,搜索专题1

POJ 2027 No Brainer Time Limit: 1000MSMemory Limit: 30000K Total Submissions: 15196Accepted: 10314 Description Zombies love to eat brains. Yum. Input The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line "X Y", where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive. Output For each data set, there will be exactly one line of output. This line will be "MMM BRAINS" if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be "NO BRAINS". Sample Input 3453343 Sample Output NO BRAINS MMM BRAINS MMM BRAINS

ACM 数据结构 ,搜索专题1

Description Zombies love to eat brains. Yum. Input The first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line "X Y", where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive. Output For each data set, there will be exactly one line of output. This line will be "MMM BRAINS" if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. 8 Otherwise, the line will be "NO BRAINS".

ACM 数据结构 ,搜索专题1

ACM题型分类 1,基本算法 2,图算法 3,数据结构 4,搜索 5,动态规划 6,贪心 7,数学 8,计算几何 9,模拟9

ACM 数据结构 ,搜索专题1

搜索概论 搜索被称为“通用解题法”,在算法和人 工智能中占

据重要地位。 但由于它巨大的局限性和自身灵活性，也 被认为是最难学难用的算法之一。 本节目标：希望同学们对于任意一个问题， 1.很快建立状态空间 2.提出一个合理算法 3.简单估计时空性能10

ACM 数据结构 ,搜索专题1

搜索分类 盲目搜索：按预定的控制策略进行搜索， 在搜索过程中获得的中间信息不用来改进 控制策略。 启发式搜索：在搜索中加入了与问题有关 的启发性信息，用以指导搜索朝着最有希 望的方向发展，加速问题的求解过程并找 到最优解。

ACM 数据结构 ,搜索专题1

搜索算法 盲目搜索： 1. 广度优先搜索(Breadth First Search) 2. 深度优先搜索(Depth First Search) 3. 纯随机搜索、重复式搜索、迭代加深搜索、 迭代加宽搜索、柱型搜索 启发式搜索： 1. A*算法 2. IDA*算法

ACM 数据结构 ,搜索专题1

DFS&BFS 深搜例子：走迷宫，你没有办法用分身术 来站在每个走过的位置。不撞南山不回头。 广搜例子:你的眼镜掉在地上以后，你趴在 地板上找。你总是先摸最接近你的地方， 如果没有，再摸远一点的地方……

ACM 数据结构 ,搜索专题1

状态空间明确以下概念： 状态：问题在某一时刻进展状况的数学描述。 状态转移：问题从一种状态到另一种或几种状态 的操作。 状态空间：一个“图”,图结点对应于状态，点 之间的边对应于状态转移。

搜索：寻找一种可行的操作序列，从起始状态经 过一系列状态转移，达到目标状态。

ACM 数据结构 ,搜索专题1

搜索基础 搜索是常人最容易想到的解题办法，可以 说所有题都可以用搜索解决，但是没有剪 枝搜索可以看成是穷举法，时间上无法忍 受

ACM 数据结构 ,搜索专题1

8皇后问题 给定8*8棋盘，要在上边放子，要 求各棋子在同一行，同一列，同 一斜边上不能有两个或两个以上的子，找 到所有的放子方法，并输出放子过程与种 类数。