xudong9419 xudong9419
关注数: 14 粉丝数: 15 发帖数: 591 关注贴吧数: 36
[转]Fibonacci数列性质的组合证明(非专业人士慎入...) 以下内容转自matrix67的blog: 数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质,其中一个性质是,每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说,如果把第 n 个 Fibonacci 数记做 Fn ,那么有: Fn+1 · Fn+1 - Fn · Fn+2 = (-1)n 今天看到了这个定理的一个组合数学证明,觉得非常有意思,在这里和大家分享。 Fibonacci 数有很多组合数学上的意义。比如说,用 1 × 1 和 1 × 2 的积木覆盖一个 1 × n 的棋盘,总的方案数恰好是 Fn+1 。下图显示的就是 n 较小时的一些实例: 这个规律背后的原因其实很简单:给出一个长度为 n 的棋盘后,它的覆盖方案可以分成两类,最后边放的是一个 1 × 1 的积木,或者最后边放的是一个 1 × 2 的积木。前一类情况下的方案数也就完全取决于前 n - 1 个格子的覆盖方案数,后一类情况下的方案数则等于前 n - 2 个格子的覆盖方案数。因此,如果用 f(n) 来表示 1 × n 棋盘的覆盖方案数,那么正好就有 f(n) = f(n - 1) + f(n - 2) 。另外,由于 f(1) = 1 , f(2) = 2 ,因而接下来的数 f(3), f(4), f(5), … 也就恰好构成了 Fibonacci 数列。 既然这样,那么用积木覆盖两个独立的 1 × n 棋盘,总方案数就是 Fn+1 · Fn+1 。我们有意把这两个独立的棋盘像左图那样摆放。类似地,用积木覆盖一个 1 × (n+1) 棋盘加上另一个 1 × (n-1) 棋盘的总方案数则为 Fn · Fn+2 ,我们把这两个棋盘放成右图所示的样子。左图的覆盖方案和右图的覆盖方案之间有一种非常巧妙的一一对应关系。 对于左图中的任意一种覆盖方案,我们找出上下两块棋盘中所有位置重合的“公共分割线”,选出最右边的那条公共分割线,然后交换此分割线右侧的部分。这样,左图棋盘的每个覆盖方案就能变成右图棋盘的一个覆盖方案。根据同样的方法,右图棋盘的每个覆盖方案也能变回左图棋盘的覆盖方案,这就说明了 Fn+1 · Fn+1 和 Fn · Fn+2 是相当的。等等,那为什么当 n 为偶数时, Fn+1 · Fn+1 比 Fn · Fn+2 要大 1 ,而 n 为奇数时, Fn+1 · Fn+1 会比 Fn · Fn+2 小 1 呢?神就神在这里。这是因为,刚才所说的一一对应关系并不是真的完全一一对应的。当 n 为偶数时,左图棋盘有一例极其特殊的覆盖方案无法对应到右图的棋盘——因为这种方案中根本没有公共分割线。当 n 为奇数时,左图的棋盘就不再有如此特殊的覆盖方案了,但右图棋盘中却又多出了一例没有公共分割线的情况。这就证明了 Fn+1 · Fn+1 - Fn · Fn+2 = (-1)n 。
[转]经典证明:星际争霸是NP-hard的(非专业人士慎入...) 以下内容转自matrix67的blog: 今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说,给定一个初始布局(包括地图、双方已有资源、双方已有建筑、双方已有兵力),判断其中一方是否能获胜,这个问题是 NP-hard 的。当然,考虑到即时战略游戏的复杂性,这个结论并不出人意料;真正有趣的,则是如何巧妙地利用游戏中的元素,构造出极其精巧的初始局面,从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞?你还能想到哪些别的证明方法?欢迎在下面留言一同分享。 假设初始时有 A 、 B 两位玩家,他们分别位于两个孤岛上。玩家 B 有非常多的地面兵力,但没有空中单位,并且已有资源为 0 ,而且还没有任何经济来源。他只能坐等玩家 A 来攻打他。玩家 A 一开始则完全没有兵力,但他有不少可以生产作战单位的建筑,也有一定的经济来源,理论上有获胜的希望。地图上还有第三个孤岛,孤岛周边放满 B 的对空防御,玩家 A 即使派遣空中部队也无法进入该孤岛。初始时,玩家 A 的资源刚好够造一个农民,玩家 A 还需要收集额外的 x 个单位的资源才足以消灭玩家 B 。但是,玩家 A 的所有可采集资源都在第三个孤岛上。这个孤岛上有 n 个采矿点,每个采矿点都配备有一个基地,以及 x/n 个单位的矿石资源。每个采矿点也都还预先配备了一个农民,只不过这个农民被矿石围在里面出不来了。采矿点与采矿点之间靠一些小路连接,每条路上都有玩家 B 的防御塔,保证一个农民走过去必死无疑,但是两个农民走过去恰好能活一个。游戏开始后,玩家 A 唯一获胜的途径便是,在某个采矿点建造一个农民,采完这个采矿点的矿,把被困的农民救出来,然后选择某条小路走到下一个采矿点(途中死掉一个农民),继续采矿并解救农民,以此类推,直到走遍每一个采矿点,采完所有的矿。很容易看到,玩家 A 相当于要解决一个 Hamilton 路的问题(注意,即使平面图的 Hamilton 路问题也是 NP-complete 的)。因此,星际争霸是 NP-hard 的。
1 下一页