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

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

1

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

? ? ? ? ? ? ?

? ?

? ? ? ? ? ?

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

7

? ? ? ?

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，基本算法 2，图算法 3，数据结构 4，搜索 5，动态规划 6，贪心 7，数学 8，计算几何 9，模拟
9

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

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

11

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

12

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

13

? 状态转移：问题从一种状态到另一种或几种状态 的操作。 ? 状态空间：一个“图”，图结点对应于状态，点 之间的边对应于状态转移。

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

14

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

15

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

16

? 深搜：可运行代码在备注中

17

1 2 4 5 6 3 7

18

void DFS(int k) //处理第k步
{ if (k==n) //已经处理到第n步，到达目的状态

else //处理第k步 for (int i=1; i<=m; i++) //第k步中有m种可能 { 处理第k步 DFS(k+1)；//进入第k+1步

}
}
19

? 小明参加一个抢东西的电视节目。这个节目很 有意思，一共有n个东西可以拿(n<50)每个参加 活动的人不能拿重量超过m(m<2000)的东西， 而每个东西都有它的价值v，有的高有的低， 帮助小明安排要拿的东西，使总价值最高。

20

? ? ? ? ? 这是一个0-1背包问题。 对于每件物品，有两种选择： 1）拿这件物品（条件是最大重量不超过m） 2）不拿这件物品 下面程序给出0-1背包的dfs解法，效率无法忍 受，但是理解简单。 ? 下一次会介绍动态规划的0-1背包解法效率会 提升很大（备注中给出0-1背包动态规划解 法）。
21

22

POJ 1088 滑雪
? Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺 激。可是为了获得速度，滑的区域必须向下倾斜， 而且当你滑到坡底，你不得不再次走上坡或者等待 升降机来载你。Michael想知道载一个 区域中最长底 滑坡。区域由一个二维数组给出。数组的每个数字 代表点的高度。下面是一个例子 12345 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一， 当且仅当高度减小。在上面的例子中，一条可滑行 的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。 事实上，这是最长的一条。 23

POJ 1088 滑雪
? Input ? 输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整 数，代表高度h，0<=h<=10000。 ? Output ? 输出最长区域的长度。

24

? 这个搜的重复的过程 太多了，交到OJ上给 个TLE

25

? 记忆化搜索

26

BFS
? 广搜例子:你的眼镜掉在地上以后，你趴在 地板上找。你总是先摸最接近你的地方， 如果没有，再摸远一点的地方……

27

BFS程序基本结构

while(队列不空) {

}

28

POJ 2243 Knight Moves
? 国际象棋棋盘上有一个马，要从起点跳到 指定目标，最少跳几步？
a1 输入： a1 h8 输出： To get from a1 to h8 takes 6 knight moves.
1 2 3 4

a b c d e f g h

5
6 7 8

h8

29

1 2 3 4 5 6 7

a b c d e f g h

8

30

? 例如：从a1到e4

1 2

a b c d e f g h

0
3 2 3 2 3

3
1 2 3 3

2
1 3 2 3

3
2 3 2 3

2
3 2 3

3
3 3 3 3

To get from a1 to e4 takes 3 knight moves.

3 4 5 6 7 8
31

3 3

32

33

? 从起点、终点同时开始
a b c d e f g h 从起点找2步能跳 到的点
1 2 3

0 2 2 1

2 1 1 2

2 1 2 1 1 1 1 双向BFS,有效地 提高了时空效率。

4

2
2

2

0

5 6 7

8

34

POJ 1745 Divisibility
? 输入N、K,然后输入N个整数，N个整数可 列出若干加减运算式；若存在一个算式， 它的值能被K整除,输出“Divisible”，否则 输出“Not divisible”.

2
4 7 17 5 -21 15 4 5 17 5 -21 15

Divisible
Not divisible

35

?

{17，5，-21，15}
+ 5 + -

17

+ 5 -

+

-21
-

+

-21
-

+

-21
+

-21
-

15

15

15

15

15

15

15

15

17 + 5 + -21 + 15

17 - 5 + -21 - 15

36

? 最坏情况N=10000，二叉树有10000层，结点 总数210000-1。不可能枚举所有表达式 本题的目标：判断叶子结点上是否有值能被k 整除=>判断是否有值，除以k的余数为零。 计算中间值取余，不影响结果。 (a + b) % k = ( a % k + b % k) % k ? 因此只需记录对k的余数。2<=k<=100，每 层结点最多100个，不是指数级增加。
37

47 17 5 -21 15

0

1
+

2

3

4

5
-

6

0

1

2

3

4

5

(1+ -21)15) 7 = 1 6 (5 + % % 7 = 首先加入起点，17 % 7 = 3 (1 – -21) %% = = 4 (5 – 15) 7 7 1 扩展第2层结点 % 7 = 5 (5+ -21)
(3+5) % 7 -21) % 7 = 5 (5– = 1 (3 – 5 + 7) % 7 =5

0

1

2

3

4

5

6

0

1

2

3

4

5

6
38

?

39

? 蛇头在上、下、左、右四方向上的探索过 程 ? 注意： ? 蛇不能出界， ? 不能撞自己， ? 不能撞石头。

40

? 八数码游戏

Input: 2 3 4 1 5 x 7 6 8 Output: ullddrurdllurdruldr

41

2 1 7

8

3 4

1

6

5

2 2 8 1 7 6 8 2 7 14 8 2 7 22 8 2 7 3 1 6 4 5 8 2 7 6 1 1 6 3 4 5 23 3 4 5 1 6 3 4 5 15 2 7 6 8 1 3 4 5 7 6 3 4 5 7 2 7 8 1 6 3 4 5 1 7 16 1 2 8 6 8 2 8 6

3 2 1 7 8 6 9 3 4 5 17 3 4 5 2 1 7 3 8 6 5 4 2 1 7 3 8 6 4 5 3 4 5 10 2 1 7 18 2 1 7 4 6 8 3 5 8 4 6 3 5 19 2 1 7 8 4 6 11

4 3 2 1 5 12 2 1 7 8 4 6 20 2 1 7 8 4 3 5 6 1 2 8 6 7 3 4 5 3 5 2 1 8 6 7 3 4 5 7 8 6

5 3 4 5 13 2 1 7 21 2 1 7 8 6 5 4 3 8 6 5 3 4

42

? 分析：所给输入为初始状态，终态是1 2 3 4 5 6 7 8 x。 ? 将x当作9，开一个数组a[9！]，存每种状态 ? 采取双向BFS，前后搜同时进行。 ? 初始时每种状态标记为0. 在数组a里查找从前边搜到的状态，标记是0， 则置标记为1；标记是-1，则说明这是个前后 搜重合状态，同时说明input有解。 在数组a里查找从后边搜到的状态，标记是0， 则置为-1；标记是1，则也说明这是个前后搜 重合状态，同时说明input有解。
43

44