下面的视频是The Simpsons的95年Halloween特别版Treehouse of Horror VI的最后一部分，名字叫做Homer^3：

  

YouTube链接：http://www.youtube.com/watch?v=AzecHW-DTqY
难怪说The Simpsons是一部属于Geek的剧集，里面隐藏了好多彩蛋！
你能在那个三维空间里看到些什么东西？





我看到了：

• 信息学界的终极难题
  
• 一段由ASCII码组成的字符串
  
• 一个我最喜欢的数学等式，由三个数学界最神奇的数组成
  
• 一个最简单、最基本的等式
  
• 一个Fermat大定理的“反例”（95年的时候Fermat大定理还没有得证）
  
• 一个物理公式，它给出将导致整个宇宙坍塌的宇宙密度的临界点

    考虑一个事件，它有两种概率均等的结果。比如掷硬币，出现正面和反面的机会是相等的。现在我们希望知道，如果我不断抛掷硬币，需要多长时间才能得到一个特定的序列。

序列一：反面、正面、反面
序列二：反面、正面、正面

    首先，我反复抛掷硬币，直到最近的三次抛掷结果形成序列一，然后我记下这次我抛掷了多少次才得到了我要的序列。重复执行这个过程，我可以算出得到序列一平均需要的抛掷次数。同样地，反复抛掷硬币直到序列二产生，它所需要的次数也有一个平均值。你认为这两个平均值哪一个大哪一个小？换句话说，出现序列一平均所需的抛掷次数少还是出现序列二平均需要的次数少？


    大多数人会认为，两个序列会以同样快的速度出现，因为在所有“正”和“反”的8种三元组合里，“反正反”和“反正正”各占1/8，其概率是均等的。而事实上，我们将会看到掷出序列二所需的次数更少一些。不妨考虑这样一个问题：在由“正”和“反”构成的n位01序列中，有多少个序列以序列一结尾但之前不曾出现过序列一？有多少个序列以序列二结尾但之前不曾出现过序列二？当n比较小时，两者答案是一样的（例如n=3时符合要求的情况都是唯一的），但到后来n越大时，两者的差距越明显：后者的个数总比前者的个数要多一些。不妨看一看n=6的情况。对于序列一，只有以下5个序列是符合要求的：

• 反反反反正反
  
• 反正正反正反
  
• 正正正反正反
  
• 正反反反正反
  
• 正正反反正反

    但对于序列二来说，符合条件的序列就有7个：

• 反反反反正正
  
• 反正反反正正
  
• 反反正反正正
  
• 正反反反正正
  
• 正正反反正正
  
• 正正正反正正
  
