## 在北京的数学系的娃儿们

03 的哥们好像就来了张博、刘元杰和刘增禄，02 的也就来了一个获鼎，再加上我认识的学弟中洋、程棵和新雨，剩下的就全是陌生人了。

## Math in CS：置换的轮换分解

1, 2, 3, 4, 5
2, 5, 4, 3, 1

1, 2, 3, 4, 5
2, 5, 4, 3, 1

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
* the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
int i, j;
if (a == NULL)  return 0;     /* Test input */
a[0] = 1;
for (i = 1; i <= n; ++i)      /* Test input */
if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
a[0] = 0;
return a[0];
}

for (i = 1; i <= n; ++i)
if (a[i] > 0) {
j = i;
while (a[j] > 0) {        /* Follow the cycle */
a[j] = -a[j];
j = -a[j];
}
if (j != i)  a[0] = 0;    /* Test the cycle */
}

for (i = 1; i <= n; ++i)
a[i] = a[i] > 0 ? a[i] : -a[i];

return a[0];
}

100 个囚犯，每人有一个从 1 到 100 的不重复不遗漏的号码，国王把这些号码收集起来，打乱放进 100 个箱子里，每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前，每人可以打开至多 50 个箱子来寻找自己的号码，可以一个一个打开（即可以根据之前箱子里看到的号码来决定后面要打开的箱子）。如果有一个囚犯没有找到自己的号码，那么这 100 个人一起被处死；只有当所有的囚犯都找到了自己的号码，他们才会被国王全部释放。

$P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100} \frac{1}{k}=1-(H_{100}-H_{50})$

$P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059$[6]

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是：0.31182782068980479698，Bash 代码：

STR="1-("
for i in seq 51 99; do
STR+="1/$i+" done STR+="1/100)" echo$STR | bc -l

## 维度：数学漫步

My name is Hipparchus. I lived in the second century before the birth of Christ, and I don't think I'd be bragging if I told you that I am the father of the sciences of Geography and Astronomy. You know, I wrote more than 14 books but unfortunately they have almost all been lost in the mists of time. I was responsible for the first catalogue of the stars, founded the field of mathematics called trigonometry and even invented the astrolabe. Fortunately, my brilliant successor Ptolemy, three centuries after my time inspired by my work, took up where I left off, and nowadays historians sometimes can't determine what was my contribution and what was his.

SMplayer:
Options->Subtitles->Default subtitle encoding: UTF-8

VLC Player：
Settings->Preferences->Video->Subtitles/OSD->Text renderer->Font:
Linux(Ubuntu) 下找到：/usr/share/fonts/truetype/wqy/wqy-zenhei.ttf（可以换成系统中其它的中文字体）
Windows 下找到：C:\WINDOWS\Fonts\simsun.ttc
Settings->Preferences->Input/Codecs->Other codecs->Subtitles->Subtitles text encoding: UTF-8

PS: 特别推荐一下 SMplayer