Archive for the ‘Calvados’ Category
吃… 拉面 的 问题
我在万圣节的晚上饿着肚子来计算一个关于拉面的问题真是杯具啊
一乐拉面馆, 一共有4种口味的拉面, 老板每天会选1种供应, 鸣人每天只去吃1次拉面, 问平均多少天鸣人才能尝遍所有4种拉面呢?
一个数学化的描述: 假设第N天吃到了第4种拉面, 求E(N),
下忍级解法:
显然的最少需要4天
需要4天:
所有可能数 4^4
符合要求的可能数 4*3*2*1
P(N=4)= 4*3*2*1 / 4^4
需要5天:
所有可能数 4^5
符合要求的可能数: 4*(3^4 – 3 – 3*(2^4 -2))
P(N=5)= 4*(3^4 – 3 – 3*(2^4 -2)) / 4^5
首先从4个中选择一个做”第4种”, 剩下3种, 前面4天总的可能有 3^4 种, 去掉只吃了1种拉面的情况 3 种, 去掉只吃了2种拉面的情况: 从3种拉面中选择这2种, 4天中吃2种拉面的可能为2^4 -2 (总可能2^4 去掉只有1种拉面的2种)
…
需要n天:
所有可能数 4^n
符合要求的可能数: 4*(3^(n-1) – 3 – 3*(2^(n-1) -2))
P(N=n)= 4*(3^(n-1) – 3 – 3*(2^(n-1) -2)) / 4^n
最后整理得到的求和公式为
瞄一眼发现第无穷项貌似是0, 这个级数有可能收敛, 但是我饿了, 所以直接丢Mathematica里, 解得答案25/3
影级别的解法:
如果某一事件发生的概率为p, 那么平均1/p天发生一次
第一天吃第1种面, 其后
其后吃到第2种拉面概率为3/4, 那么平均4/3天吃到第2种拉面
其后吃到第3种拉面概率为2/4, 那么平均2天吃到第3种拉面
其后吃到第4种拉面概率为1/4, 那么平均4天吃到第4种拉面
1 + 4/3 + 2 + 4 = 25/3
德·梅齐里亚克的砝码问题
碎碎念 关于睡前看实分析有助于睡眠一事的确合理 尤其是窝在被窝里 但是 隔壁的老外如果叫得很基情的话 就… 很难想象3个男人在一起为什么会发出那种声音哦 于是我起床 于是我更新blog
关于这个梅氏砝码的问题, 貌似出自1624年出版的Problèmes plaisants et délectabled qui se font par les nombres一书, 作者是法国数学家G·B·德·梅齐里亚克(Gaspard Bachet de Méziriac，1581 – 1655)
问题描述如下
一个商人有一个40磅的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整磅数，而且可以用天平和这4块来称从1至40磅之间的任意整数磅的重物。
问这4块砝码片各重多少？
这个问题我所能理解的最为简单的解法如下: 对于每一个砝码, 都有3种状态, 即 放在天平左盘 放在天平右盘 不放在天平上, 那么这个问题就可以被理解为 找到一个三进制的计数系统, 那么每个砝码的重量必须是3的n次幂, n=0, 1, 2, 3 可知 砝码重量为1 3 9 27 和恰好是40且可以组成1~40所有的数
当然上述答案是比较难想的(精妙的解答往往在于此, 想出来很难, 理解起来却容易), 下面有一个比较容易想到的解法, 摘自100 Great Problems of Elementary Mathematics:Their History and Solution
天平的两个秤盘可区别为砝码盘和称量盘，在砝码盘上只放砝码，而在称量盘上放重物外还可附加砝码。若想设法用最少块数的砝码去称量，就要把砝码也放到称量盘上。
假如任意取出几块砝码放在盘上，例如，在一个盘上放 5 磅砝码和 10 磅砝码各一块，另一个盘上放 1 磅、3 磅、4 磅的各一块，那么这些砝码便使前一个秤盘偏重 7 磅。
我们只考虑重物和砝码均为整数，也就是说，重物和砝码的重量均为整数磅。
假如有一系列砝码 A ，B ，C，…，把它们适当地分放在两个盘上，就能称出从 1 到 n 的所有整数磅的重物。如果有一块新砝码P ，它的重量p 超过原有砝码的重量总和n，超过 量为原有砝码重量的总和加 1：
p – n = n + 1，
或者
p = 2n + 1，
那么，把砝码P 加入砝码组A 、B 、C、…之后就能称出从 1 至p + n = 3n + 1 的所有整数磅的重物。
事实上，原有砝码组足以称出所有从 1 至n 磅的重物，为了称出 1 个p + x 或p – x 磅的重物，这里x 表示从 1 到n 的任一个数，把砝码P 放在砝码盘上，再把砝码A ，B ，C，… 分别放在两个盘上，使砝码盘或称量盘上的重量偏重x 磅。
此法成立后，这个题目就容易解答了。
为了使两个砝码A 和B 能称出最多重量，A 必须是 1 磅，B 必须是3 磅，这两个砝码能称出 1，2，3，4 磅的重物。
如果选第三块砝码 C，使它的重量
c = 2 × 4 + 1 = 9 （磅）， 那么用A ，B ，C 三块砝码就能称出从 1 至c + 4 = 9 + 4 = 13 磅的所有重物。
最后，如果选第四块砝码D ，使它的重量
d = 2 × 13 + 1 = 27 （磅），
那么，这四块砝码A ，B ，C，D 便能称出从 1 至27 + 13 = 40 磅的所有重物。
结论：这个砝码的四块碎片的重量分别为 1，3，9，27 磅。
基情貌似结束了 我去睡觉了 困啊…
SAS & R
“喏, 这便是行业头号软件SAS了, 24万淫民币, 一个子都不能少”
“…”
关于对比 I
安装文件 SAS 3G R 30MB
核心代码 SAS JAVA R C
价格 SAS 24万 R Free
那我为什么要用SAS呢? 答曰: 看上去比较专业 吐槽曰: R看上去更加阴霸
关于对比 II
导入CSV文件 显示数据 显示二维图 进行线性回归计算
SAS代码
proc import datafile="d:\doc\data.csv" out=mydata dbms=csv replace;
getnames=no;
proc print data=mydata;
proc plot data=mydata;
plot VAR2 * VAR1;
proc reg data=mydata;
model VAR2 = VAR1;
run;
R代码
mydata = read.csv("d:\ \doc\ \data.csv", header=FALSE)
mydata
plot(mydata)
mylm = lm(V2~V1, data=mydata)
summary(mylm)
我恨分号我恨分号我恨分号, R更加UNIX, 大小写敏感, 在win下需要双斜线, 很莫名其妙的一点, 如果csv文件的结尾不是一个空行的话, R会有一个warning说最后一行不完全, 但不影响数据获取, SAS则没有这个问题
关于对比 III
折磨一下吧
数据量10 million, CSV文件体积244 MB(其实我开始生成的是100 million条, 2.38 GB的庞然大物, 结果发现我电脑吃不消), 这些数据大概是一个y=0.123456789x+987.654321的回归线, 每个值的误差在[-13,13]内
SAS的表现是7s读取完后瞬间算出y=0.12346x+987.65698
而R在吃掉800MB读了N分钟后读完数据然后计算, 内存占用瞬间飙升1.X G然后提示超过最大可用内存, 罢工了, 杯具啊
CUDA & Monte Carlo Method
当年在选笔记本的时候, 一定要买NV卡的原因就是NV有CUDA, 而我的陈旧的GeForce 7300并不支持这个功能
简单的说, CUDA是一个C/C++语言的编译器, 由她编译出来的程序可以利用GPU强大的浮点运算能力, 提高运行效率
目前比较常见民用级的应用主要集中于视频压缩
当然, 在金融计算这样的领域, 它的价值应该得到更好的体现, 一堆GPU连起来起来比N堆CPU连起来还要强N多的样子
在Windows 7平台下搭建CUDA开发运行环境还是非常简单的(相对于Linux), 首先在NV CONTROL PANEL -> SYSTEM INFORMATION -> COMPONENTS 下看看CUDA的Driver版本号是多少, 我的是显卡是Geforce GT 240M, 目前可以用的驱动带的CUDA Driver版本是2.2, 好像多数桌面显卡都有2.3驱动支持, 在确认有CUDA支持的驱动装好后, 依次安装对应版本的CUDA Toolkit 和 CUDA SDK (http://www.nvidia.com/object/cuda_get.html), 然后安装Visual Studio, 需要注意的是, 虽然Visual C++ Express可以支持CUDA, 但是由于其默认不支持64bit编译, 所以需要下载安装.Net Framework和替换, 所以还是推荐安装Visual Studio, 我安装的版本是2008 Pro, 安装的时候务必选择Full安装, 以保证64bit compiler装上, 安装完后安装CUDA VS Wizard (http://sourceforge.net/projects/cudavswizard/), 这样可以在New Project里面看到CUDAWinApp, 至于代码高亮, 发现目前只支持VS 2005, 反正我一般都是在Notepad++里写代码, 然后扔VS里调试编译.
简单安装流程:
1.安装最新显卡驱动并查看CUDA DRIVER驱动版本
2.下载对应的CUDA Toolkit 和 CUDA SDK
3.Full安装Visual Studio
4.安装CUDA VS Wizard
注: 安装好CUDA SDK后可以运行C:\ProgramData\NVIDIA Corporation\NVIDIA CUDA SDK\bin\win64\Release中的程序以测试是否安装了正确的驱动和Toolkit
搭建好CUDA的平台后自然要测试一下, 刚好拿最近在看得Monte Carlo Method试试, 几乎所有的Monte Carlo Method入门介绍都会提到用这种方法计算pi, 其C语言的核心代码非常简单
int i, pi=0;
double x, y, area;
for (i=1; i<=1000000; i++){
x= rand()/16384.0-1;
y= rand()/16384.0-1;
if ((x*x + y*y)<1) pi++;
}
area=4.0*(double) pi/(double) i;
printf("%f \n", area);
CUDA是支持标准的C语句的, 但是它有一些自己的.h文件, 比如cutil_math.h (对应math.h)
进行100万次循环, 纯C和CUDA运行时间分别为56ms和51ms
貌似没有明显差别, 下次打算拿更复杂一些的代码来测试一下, HOHO~
[Puzzle]Names in Boxes
地球上的某日:
我: 唉, 今天忘记带眼镜了, 看不到PPT
桶: 啊, 你眼镜多少度的呀
我: 250(事实)
桶: 不会这么低吧?
我: 我真的是250(干脆滴)
众: 扑哧~~~(笑…)
——————-正文滴分割线———————–
有一个监狱有100个囚犯, 他们的名字被写在一张纸上, 放在外形相同的盒子中, 这些盒子有1~100的编号, 它们被整齐在摆在一个房间里, 现在这些囚犯一个一个地进入这个房间, 进入房间后他们可以打开至多50个箱子, 如果其中有自己的名字, 则表示他”成功”了. 只有所有囚犯都”成功”了, 他们才可以被全部释放, 否则则会被人道毁灭.
1. 所有的囚犯依次进入房间且不可在打开箱子之后和其他囚犯进行任何交流
2. 对于盒子只有打开是允许的, 不能移动他们, 不能拿走里面写有名字的纸
问是否有一种策略, 使他们有30%以上的机会可以被释放呢?
直观上这的确是很难的, 按照最普通的方法, 每个人随机取50个箱子, 拿到自己的那个的概率是50/100=1/2, 他们能被释放的概率只有(1/2)^100, 无疑远小于30%, 但是利用如下的策略却可以达到30%的概率:
制作一个表, 把囚犯的名字随机编号1~100, 每个囚犯带着这张表, 他们中的某个人进入房间之后, 首先打开编号为自己名字对应的编号的那个箱子, 如果箱子里写的不是自己的名字, 则按照这个名字, 找到表上对应的编号, 然后再去打开此编号的箱子, 以此类推, 直到找到自己的名字或者已经打开了50个箱子为止.
解释
一般化: 取n=50
2n个名字可以组成的排列有(2n)!个, 假设这些囚犯需要打开k(k>n)次才能找到各自的名字, 这种情况下可以组成的排列如下:
从2n个名字中取k个, 有(2n)!/(k! * (2n-k)!)种可能, 这些排列中有一个(即囚犯自己的名字)位置是确定的, 剩下的(k-1)个名字可以自由排列有(k-1)!个, 剩下的(2n-k)个也可以自由排列, 又有(2n-k)!个, 把这个3个数相乘是(2n)!/k, 占所有可能性(2n)!的1/k
那么囚犯至多需要n次就可以找到各自名字的概率
1-1/(n+1)-1/(n+2)-……-1/(2n) = 1 -(ln 2n – ln n) = 1 – ln2 = 0.31
写给 从来没有Blog写给他们的那些人
标题出自 罗伊·索罗森 的 <悖论简史> 这本书从BNU分店的图书馆翻过之后就一直以电子书的形式躺在我的硬盘中, 今天把它翻出来看一下, 看到第一页”献给 从来没有书献给他们的那些人”发现这书果然不愧是写悖论的
先扯一下一些琐事简单讲就是我早晨被叫醒之后雕匆匆煎蛋我匆匆洗碗我们匆匆去学校发现自己提前2小时参加一个和我们没有任何关系的活动之后, 我们前往伦敦华人街中国淫行丢给他们15个胖子之后被把我的汇票换成10 20元不等的1万块现金, 各种原因解释N次开支票未遂等一系列悲剧相继发生, 然后我们买米买面买刀买厨具就是忘了买带在手上的套, 再感叹完接近100块淫民币的香菇很贵之后各自花了100+块吃了一顿丰盛到爆的广式茶点, 为钱包稍稍默哀之后去看眼 钟 桥以及某不知名宫殿期间遇到各种有趣的卖艺NPC若干后打道回府, 注册开地址证明如腹泻般顺畅但是回来发现我的account还是disabled说要等到明天因为今天刚刚更新莫名其妙的规矩?下面还大言不惭地写到这个过程是自动的不可跳过鄙视之 在MSN上和某北京友人吹水伦敦建筑之破和跑车之豪华, 顺便在 哔 ~ 下线之前聊上几句
回到正题: 那本书, 首先扉页上这段话貌似巨好
我们的理性常常陷入两个著名的迷宫: 一个是关于自由和必然的大问题, 特别是关于恶的产生和起源的问题; 另一个问题关于有连续性和看来是它的要素的不可分的点的争论, 而这问题牵涉到对于无限性的考虑. 前一个问题烦扰着几乎整个人类, 而后一个问题则只是得到哲学家们的注意. — 出自 莱布尼兹 <神正论> 序言 译者: 陈修斋
然后书里提到的悖论貌似我以前都看过, 它并不是讲技术细节的, 基本上是对历史的描述: xx年xx提出xx, 这本书作为通俗读物并没有牵扯到过多的数学符号形式的描述, 而是以文字表达为主, 穿插一些野史趣闻, 读来倒也不错
既然以悖论为题, 那么这里写一个比较不常见的悖论吧(相对于理发师悖论, 全能悖论, 罗素悖论那些而言), 悖论名为Braess’s paradox, 简单讲在某一些特定的大家都想尽快到达目的地的交通网上, 如果修一条近路, 反而会造成通行效率的下降, 以下例子翻译自Wikipedia(En)
考虑右图中的交通网, 有4000辆车打算在其中路上通行. 通过的时间从起点到A是路上车的数量除以100, 而从起点到B是固定的45分钟(另一条路相同). 如果近路不存在(即交通网上只有4条路), 从起点到A到终点需要的时间是
现在假设有了一条近路(通过时间接近于0), 在这种情况下所有的司机都会选择从起点到A到B这条线路, 因为就算所有的车都走这条路, 通过时间也不过40分钟, 小于起点到B的45分钟. 到达A之后, 所有的司机都会选择从用接近0的时间行驶到到B再到终点, 因为就算所有的车都走这条路, 通过时间也不过40分钟, 小于A到终点的45分钟. 这样所有车的通过时间是
From: 布雷斯悖论
有趣的是Google这个东东的时候貌似发现有人将这个悖论类比作:”如果你失恋了, 急需要找男女朋友, 不要以为同时找多个可以提高效率”
兔子 says:
给与你最初的那个阶段精神的慰籍
呵呵
刚到一个地方的开始超级闷
所以
宅,加油噢
我 says:
嗯 所以我拼命写blog
谢谢兔子, 我会拼命适应的, 作为礼物, 给你看一个优雅的证明吧, 别说这个看不懂, 我会崩溃Di…
叔看的不是豆瓣, 是寂寞
今天在SKYPE上看到爸爸妈妈了, 老爸要少喝点酒少抽烟, 听说他回来之后第一件事情就是开电脑看我是否在线, 心里酸酸的
今天在QQ上和表哥一起语音了, 希望他在那个我不怎么喜欢的省会里学业顺利, 家族里第一个博士哦
今天跟 哔~ 在MSN上一起聊天了, 出国之后第一次碰到, 很想她, 希望她在 哔~ 大活得黑皮一些, 还有, 我只是偶尔闷骚
今天依然没法不去超市, 用水冲泡过的肉吃起来果然腥味大大减轻, 我开始习惯于需要关心柴米油盐的生活
今天跟easy小盆友语音, 一方在感叹作业多的同时感叹无聊让我感觉大学生活其实面对的就是无聊的作业
今天看到了JJ, 依旧是小白脸万年受和我一样的修空调大叔装束, 哈哈
今天跟雕说:”叔看的不是豆瓣, 是寂寞” 他回:”锅看的不是土豆, 是红薯”
没开学的日子的确有些忧郁, 今天被邀请去BBQ我说自己感冒了要呆在宿舍, 其实是依然不习惯英国式的开放, 同flat的女生淡定地拿走半瓶伏特加让我有点小小的崇拜, 15胖子2箱子30瓶的百威让我心生邪念
贴一个看到的比较优雅的证明, 算是最近除了雕做的饭之外的赏心悦目的事情吧
明天第二次去China Town, 希望在BoC的Draft相关事情顺利, God Bless
我远方的朋友们, 尽管你们看不到这个BLOG, 我依然在这里写下对你们的祝福
Why Benford’s law works?
从solidot.org看到素数数列也有本福特定律 ，觉得这个定律蛮有意思的，于是造一篇POST
为什么本福特定律是有效的？
直觉
如果给你一堆生活中的数据，比如一个堆人的工资，那么这些数字是以1开头的概率大一些呢，还是2呢，还是?呢，直觉上，我们认为每个数字开头的概率是相等的。我们很容易联想到掷色子的例子，掷出的数字是1～6的概率是相等的。
矛盾
如果这样是对的话，那我们来看一个例子，我手里有一堆火星币：1块，2块，3块，4块，5块，6块，7块，8块，9块，现在我需要去月球。那么我按照1：2的比例换成月球币，比例是1：2，那么我换成了：2块，4块，6块，8块，10块，12块，14块，16块，18块；一个矛盾出现了，我手上的钱对于每个数字开头的频率并不一样，1开头的频数更高一些。
为什么
掷色子掷出5和口袋里有5块钱，这2个5是否有所不同呢？
其实是有的，我们可以把掷色子掷出5看作一个瞬间发生的事情，它没有一个积累的过程，更准确的说，它不可以被看作一个积累的过程。而口袋里有5块钱则不然，我可以把它看作是我由1毛钱逐渐积攒起来的，尽管这个积攒可能瞬间就完成了，但是它可以被看作是一个积累的过程。我们的工资，一个公司的资金等等很多生活中的可以用数字表示的数据，都是后一种：它们有一个积累的过程
回到直觉
这有什么不同呢？我们如果现在的工资是800，我们需要升到1000的话增加了200块，这是比较容易达到的，而需要升到2000的话，我们需要再增加1000，难度增大了，直觉上，1开头是比较容易达到的，越向后越难，直觉上1开头的概率应该比较大一些，事实的确如此：
1 30.1%
2 17.6%
3 12.5%
4 9.7%
5 7.9%
6 6.7%
7 5.8%
8 5.1%
9 4.6%
为什么2
我们可以通过足够大的样本来得到上面的分布情况，但是我们是否可以找到一个可以用数学的分布形式，即我们能否得出关于生活中由累计获得的数字的第一位的概率密度函数or概率累积函数？
尝试
我们找一个数字的第一位，首先用科学计数法表示这个数，即123=1*10^2+2*10^1+3*10^0，有用的只有第一项1*10^2，第一位就是1，第一项可以表示为x*10^n，x属于[1,10)，x我们已经知道不是均匀分布的，那么我们可否对x进行一下处理，即y=f(x)，y是均匀分布的呢？在解答这个问题之前，我们首先要知道的一点是，如果这种处理存在，那么对于任何的a*x，它也必定成立（为了避免上面的矛盾），即y=f(a*x)也是相同的均匀分布
怎么去想
假设y是均匀分布的，y+C也是密度函数相等的均匀分布，所以如果a*x能由乘法变成一个加法就好办了，即y=f(a*x)=f(x)+g(a)。乘法变加法，取对数，即y=f(x)=log(b)x，x属于[1,10)时，y的范围是[0,log(b)10)，y是均匀分布的，所以其密度函数的值是log(b)10-0=log(b)10
确定b的值
知道密度函数之后，我们在[0,log(b)10）上对log(b)10积分的值是1，可知b=10（虽然b=1/10也是一个解，但是它会导致负概率的出现）
怎么用？
如果我们想知道第一个数字2的概率，即是p(x=2)=p(2<=x<3)=p(lg2<=y<lg3)=从lg2到lg3上对1积分=lg3-lg2=lg(3/2)=0.176
更广泛的，数字n开头的概率=lg (n+1)/n
更更广泛的，对于b进制而言，数字n开头的概率=log(b) (n+1)/n
为什么3
我不得不承认，虽然沿着一条正确的思路，造了一个和现实拟合的非常好的公式，但是我的确对这个公式为什么有效没有了解，所以今后的某刻，当我能更深刻的理解它的时候，我可能会更新一下或者造一个新的POST
本文主要参考：
http://plus.maths.org/issue9/features/benford/
http://en.wikipedia.org/wiki/Benford’s_law
Ideas about sequences of sets’ limit superior and limit inferior
对于集合列的上极限和下极限的理解
咔咔，今天早起去上合同法，无事掉某老师的讲课翻看微观金融学
看到关于集合列的极限部分有些囧， GOOGLE一下发现还真有N多人困扰在这里
查看了英文的WIKI之后才有点顿悟的感觉， 不得不佩服英文在这方面的表达能力
一些直觉上的思考
1, 1, 2, 3, 5, 8, 13 …
这是一个数列
{0}, {1}, {0}, {1}, {0}, {1}, {0}, {1}, {0}, {1} …
这是一个集合列
一个数列的极限代表着这个数列中元素（就是数啦）的变化趋势
比如数列0.9, 0.99, 0.999, 0.9999 …的极限是1
那么， 一个集合列的极限类比过来，应该代表着这个集合列中的元素（就是集合啦）的变化趋势
数的变化可以用变大or变小来体现，就是加减运算
而集合的运算是并或者交，集合的变化就可以用增减元素来体现，在做两个or以上集合的并或交运算时，我们需要先找到其公共部分（共有元素）
在集合列的极限应该也和这个公共部分（共有元素）有关
数列的极限是数， 集合列的极限应该也是一个集合
集合列上下极限的定义
集合列的上极限包含这样元素，这些元素无限次的出现，或者说有无数个n，使a属于Xn（Xn是集合列），a构成的集合就是集合列的上极限（上限集）
比如上面的集合列{0}, {1}, {0}, {1}, {0}, {1}, {0}, {1}, {0}, {1} … 显然0和1出现的次数是无穷的，那么{0,1}就是这个集合列的上极限
集合列的下极限包含这样元素，这些元素无限次的出现，但是，我们总是可以找到n个集合不包含此元素（n是一个自然数， 注意0是自然数哦）
依然对于上面的数列，是不存在这样的元素的
考虑这样的一个集合列
{0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, {0, 1, 2, 3, 4} …
我们发现1这个元素出现了无限次，且只有第一个X1={0}不包含它，即我们找到1个集合不包含此元素，那么1是下极限中的一个元素
再考虑这样一个集合列
{0}, {0, 1}, {0}, {0, 1}, {0}, {0, 1} …
我们发现0这个元素出现了无限次，且没有集合不包含它，即我们找到0个集合不包含此元素，那么0也是下极限中的一个元素，这说明如果一个元素再集合列中每一个集合都出现了，那它也是下极限中的一个元素
我们可以发现，我们对于定义上极限中元素的条件“出现无限次”加了一个限制“可以找到n个集合不包含它”， 对于满足这一限制的元素才属于下极限，显然的，这样一切属于下极限的元素也必定属于上极限的
寻找上下极限的公式
我们如何找到出现无限次的元素呢？ 无限次出现代表着它有可能出现在X1，在X2，在X3 …
考虑集合列X1, X2, X3, X4 ….
如果一个元素属于X1 X2 X3 …这些集合并集，同时又属于X2 X3 X4 … 这些集合并集，同时又属于X3 X4 X5 … 这些集合并集，那么它在X1, X2, X3 …每一个集合中都可能存在，这个元素就出现了无限次
于是我们先求X1 X2 X3 … 的并集，X2 X3 X4 … 的并集，然后把它们求交，就得到了上极限的公式
沿着类似的思路，我们寻找那些出现了无限次却又有n个集合不包含它们的元素，它可能不存在于X1，可能不存在于X2，可能不存在于X3 …
如果一个元素属于X2 X3 X4 …这些集合的公共部分（交集），那么它在X2, X3, X4 …每一个集合中都可能存在，这个元素就出现了无限次，且不一定出现在X1中，如果不出现，那么我们找到集合X1不包含它，出现了也没关系，因为我们已经知道如果一个元素再集合列中每一个集合都出现了，那它也是下极限中的一个元素。
于是我们先求X1 X2 X3 … 的交集，X2 X3 X4 … 的交集，然后把它们求并，就得到了下极限的公式
优雅的对称，咔咔
如果一个集合列的上极限等于下极限，我们说这个集合列的极限存在（于函数的极限存在判定有有趣的对称）
KMP
吐槽0：看毛片算法？
吐槽1：WP又被强奸了
吐槽2：大S呀，你说你诱惑我研究这个干虾米，我写出来自己都不想看第二遍。
建议去 http://docs.google.com/Doc?id=dm48v73_572gz954wdf 看，有比较好的效果
贴在这里的颜色信息和排版乱了不少 