• 正反正反正正

    你可以通过计算机编程枚举，计算一下n为其它值的情况。计算结果和刚才也一样：在n位01序列中，以序列二结尾但之前不含序列二的情况不会少于以序列一结尾但之前不含序列一的情况。这说明，抛掷第n次硬币后恰好出现了序列二，其概率不会小于恰好出现序列一的概率。显然，当n渐渐增大时，这个概率应该呈下降趋势；同时，随着n的增长，两个序列各自出现的概率由相等开始慢慢拉开差距，第n次抛掷产生序列二的概率下降得要缓慢一些，或者说更多的情况集中发生在n更小的时候。因此总的来说，出现序列二所需要的抛掷硬币次数的期望值更小。
    虽然我们通过一系列的观察验证了这个结论，并且我们也相信这个结论是正确的（虽然没有严格的证明），但我们仍然不是很接受这个结论。这种情况是有悖于我们的直觉的，它与我们的生活经验不相符合。此刻，我们迫切需要一个解释，来说明这种出人意料的反常现象产生的原因。




    如果不亲自做几次试验的话，你很难体会到这种微妙的差距。考虑整个游戏的实际过程，“反正正”序列显然会出现得更早一些。假如某一次我们得到了序列“反正”。如果我们需要的是“反正反”序列，那么下一次抛掷结果为反面将结束本轮的抛掷，而下一次是正面则前功尽弃，你必须再次从零开始。如果我们需要的是“反正正”序列，那么下一次抛掷结果为正面将结束本轮的抛掷，而下一次是反面的话我至少不会惨到一切归零，这相当于我已经有了一个反面作为新的开头，只需再来两个正面即可。这样看的话，提前掷出“反正正”的可能性更大一些。
    反复体会上面的想法，了解KMP算法的网友会恍然大悟：这就是KMP算法的基本思路！考虑这样一个问题：我们在当前字串中寻找子串“反正正”第一次出现的位置。假如当前已经能匹配模式串的前两个字“反正”，主串中的下一个字是“正”则匹配成功，主串的下一个字是“反”则将使模式串的当前匹配位置退到第一个字。考虑一个更复杂的例子：我们希望在主串中寻找子串abbaba，现在已经在主串中找到了abbab。如果主串下一个字符是a，则成功匹配；如果主串下一个字符是b，则模式串最多能匹配到的位置退到了第三个字符，我只需要从abb开始继续匹配，而不必一切从头再来。
    我们可以用KMP算法完美地解决上面的问题。首先预处理出一个数组c，c[i,0]表示模式串匹配到了第i个字符，主串下一个字符为0（反）时，模式串的匹配位置将退到哪里；同样地，c[i,1]表示模式串匹配到了第i个字符，主串下一个字符为1（正）时，新的模式串匹配位置在什么地方。设f[i,j]表示第i次抛掷硬币后恰好匹配到模式串第j位有多少种情况，则f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k满足c[k,0]=j，l满足c[l,1]=j。将f[i,j]除以2的i次方，我们就得到了相应的概率值。或者更直接地，设P[i,j]表示第i次抛掷硬币后，最远能匹配到的模式串位置是第j位的概率，则P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我们还应该添加一种特殊的概率值P[i,*]，它表示在主串第i个字符以前已经成功匹配过的概率，这样的话下表中每一列的和才能为1。

    来看一看程序的输出结果：
Pattern 1: s[]="aba"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1641  0.1445  0.1270  0.1113
匹配到s[1]  0.5000  0.5000  0.3750  0.3125  0.2813  0.2500  0.2188  0.1914  0.1680  0.1475
匹配到s[2]  0.0000  0.2500  0.2500  0.1875  0.1563  0.1406  0.1250  0.1094  0.0957  0.0840
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.0938  0.0781  0.0703  0.0625  0.0547  0.0479
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3438  0.4219  0.4922  0.5547  0.6094

Pattern 2: s[]="abb"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.1250  0.0625  0.0313  0.0156  0.0078  0.0039  0.0020  0.0010
匹配到s[1]  0.5000  0.5000  0.5000  0.4375  0.3750  0.3125  0.2578  0.2109  0.1719  0.1396
匹配到s[2]  0.0000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1563  0.1289  0.1055  0.0859
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.1250  0.1094  0.0938  0.0781  0.0645  0.0527
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3750  0.4844  0.5781  0.6563  0.7207

    这下我们可以清楚地看到，序列二提前出现的概率要大得多。注意到，根据我们的概率定义，表格中每一列的数字之和都是1。同时，倒数第二行的数字之和（有无穷多项）也应该为1，因为最后一行的概率就是倒数第二行的概率值累加的结果，而根据最后一行概率的定义，主串无穷长时已找到匹配的概率应该为1。因此，我们也可以把倒数第二行看作是模式串在主串第i个位置首次匹配成功的概率。我们可以根据这一结果近似地计算出抛掷次数的期望值。

Matrix67原创
转贴请注明出处

    一架客机上有100个座位，100个人排队依次登机。第一个乘客把机票搞丢了，但他仍被允许登机。由于他不知道他的座位在哪儿，他就随机选了一个座位坐下。以后每一个乘客登机时，如果他的座位是空着的，那么就在他的座位坐下；否则，他就随机选一个仍然空着的座位坐下。请问，最后一个人登机时发现唯一剩下的空位正好就是他的，其概率是多少？









































    当最后一个乘客登机时，最后一个空位要么就是他的，要么就是第一个乘客的。由于所有人选择座位时都是随机选择的，这两个位置的“地位”相等，它们所面对的“命运”是相同的，不存在哪个概率大哪个概率小的问题。因此，它们成为最后一个空位的概率是均等的。也就是说，最后一个人发现剩下的空位正好是他的，其概率为50%。

