博文
[转-百度d2core吧]MF中的概率问题(2006-07-22 19:53:00)
摘要：前言：
呵呵，不知道有没有人转贴过，没有的话，我就抢先了哦。
又是长戟三十万兄的作品，不知道大家看没看我上次转的《菜鸟暗黑手记》啊，好看吧，这家伙该去写小说的，呵呵，写技术贴也象在写小说，够罗嗦的。哈 :laugh:
主题：MF中的概率问题
版权所有：长戟三十万 原作 提交时间：16:50:36 12月10日
//**** 作为一个科幻/科普作品的忠实拥护者，我对中国此类创作的凋零局面深感痛心，但是也只有努力收拾起沮丧的心情，尽量尝试着写一些蹩脚的文字。本文将要介绍的概率知识极其简单，你不用学习专门的概率课程，仅凭直觉也应该知道。本文面对的对象是如狐狸的BOT(^O^)等既未曾受过四则运算知识教育，又常常坚持一些错误MF概率观点的朋友。（狐狸的BOT：我哪儿有啊...... 呜呜呜........作者：就看你好欺负啊.这样罢，下次欺负盐水菠萝 ^^）
第一个问题: 如果我需要60秒钟K一次 Pindeskin, 而Pindeskin掉下Winforce的几率为0.006%(十万分之六),我的MF值为400,那么我需要MF多长时间，才能保证我得到一把WF的机会不小于90% ?
掉下WindForce的几率为十万分之六，并不是说，如果你坚持KP十万次，你一定能得到六把WF，极端情况一样会出现。你有可能一把也没有(几率大概是0.25%的可能出现这种倒霉情况)，当然，你连续得到10万把WF的机会也还是存在的，只是这个机会如此之小，比我立即当上暴雪总裁的机会还要小的多的多。也许你看过一本科幻小说，《不变的逻辑》，文中有几只大猩猩，随机的在打字机键盘上敲打，结果打出来的是一本本世界文学名著，一本接一本，无错误无停顿（这个事件的可能性也是极小极小极的）结果看管它们的科学家大惊失色，为了维护概率理论，只好杀猴灭口，掏出手枪将这些大猩猩打死。然而，连续十万次KP，都掉出WF的概率是这样的小，以至于大猩猩打出文学名著和这件事比起来，发生的可能还要大的多！本文的读者们，如......
家里的旧电脑差点罢工(2006-07-15 11:40:00)
摘要：回到家这是第五天了，家里的一台电脑是赛扬466的，跑WIN98，因为不想太难为它，就算这样昨天她还是发了次脾气。
具体情况是这样的，那天下午想上会网，按了电源后，正在启动，启动画面都出现了，突然显示器上下晃得厉害，好像电视机没有信号的样子，然后显示器倒数秒，10秒钟后显示器shut down，于是我按了一下电脑的复位键，再次启动的时候，‘嘀~嘀~’，长长的响了两声，然后显示器没任何反应漆黑一片，然后我又按了一下复位键，响都不响，显示器照样漆黑一片，就CPU风扇在那呼呼的响。
没修电脑的经验，我的第一感觉是显示器坏了，因为系统在没有检查到标准输出设备时是不进行启动的，然后我就把显示器接显示卡的接头拔了，再试一次，显示器没有黑屏，而是显示了一条英文，大概意思简单来说就是‘No singal’，这和前面的现象不一样，于是我就觉得不是显示器坏了。
然后我就怀疑是显卡坏了，找来把螺丝刀，把显卡拆了，刷灰，擦金手指，忙了半天，再放回去，重启，还是不行，这样的试了好几次，忙得一头是汗，没有成果。我甚至要确定是显卡坏了。
后来一想，不对呀，要是没有标准输出设备，系统至少会有一声‘警告’的，现在是任何声音都没有，非常奇怪，于是我就想到，可能是内存条的问题，于是我就拆内存条，我有两个内存条，加起来192MB，我把显卡先弄好成原来的样子，再把其中一块拔出来，重启，还是一样，一声不吭，我又擦干净了放回去，咦，再开机它有‘嘀’的响声了，但是显示器画面停在了内存检查那步，还是卡死了，没有后文，不过有希望了，至少我知道是附加内存没有接好，系统检测的内存有错误，于是我拆下另外一条内存条，在我擦这个内存的时候试了下启动，系统可以正常进入，但内存只有64MB，这时才放下心来，至少其它的没有坏，如此折腾了半天，才确定是我手上这块内存条有问题。唉，修电脑真麻烦~！
后来？后来我擦了好多次，再把‘坏’的那块内存条装上去，又好了，一切正常了现在。电脑就像女人啊，不过我这台电脑算是脾气好了，已经是用她五六年了，就发过两三次脾气而已，其它时候还是挺和睦相处的。
2006/07/15......
了解遗传算法(2006-06-29 22:08:00)
摘要：了解遗传算法
遗传算法是一种最优化算法，所谓最优化问题，就是这样一类问题，满足它的解（称为可行解）有很多（通常是极多）对于每一种解有一个评价函数得到一个评价值，也就确定了解集的一个偏序关系，在这个偏序关系的求最小值（或最大值）或者近似最小值（或最大值）。因为通常可行解非常之多，所以确定性算法很难做到这一点，而遗传算法是模拟了生物学中物种进化的过程的一种最优化算法，简单来说，遗传算法=遗传操作+遗传选择。
在算法开始之前要做一下准备工作：编码。
对于不同的问题有不同的解的形式，但要运行遗传算法就要对其进行抽象的编码，也就是确定染色体的形式，这里的染色体就是用某种特定的编码方式描述一个解，通常一个具体的解也称为个体。而多个不同的个体就组成一个种群，一个种群内有统一的编码方式。这些概念都完全等同于生物学中的概念，它们是平行的。
例如，N个城市的旅行商问题(TSP)，假如用1,2,...N表示这N个城市，那对于任意这样的一个排列1p2p3...pN就表示了一个解，这个串就可以认为是一个染色体，它表示一个个体的基因。
遗传算法有一些基本的操作，如选择、交叉和变异等。
选择操作：
首先要知道适应度函数，所谓的适应度函数就是评价函数，通常是问题的目的函数（或它的倒数），它描述了个体的优劣程度同时也决定了选择操作的概率，设fi表示第i个个体的适应度值，那选择第i个个体的概率就是fi/∑fj，简单来说，这个概率的大小就决定了该个体是被淘汰还是被保留。通常的具体做法是用类似赌盘的方法，每个个体占它的适应度那么宽的转盘大小，每次掷色子，落到哪一格就选哪一格对应的个体。
交叉操作：
交叉操作就是让2个以上的染色体进行交叉产生后代的过程，具体的交叉操作要看具体的问题。不过我觉得有一个原则，就是要有对称性，交叉得到的后代中的基因要来源于父代的所有个体中，也就是说n个个体进行交叉是和它们的排列没关系，这样子代才有机会得到更优秀的基因。交叉操作是遗传算法中最重要的操作。最简单的基本方式是交换父代中染色体片段。
变异操作：
生物可以突变，有时候突变是好的，有时候却是坏的，但正是因为有了突变才让有限的种群中基因库可以非常丰富，也保证了种群的适应能力。变异操作通常是翻转个体中某段染色体，编码后的染色体在计算机中都是01串，也就可以......
博弈与人工智能(2006-06-15 02:50:00)
摘要：突然迷上了博弈算法，真是一件让我疯狂的事儿，我极渴望去做。
首先让我理下思绪，起码看清楚目前前人是怎样做的：
还是先给个网站吧，前天搜到的‘计算机博弈门户网站’URL:http://www.elephantbase.net，里面有好些老外写的译文，除了估值函数那部分太过潦草外（当然作者是都不愿意公开的），其它都讲叙得非常清楚。
1，博弈为什么这么有趣，这么有挑战，现在的计算机速度如此之快不是很容易解决吗？
我的理解是，这是因为棋类对弈中的‘变换’非常之多，我有一个表哥的中国象棋下得非常好，他原来对我说过一句话‘象棋这么有趣是因为，你一辈子都不会走出两盘完全相同的棋’，不信？那就算算，在棋类算法里都考虑一个叫‘博弈树’的状态树，树中每一个结点表示一个‘局面’，子结点表示可以由一步走成的局面，每一步可以有不同的‘着法’，着法的个数叫‘分枝因子’，当然每一个局面的分枝因子不尽相同，但大致差不多，就平均来算，中国象棋比较多，有30种左右，于是从上往下，可能走出的局面数成指数增长：1+30+30^2+30^3+...，不要以为只是简单的考虑30种着法，这里面的选择可并不简单。
所以，博弈的乐趣就在于不管是人还是机器都不可能完全了解这么大一棵树上的所有信息，不可能分析到所有的可能局面，于是就可以真正的较量。不要以为这只是数量问题，觉得只要计算机速度够快就可以完全解决，指数增长的东西除了上帝谁都追不上！机器的运算速度永远也追不上它的。所以智能的体现就在于‘方法’，我们只能求近似解，那就要看谁的更精确！
2，我们不能完全考虑，那就只考虑有限深度。迭代加深是很好的方法，如果不控制深度，那将和‘死机’的现象一样，程序掉进了博弈树中，永不回溯啦~当然实际当中很可能是系统栈用完。
3，按深搜的方式搜索，再控制搜索的深度，那要怎么取舍搜索出的结果呢？估值！也就是评价啊，不过要明确的是，这样的评价只是对一个局面做评价，就是说只是对一个点做评价，象棋是活的，动态的，所以不可能精确，但是它必须是近似正确的，有多接近就有多聪明（但是有一个局面的评价是非常准确的，那就是判负的局面，由规则得到）；更加简单的说，就是一个启发值，起到的作用只不过是让搜索少走一些‘弯路’。怎么估值？各种棋类游戏方法不同，不过有一......
模式匹配的KMP算法详解(2006-06-12 16:33:00)
摘要：模式匹配的KMP算法详解
这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：
int Index(String S,String T,int pos)//参考《数据结构》中的程序
{
i=pos;j=1;//这里的串的第1个元素下标是1
while(i<=S.Length && j<=T.Length)
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2;j=1;}//**************(1)
}
if(j>T.Length) return i-T.Length;//匹配成功
else return 0;
}
匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子：
S:aaaaabababcaaa T:ababc
aaaaabababcaaa
ababc.(.表示前一个已经失配)
回溯的结果就是
aaaaabababcaaa
a.(babc)
如果不回溯就是
aaaaabababcaaa
aba.bc
这样就漏了一个可能匹配成功的情况
aaaaabababcaaa
ababc
为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先......
证明(0,1)~[0,1](2006-06-03 20:29:00)
摘要：要证明(0,1)和[0,1]等势，就是要找到一个双射函数f:[0,1]->(0,1)，考虑函数f(x)=x，是一个f:(0,1)->(0,1)上的双射函数，而关键就是要在这中间加入0和1这两个元素。前面讨论过可数集，想想无穷饭店的老板在知道饭店已住满客人时又来了有限k位客人是怎么做的？没错，对于可数集完全可以做到，只要让所有客人往后平移k个房间号就可以住下了，而(0,1)的基是阿列夫1比可数集的阿列夫0要大，也就是说存在着一个它的子集是可数集。
这样一来思路就清晰了，从(0,1)中找一个子集A，使A是可数集，也就是一个无穷饭店啦，f(x)=x表示已经住满了客人，现在新来了两位客人0,1，要住下来，OK，所有客人往后移两个房间号搞定。A怎么找？其实怎么找都行，甚至我抽象的描述一下也可以，因为证明是要证存在，还是构造性的找出来比较好，设A={1/2,1/3,1/4,...1/n,...}，于是找到的函数就是：
g(x)=
if(x==0) g(x)=1/2
if(x==1) g(x)=1/3 //新来的两位客人住前两个房间
if(x==1/n) g(x)=1/(n+2) n为正整数且n>=2 //老客人从n号房间搬到n+2号房间
if(x属于(0,1)-A) g(x)=x //剩余的不变
双射已经找到了，故(0,1)~[0,1]，证毕。......
[TOJ]1010数素数(2006-04-25 13:04:00)
摘要：数素数（http://acm.tongji.edu.cn/showproblem.php?problem_id=1010）
Problem
素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。
其实是个简单问题，但对于给出的数据范围（0<M<N<1000000），总是迫使我寻找更快更省的方法。
一开始我就想找到一种数学方法，如果找到了当然是最快最省的，但是，还没找到，于是只好用笨的方法。
1、用素数的定义
素数是的只能被1和它本身整除的自然数。那就从2到sqrt(n)进行试除，如果有一个数能整除n，那n就不是素数，否则n就是素数。
如果不仔细想，会认为这样做已经是非常快了，其实做了很多多余的工作，以下简单分析：首先从奇偶性上看，所有的素数中只有2是偶数，也就是说几乎所有素数都是奇数，而在试除的过程中，我们还用4,6,8之类的偶数去试除，真是愚蠢到家了。同样的道理，如果3不能整除的，那所有的3的倍数也不能整除，那也不必用6,9,12去试除了。
稍微进行改进的方法是，建立素数表，于是判断一个数n是否是素数就可以用2到sqrt(n)间的素数去除n，如果有一个素数能整除n，那n就不是素数，否则n就是素数。
我说‘稍微’改进，实际上对于基于‘试除’的求素数方法，已经是达到了极致，同时对于n比较大的数，进行试除次数也会大大降低。以下数据可以说明问题：
n= sqrt(n)= 直接试除次数 基于素数表试除次数
10000 100 98 25
&nbs......
最长递增子序列问题的求解（LIS）(2006-04-23 17:13:00)
摘要：应该把这个问题看成一个基本问题，感觉用动态规划的算法比较容易想到，也很不错，关于那个改进的O(nlogn)的算法有些不太明白，大部分动态规划都要寻求一个当前状态的最小值或最大值，如果按这样的思想，那不是所有的DP算法都可以降为O(nlogn)？
以下文章转载自CSDN，我收藏一下。因为找不到原作作者，敬请原谅，如果您是作者请告知我。
最长递增子序列问题的求解
最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么显而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想，能够锻炼设计较复杂算法的思维，我对这个问题进行了较深入的分析思考，得出了几种复杂度不同算法，并给出了分析和证明。
一， 最长递增子序列问题的描述
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
二， 第一种算法：转化为LCS问题求解
设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。
最长公共子序列问题用动态规划的算法可解。设Li=< a1,a2,…,ai>,Xj=< b1,b2,…,bj>，它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程：
这可以用时间复杂度为O(n2)的算法求解，由于这个算法上课时讲过，所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n2)的时间，算法的最坏时间复杂度为O(nlogn)＋O(n2)＝O(n2)。
三， 第二种算法：动态规划法
重读《悟空传》(2006-04-11 15:01:00)
摘要： 《悟空传》是本好书，任何年龄的人读都有不同的收获，我中学的时候第一次读，全当成笑话书，也是完全可以的。
悟空，有一个好名字，同样也注定有不同的一生。它不像《西游记》把悟空太过神化绝对化完美化，这里的悟空更加有血有肉一些，同样也包括另外一些人物，比如八戒、玄奘等。从人物的角度看，这是一本不错的小说。
我觉得非常经典的一回，少年玄奘和云游法师斗法的一回：
－－－－－－－－－－
第七回
--------------------------------------------------------------------------------
她化成一只纯白百灵来到大殿窗边，这里最多的是山雀，但她怎么能变那种俗鸟呢？
殿内坐了一地和尚，中间有两个老的。一个持禅杖，身边还有包袱，象是外地云游到此的。另一个自然就是本寺的主持了。
“法明长老，久闻金山寺佛法昌盛，特来请教。”那持禅杖的老和尚道。
“天杨师父，不敢。”
“什么不敢？”天杨忽厉声道，“敢做不敢应么？”
法明长老一愣，才悟道这就开始论法了，于是一笑答道：“敢应不敢放。”
“放下！”
“我两手皆空，放什么？”
“那为什么还抓着？”
“心有灵犀。”
两人一问一答，问的凶答的快，只听的两旁僧人议论纷纷。
“你听懂了么？”“没有啊？”“哎，太高深了。”“真是玄机啊！”
小白龙只找那玄奘，却见他在人群之中，正向这边看着她。
小白龙心一跳，只觉脸要红了，忽发现自己是一只鸟，他看不见脸红的。
只见玄奘对她笑了一笑。
这人莫不是认得我？小白龙想，不可能的，他不过一凡人而已啊。
这边论答已到了关键时刻，两个老和尚头上都起了白烟。
天杨：“如何是禅？”
法明：“是。”
天杨：“如何是正法眼？”
法明：“不是。” ......
我喜欢的台球游戏(2006-04-11 14:49:00)
摘要： 昨天突然想玩台球游戏，我就想起了两三年前玩的雅虎的台球游戏，我敲cn.games.yahoo.com打开久违了的游戏页面，选了Break It Up全球游戏室。
这个台球游戏很朴素，８球美式打法，跟我家乡的街头台球打法差不了多少。
来这里打球的人都是来自全球各地的，我偶尔甩两句我那破Ｅ语和人搭话，我发现大多数说英语的人都很有礼貌，他们喜欢台球但不争强好胜，打出好球会称赞你，自己打得不好就会笑一笑。
我虽不太喜欢英语，但和人交流的感觉还不错，这里都会说省略语，比如：ns:nice shot,gg:good game,ty:thank you,thx,thanks,lol,laugh out l..(就是笑一笑啦)。
我非常喜欢台球啊，虽然是一个人参与，但感觉我像是教练，而桌上八个小球都是我的队员，我会一个一个进球，直到黑球轻松完成游戏，整个是一个完整的：小球、黑球还有我和我的球杆。
我想我变了不少，我从一个与人争强（当然也可以说成是上进）一个自以为是一个目中无对手的孩子，慢慢成熟起来。......