算法笔记-暴搜

19 January 2014

这篇终于不是翻译了><

想想还是把最近在看的一些算法和题目记下来(好记性不如烂笔头嘛

最近在看的一本算法书叫”挑战程序设计竞赛”, 豆瓣链接

Ants

题目链接

题目翻译:

n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行. 当蚂蚁爬到竿子的端点时就会掉落. 由于竿子太细, 两只蚂蚁相遇时, 它们不能交错通过, 只能各自反响爬回去. 对于每只蚂蚁, 我们知道它距离竿子左端的距离xi, 但不知道它的当前朝向. 请计算所有蚂蚁落下竿子所需的最短时间和最长时间.

每只蚂蚁开始的朝向都有两种, n只蚂蚁就是2n种. 如果用暴搜的话时间开销很大.

考虑下蚂蚁相遇的时候, 如果不考虑两只蚂蚁的不同, 其实反向与否没有关系. 对两只蚂蚁消耗的时间来说, 反向和没有反向继续往前走是一样的. 这样就可以认为每只蚂蚁是独立活动的, 求出最短和最长时间就可以了.

POJ1852的参考C++代码如下(C++新手请多多指教><):

深度优先搜索(DFS)

部分和问题

题目:

给定整数a1, a2, …, an, 判断是否可以从中选出若干数, 使它们的和恰好为k.

考虑下面的例子:

n = 4

a = {1, 2, 4, 7}

k = 13

输出: Yes

然后考虑下面的图片:

部分和实例图片

从图片可以很清晰地看到, 对于数组中的每一个数字, 我们有两种选择即加或不加. 那么我们可以用递归, 从第一个数开始遍历, 如果加的次数达到了就返回sum == k, 判断结果是否是想要的结果.

参考C++代码如下:

广度优先搜索(BFS)

迷宫最短路径

题目:

给定一个大小为N*M的迷宫. 迷宫由通道和墙壁组成, 每一步可以由邻接的上下左右四格的通道移动. 请求出从起点和终点所需的最小步数. 请注意, 本题假定从起点一定可以移动到终点.

我们可以考虑下从起点开始考虑它四周的点, 起点邻接的点到它的最短距离是1, 然后和邻接的点邻接的(除去起点)到起点的最短距离就是2, 以此类推, 那么我们可以用一个二维数组表示坐标然后记录下该坐标到起点的最短距离, 这样当坐标是终点的时候就得到了终点到起点的最短距离.

先把记录距离的二维数组都初始化为INF, 那么如果到最后终点仍然是INF的话就表明无法从起点到终点.

参考C++代码如下:

标签:
  • Algorithm
comments powered by Disqus