• 七种武器——C++11 VS Java与C#

    Java和C#在某种程度上都“源自于”C++,但这些语言在发展过程中也相互借鉴。C++也在不断进化着,C++11的出现和广泛支持让我们需要重新认识一下这门“古老”语言的新面貌。另外,通过对比Java和C#,我们或许能够对这些语言有更深入的认识。 继续阅读 »

  • 杭州登山记

    杭州不止有西湖,还有围绕西湖的群山。杭州的山不高,山上还有人工修建的石头小路。沿路而上可以登顶,俯瞰西湖、龙井茶庄和山下的城市与村庄。

    可我却不是来旅游的:我来锻炼,山地徒步。

    在一个地方待得太久会闷,我已经在上海待得太久,因此闷的发慌,想要离开这座钢筋水泥的堡垒、透透气。有时候,你觉得自己透不过气来,你需要一次说走就走的旅行。

    继续阅读 »

  • 七种武器——C# VS Java

    C#和Java相似:它们都把程序编译成某种“字节码”,然后在某种“虚拟机”上执行该字节码。此外,它们的语法形式都深受C++影响。另外,它们还是相互竞争的关系。因此,把它们放在一起比较是有意义的。 继续阅读 »

  • 七种武器——由一个算法的实现看编程语言的横向对比

    学习一门语言的最佳方式是实践——但“Hello, World!”之类的实践太过简单,然而太复杂的实践(比如一个复杂的项目代码)又让人十分痛苦。本文提供了一个不那么简单、又不会让人过于痛苦的算法用于编程实践。同时,它还提供了若干种不同编程语言对这一算法的实现——通过比较它们,我们可以对这些语言有更好的理解。 继续阅读 »

  • 连连看与一种巧妙的广度优先搜索

    连连看是一种益智游戏,其核心算法是要在一个M * N的矩阵上找出两个点的“最短路径”,满足:1. 转弯数最少 2. 经过的点最少。谈到图的两点间最短路径,我们会想到用于无权图的广度优先搜索(BFS)和带权图的Dijkstra算法。那么对于连连看的M * N矩阵来说,究竟可以抽象成有权图呢还是无权图?如果有,权重又是什么呢? 继续阅读 »

  • Slash Maze

    这道题不简单!首先要把迷宫表示成可遍历的图,其次要找出图中所有的环及其长度。

    第一个问题就很棘手:只用斜线矩阵(构成的邻接矩阵)来表示图可以吗?这种方式看似简单可行——可以遍历出环——但是难以计算环的长度(如环内部的情况比较复杂时),而且难以枚举出所有环(环和环之间可能有共享边),必须考虑其他方式。

    继续阅读 »

  • Playing With Wheels

    每个数字代表一个状态,其任意一位左/右转动得出的数字代表一个新的状态:如果把这些状态看作一张图的顶点,在一个状态和它可以(一步)到达的状态之间连一条线,那么在初始状态和目标状态之间的最短路径长度就等于最少的转换步数,可以用广度优先搜索得到;对于禁止的状态,可以在遍历图之前就把它们标记为“已访问”状态,这样就不会搜素经过这些禁止状态的路径了。代码如下:

    继续阅读 »

  • Chopsticks

    如果考虑一般情况:把n个元素划分成p组(p = k + 8)、每组3个元素,分别计算每种划分的“难用度”然后找出最小值,这种穷举算法时间复杂度巨大、不可用。

    题目中说筷子数组l是按长度排好序的,这是一点很重要的提示:如果我们拿l[i]做A筷,则B筷一定是l[i + 1]才能保证(A - B) ^ 2最小,至于C筷,只要它的序号大于i + 1即可。

    这样,如果设f(i, j)为从l[i]到l[n - 1]里选出j组筷子(每组3支)的最小“难用度”,则f(0, p)即求解目标,并有以下递推式:

    继续阅读 »

  • Ferry Loading

    此题最简单、直观的办法是递归求解:

    继续阅读 »

  • Weights and Measures

    此题贪心可解:定义第i层的最大负载为p(i),则:

    继续阅读 »