当前位置:首页 >> IT/计算机 >>

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

如果按照1-2-4-5-3-6-7的顺序,叫深度优先(DFS) 如果按照1-2-3-4-5-6-7的顺序,叫广度优先(BFS)
18

深度优先(DFS)模板:
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,有的高有的低, 帮助小明安排要拿的东西,使总价值最高。
输入 5 12 3 5 4 6 5 3 8 9 10 8 0 0

样例输出: 15

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

跳马规则
在2×3的矩形里:
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

双向BFS
? 从起点、终点同时开始
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

从终点找1步能跳 到的点

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
每层最多7个结点 (定义数组): 扩展第4层结点 (1+ 15) % 7 = 2 扩展第3层结点 7 = 0 (1 – 15) % 6

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

例3 Holedox Moving
?

一条长度为L“贪吃蛇”在n*m的迷宫中, 求它走到出口(1,1)的最少步数。 (2≤L ≤ 8;1<n,m ≤ 20)
输入: 564 41 42 32 31 3 23 33 34 000
39

输出: Case 1: 9

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

40

例4:Eight
? 八数码游戏

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


相关文章:
HNUSTC语言基础,简单数据结构,acm入门,第一讲,搜索_图文.ppt
HNUSTC语言基础,简单数据结构,acm入门,第一讲,搜索_IT/计算机_专业
C语言基础,简单数据结构,acm入门,第一讲,搜索.ppt
C语言基础,简单数据结构,acm入门,第一讲,搜索_理学_高等教育_教育专区。bjut的acm讲座 搜索入门C语言基础,简单数据结构, ACM入门讲座 搜索部分 Bjut:mark063 2010...
ACM算法与数据结构题目推荐(基础).xls
ACM算法与数据结构题目推荐(基础)_学科竞赛_高中教育_教育专区。acm基础题目 Online Judge POJ POJ POJ codeforces codeforces POJ POJ HDU POJ HDU HDU HDU POJ...
ACM入门1解析_图文.ppt
第一讲 ACM入门计算机科学与信息工程学院 ACM队 ...基本数据结构 ? 搜索、分治 ? 动态规划 ? 贪心…...遇到问题首先自己查找资料,之后再提问 76 三、C语言...
2014-2015湘潭大学ACM.ppt
需要有C语言或者C++或者Java的语言基础 ? 大约8-9次课,涉及到ACM/ICPC比赛基础的知识, ? ? ? ? 主要内容是搜索,动态规划,基础数据结构 每周一次课,每次课后...
ACM入门之新手入门.doc
ACM 入门之新手入门 1.ACM 国际大学生程序设计竞赛...语言,只要提高了自己 在算法设计上的造诣,纯 C 一...库中提供的对于基本数据结构的统一接口操作 和基本...
ACM新手入门指南.doc
搜索查询, 这里介绍的只是一个计算机学生想要在 ACM...一般通用语言C、C++、JAVA 都可以,这三种语言都...比较基础的,要重点掌握,可以自己买 一本数据结构,...
ACM入门_图文.ppt
第一讲 ACM入门计算机学院 陈星 2009.3 1 第一...支持语言:c/c++, java, pascal ? 题目表达:英语 ...基本数据结构 ? 搜索、分治 ? 动态规划 ? 贪心…...
ACM竞赛中所用到的数据结构_非常不错_和大家分享_图文.ppt
ACM竞赛中所用到的数据结构_非常不错_和大家分享_学科竞赛_高中教育_教育专区。ACM竞赛中所用到的 数据结构唐陈兴 2007.12.26 基本数据结构 ? ? ? ? ? ?...
ACM入门教程-数据结构(4)_图文.ppt
ACM入门教程-数据结构(4)_计算机软件及应用_IT/...对于“合并操作”,必须搜索全部元素 ! ? 树结构...HNUSTC语言基础,简单数据... 44页 免费 ACM之...
acm一些初学者必须要知道的问题_图文.ppt
acm一些初学者必须要知道的问题_IT/计算机_专业资料...%s扫描前导空白,并且只读一个字符 char c = str[...有了STL仍然要学习基本算法和数据结构,即使不实现也...
HNUST 20120216(搜索专题)-解题报告_图文.ppt
数据结构 约5% 约20% 约5% 2012-2-17 图论 约...有些 初学者在学习这些搜索基本算法是不太注意剪枝,...HNUST 20120214(递推专题... 18页 免费 ACM数论...
ACM_基础篇_图文.ppt
ACM_基础篇_高等教育_教育专区。基础算法 ? ? ? ? ? ? ? 基础算法类 模拟算法类 字符串处理类 基本数据结构搜索算法类 贪心算法类 时空权衡 基础算法类...
ACM入门之二-字符串处理_图文.ppt
第一讲 ACM入门 1 第三部分 字符串处理 2 搞ACM...C语言的输入输出比C++速度要快,当程 序中有大量...? 提供:基本数据结构的统一接口;基本算法的实现; ...
ACM最常用算法,算法讲解,ACM大赛无压力_图文.ppt
竞赛中基本数据结构与算法 5、ZOJ入门 2 ACM/...对于每对问答(a,b,c),都可以 知道sum[b] xor ...动态维护一组数据中最小(大)的一个 ? 实现简单 ...
数据结构授课教案(理论).doc
数据结构是计算机及相关专业中一门重要的专业基础课程...列举 C/C++语言中的程序实例进行理解和对比。 面向...以实际程序为例来分析讲解,介绍一些 ACM 比赛的网站...
ACM竞赛常用算法与数据结构_图文.pdf
ACM竞赛 常用算法 &数据结构 1 1ACM/ICPC简介 2、竞赛中常见的16种题型 3、时空复杂度的分析 4、竞赛中基本数据结构与算法 5、ZOJ入门 2 ACM/ICPC简介 ...
ACM_C语言经典代码(附目录).doc
ACM_C语言经典代码(附目录)_计算机软件及应用_IT/计算机_专业资料。ACM常用代码,编程常用代码,包括有数学问题,字符串处理,计算几何,数论,图论,排序/查找,数据结构...
16%-算法与数据结构-Acm竞赛常用1_图文.ppt
竞赛中基本数据结构与算法 5、ZOJ入门 2 ACM/...这步操作可以用并查集完成,对于问答(a,b,c)如果...动态维护一组数据中最小(大)的一个 ? 实现简单 ...
ACM竞赛中所用到的数据结构_图文.ppt
ACM竞赛中所用到的 数据结构 基本数据结构 ? 基础...BST(二叉搜索树)不是一棵平衡的树,它的树结 构...自然语言理解系统中经常用到 Trie结构应用字典树 ...
更多相关标签: