简介：50% informatics, 50% mathematics, and 50% imagination

原站：http://www.matrix67.com/blog/

标签：matrix67 计算机 数学 编程 oi

指数：

“Matrix67: My Blog”的内容更新

累计：669 篇（自 2007-12-19 起）

更新：约3篇/周，最后更新15 天前

Matrix67: My Blog

经典证明：星际争霸是NP-hard的

今天看到这里给出了一个“星际争霸是 np-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 np-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 np-complete 问题... (15 天前)

http://inezha.com/w/1q8d55x9

Matrix67: My Blog

Fibonacci数列性质的组合证明

数列 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 今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。 f... (15 天前)

http://inezha.com/w/pcheixx5

Matrix67: My Blog

12个经典的行程问题

无论是小学奥数，还是公务员考试，还是公司的笔试面试题，似乎都少不了行程问题——题目门槛低，人人都能看懂；但思路奇巧，的确会难住不少人。平时看书上网与人聊天和最近与小学奥数打交道的过程中，我收集到很多简单有趣而又颇具启发性的行程问题，在这里整理成一篇文章，和大家一同分享。这些题目都已经非常经典了，绝大多数可能大家都见过；希望这里能有至少一个你没见过的题... (21 天前)

http://inezha.com/w/3kz21xxs

Matrix67: My Blog

漫话中文自动分词和语义识别（下）：句法结构和语义结构

这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它... (37 天前)

http://inezha.com/w/668t7xxc

Matrix67: My Blog

趣题：这些词有什么共同点？

据说，爱出题也是 geek 的一种特征。这几天在做语言工程课的期末大作业时，再一次见识了汉语里各种诡异的语法规则，然后突然想到了这样一种好玩的题型，于是竟然暂时放下手中的作业，花时间编了几个这样的题目来（感谢 geek 小美女 localhost_8080 的帮助）。 下面的每一组词中，前五个词都具有某种共同的性质，这种性质是后面五个词都不具有的。你能猜出每组词所对应的那个... (45 天前)

http://inezha.com/w/fmha6xxo

Matrix67: My Blog

趣题：用最少的点挡住所有可能的反射路径

有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为自己挡住激光（守卫实际上也是一个个点）。当然，天使可以在自己周围密... (60 天前)

http://inezha.com/w/a4zilxxr

Matrix67: My Blog

对角线方法之后的故事

同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 cantor 证明实数集不可数的方法并不容易理解。... (67 天前)

http://inezha.com/w/5y8puxxe

订阅者 ( 31 )

										更多

相关订阅源