来源：cut-the-knot
不知不觉地，这已经是第400篇日志了

    各种违反常理的错觉图片和数学事实告诉我们，我们的直觉并不可靠。其实这本身就是一种错觉，它让我们觉得我们的直觉总是不可信的。而事实上，多数情况下我们的直觉都是可信的，而理性的思考反而会带来一些错误。

    我的书桌有8个抽屉，分别用数字1到8编号。每次我拿到一份文件后，我都会把这份文件随机地（概率均等地）放在某一个抽屉中。但我非常粗心，有1/5的概率我会忘了把文件放在抽屉里，最终把这个文件搞丢了。
    现在，我要找一份非常重要的文件（比如GF的处女鉴定书）。我将按顺序打开每一个抽屉，直到找到这份文件为止，或者令人同情地，翻遍了所有抽屉都还没找到这份文件。考虑下面三个问题：

• 1. 假如我打开了第一个抽屉，发现里面没有我要的文件。这份文件在其余7个抽屉里的概率是多少？
  
• 2. 假如我翻遍了前4个抽屉，里面都没有我要的文件。这份文件在剩下的4个抽屉里的概率是多少？
  
• 3. 假如我翻遍了前7个抽屉，里面都没有我要的文件。这份文件在最后一个抽屉里的概率是多少？

    你猜一猜这三个概率值是越来越大还是越来越小？你能算出准确的值来吗？





































    三个概率值分别是7/9, 2/3和1/3。可能这有点出人意料，这个概率在不断减小；但设身处地地想一下，这也不是没有道理的。这正反映了我们实际生活中的心理状态：假如我肯定我的文件没被搞丢，每次发现抽屉里没有我要的东西时我都会更加坚信它在剩下的抽屉里；但如果我的文件很可能被搞丢了，那每翻过一个抽屉但没找到我的文件时，我就会更加担心。我会越来越担心，感到希望越来越渺茫，直到自己面对着第8个抽屉，呆呆地看着我的最后一丝希望，同时心里想：完了，这下可能是真丢了。








































    平均每10份文件就有两份被搞丢，其余8份平均地分给了8个抽屉。假如我把所有搞丢了的文件都找回来了，那么它们应该有2个抽屉那么多。这让我们想到了这样一个有趣的思路：在这8个抽屉后加上两个虚拟抽屉──抽屉9和抽屉10，这两个抽屉专门用来装我丢掉的文件。我甚至可以把题目等价地变为：随机把文件放在10个抽屉里，但找文件时不允许打开最后两个抽屉。当我已经找过n个抽屉但仍没找到指定的文件时，文件只能在剩下的10-n个抽屉里，但我只能寻找剩下的8-n个抽屉，因此所求的概率是(8-n)/(10-n)。当0<=n<=8时，函数是一个递减函数。

参考资料：cut-the-knot
做人要厚道 转贴请注明出处

图片来源：http://brownsharpie.courtneygibbons.org/?p=313 一个非常有意思的网站！

    Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍：
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

    code/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数，与上面的代码唯一不同的就是这个函数返回的是number*y：
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

    这样的代码速度肯定飞快，我就不用多说了；但算法的原理是什么呢？其实说穿了也不是很神，程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 - a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x - f(x)/f'(x)，式子化简为x' = x * (1.5 - 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。
    但这段代码真正牛B的是那个神秘的0x5f3759df，因为0x5f3759df - (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的，只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事，很少有人说得清楚。这篇论文比较科学地解释了这个常数。

    下面这种方法可以很有效地求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
    例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：

(       4  + 2/   4     ) / 2 = 2.25
(    2.25  + 2/   2.25  ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
....

      
    这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2。
    同样的方法可以用在其它的近似值计算中。Quake III的源码中有一段非常牛B的开方取倒函数。