小名开开

ow.thnuclub.com 条目编辑规范

发表于 2016-09-01 分类于开开开发

1120 update：『下载时自动根据文本内容重命名』终于实现了。不能启用的请关闭 adblock 再试。
1006 update: 添加 Ctrl+Enter 功能：提交当前条目，并自动跳到下一条编辑面板，方便连续编辑。
0522 update: 在提交编辑文本内容时，会再播放一遍该音频，方便检查。
12.11 update: 试图添加『下载时自动根据文本内容重命名』功能 失败了。原因是浏览器限制，跨域 a 连接中的 download 属性会被忽略。请勿再提类似需求。
11.20 update: 请勿随意改动英雄标签，目前数据已经是通过客户端导入的正确数据了，除非你有非常确实的理由。比如为对话语音添加对话另一方是可以的，但猜测就不必了。

感谢您的热心贡献。

如果确信某个条目有错误或需要补充，请直接在页面上修改。

由于音频资源是托管在国外的免费空间上的，因此 ~~移动宽带~~ 国内部分品牌宽带可能无法访问，请自行准备梯子。

这篇规则说明并规范守望先锋在线音频小站 http://ow.thnuclub.com 条目编辑时的格式。这份规则不是强制的，但相同的格式有助于更好地回馈大家的贡献。

基本格式：

【黑百合】（对猎空）哦呵呵，似乎我们这次要合作了。
【地图】【好莱坞】【导演】还要多久？真希望这玩艺还有轮胎。
【源氏】竜神の剣を喰らえ（尝我龙神剑）（技能演示语音）

细则：

1. 发出语音的英雄名、地图名、特有元素名称，使用黑色方括号【】括起，放在条目开头。如果有多个元素则从大类到小类排列。

2. 并未在语音内出现，但有助于说明场景的，比如对话另一方，触发条件等，使用圆括号（）括起，放在正文文本前。

3. 并未在语音内出现，但有助于解释语义的，比如解释台词梗等，使用圆括号（）括起，放在正文文本最后。

4. 非中、英文语音（岛田兄弟日文、查莉娅俄文、D.Va 韩文、堡垒蜂鸣器文等），有能力可以使用该语言原文，并使用括号配以中文翻译，放在紧邻正文文本后。无法写出原文的，用中文或（中文）。英语文本可以不配中译。

5. 使用规范的英雄、地图、元素名称：莱因哈特大锤、查莉娅毛妹、路霸猪，尽管小站有少量繁体与海外访客，但考虑到最大用户群和称呼一致性，还是以简体中文客户端的英雄名称为准。

简体中文版英雄名称：堡垒，D.VA，源氏，半藏，狂鼠，卢西奥，麦克雷，美，天使，法老之鹰，死神，莱因哈特，路霸，士兵：76，秩序之光，托比昂，猎空，黑白合，温斯顿，查莉雅，禅雅塔，安娜，黑影，奥丽莎，莫伊拉。

6. 优先贡献尚未有内容的条目，越往后翻新条目越多。尽量保证听译的准确，不确定的使用三个问号『？？？/???』标记。

7. 即使如此，您只要愿意贡献，依然可以无视以上规则。『黑百合 – （法语听不出来）』同样可以接受，留待别人去改进。

1. 不确定的内容尽量都勾选。例如听出是女声，但不确定是猎空、D.Va 或者美的声音，则三位都勾选上，以增大曝光机率，更快地修正结果。此条部分废弃，现在涉及英雄的语音已通过拆解客户端导入了正确数据，不必猜测是哪位英雄了。尽管如此，技能音效、环境音效等依然需要通过猜测解决。
此条已废弃。

2. 对话的双方英雄都勾选上。由客户端拆解只能得到发出语音的英雄名，与其对话的另一名英雄，需要手动钩选。

3. 语言数据来自于客户端本身（中英），尽管如此，对于源氏、半藏、小美等英雄，可以按实际情况添加标签，但请勿改动旧标签。

4. 没有数据时，不会得到筛选结果，所以请勿询问为何搜索结果比标签筛选结果多。

5. 堡垒的语音是不分语言的，中英完全相同。

===============================================

由于音频内容增多，单个包的体积已经超出 github 限制，故不得不拆分为 256 个包了。

打包下载地址，随版本更新，请使用批量下载工具：

计算机里的随机数

发表于 2016-07-31 分类于硬用数学

计算机中没有随机数。

本文完。

小游戏里的小随机

如果做个打地鼠小游戏，要让地鼠从 9 个小洞里『随机』出现，不能挨个洞出来。简单办法是给九个小洞编上号 0-8，然后令 Hole_n+1 = (4 * Hole_n + 4) mod 9。也就是乘 4 加 4，然后除 9 取余数。游戏开始，我们希望地鼠第一次从中间的洞，也就是 4 号洞里出来。所以 Hole₁=4。得到的结果是：

1	4,2,3,7,5,6,1,8,0,4,2,3,7,5,6,1,8,0,4,2,3,7,5,6,1,8,0,……

也就是地鼠会这样出现：

mouse

看起来很规律，记一记就记住了。但把上面公式的几个常数放大，变成 X_n+1 = (1103515245 * X_n + 12345) mod 2³¹，序列就变成了：

4,119106029,1583775792,1104372736,1199162368,546350080,1200489472,1420813312,2119975936,33629184,192185400,1547013152,339646976,1301529152,177825024,1578512704,703899648,1482405888,1629325312,151197696,1470195776,1593643776,1066092288,1743743744,1972027136,205882112,964884288,1603859968,320138752,342722112,654956928,……

数字太大，做一下归一化。因为是 mod 2³¹的结果序列，所以归一化也就是除以 2³¹，得到：

0.0000000019
0.0554630668
0.7375030741
0.5142636299
0.5584034920
0.2544140816
0.5590214729
0.6616177559
0.9871907234
0.0156598091
0.0894933008
0.7203841358
0.1581604481
0.6060717404
0.0828062296
0.7350522578
0.3277788162
0.6902990341
0.7587137222
0.0704069138
0.6846132576
0.7420982122
0.4964379072
0.8119939566
0.9182966948
0.0958713293
0.4493092597
0.7468554974
0.1490762234
0.1595924199
0.3049880862
…………

我们再次把这个序列处理回地鼠出现的序列，Floor(X_n*9)，得到：

1	0,0,6,4,5,2,5,5,8,0,0,6,1,5,0,6,2,6,6,0,6,6,4,7,8,0,4,6,1,1,2,……

来 1000 个：

0,0,6,4,5,2,5,5,8,0,0,6,1,5,0,6,2,6,6,0,6,6,4,7,8,0,4,6,1,1,2,6,4,1,2,0,2,3,1,1,6,6,4,6,4,5,2,3,8,0,7,8,4,3,0,4,1,1,0,4,3,5,4,6,8,8,1,2,5,6,5,8,2,4,8,1,2,6,3,1,3,7,8,8,4,2,8,7,8,4,5,3,6,3,3,6,8,0,1,1,4,8,0,5,3,5,7,5,4,4,0,7,5,3,1,4,1,2,3,5,8,7,0,5,6,5,0,6,0,4,3,1,7,4,0,3,4,6,5,2,5,5,8,1,2,7,7,3,8,0,4,8,5,3,6,7,6,1,5,2,5,0,1,0,6,5,3,6,0,7,1,3,0,1,2,0,2,4,6,0,2,1,5,6,2,1,0,0,0,0,7,2,4,0,1,6,2,4,3,4,1,5,1,6,7,3,7,8,3,3,3,3,6,1,1,4,0,3,7,5,0,0,3,7,7,7,5,4,3,8,2,2,2,7,7,2,6,1,2,2,6,3,8,8,3,3,0,2,2,3,6,1,4,6,1,8,1,5,7,1,7,6,5,0,6,4,2,0,6,0,0,8,7,6,8,0,1,2,5,5,1,1,3,7,7,0,3,2,4,5,1,2,1,0,8,1,6,6,4,5,5,1,0,1,5,5,6,5,3,5,7,5,0,2,7,8,7,6,5,6,7,0,1,0,3,4,1,4,4,2,3,7,8,1,5,4,1,8,8,6,5,0,8,1,6,4,7,6,4,1,8,5,3,5,8,6,4,7,3,3,0,7,2,3,3,8,0,5,3,6,6,3,0,1,4,7,4,0,1,5,0,1,4,3,0,4,0,0,1,0,5,4,4,5,4,3,6,4,8,5,7,6,7,4,0,8,4,2,7,8,6,6,0,4,4,6,6,6,4,2,3,8,2,1,6,8,5,3,6,4,3,7,3,4,5,4,8,6,1,5,0,4,1,7,6,5,7,3,5,6,5,7,5,0,4,0,1,7,0,5,6,3,0,8,7,6,3,3,3,8,1,3,4,8,1,4,7,3,3,3,1,6,0,4,8,8,3,7,5,7,3,8,3,3,7,2,7,7,1,3,7,2,6,7,1,1,7,4,4,8,0,7,2,6,7,6,0,7,7,1,8,2,3,4,7,3,3,4,3,0,0,7,5,1,8,2,3,1,0,1,4,7,2,0,0,7,8,5,3,1,0,3,8,5,7,8,5,1,5,3,7,3,6,0,8,8,7,8,8,4,7,1,0,6,5,6,4,5,0,4,7,0,8,5,8,8,5,4,3,8,5,4,3,8,6,6,4,6,3,3,3,1,6,3,0,4,7,7,2,2,2,7,1,3,2,0,4,2,2,2,1,2,2,8,2,4,7,8,7,1,2,6,8,0,7,3,1,0,7,0,0,8,6,1,0,0,4,1,0,5,4,2,8,8,2,8,7,7,0,3,3,8,8,2,4,1,3,6,1,1,5,3,6,8,3,3,3,5,4,4,8,4,6,1,6,2,8,1,1,3,0,0,5,0,0,2,2,8,8,8,8,3,7,1,0,0,5,0,7,7,7,7,4,3,2,6,8,7,6,7,0,4,8,7,2,2,7,6,3,5,2,8,8,5,6,8,2,0,8,3,7,0,4,5,4,4,0,5,3,5,4,1,7,3,7,5,8,4,6,0,6,2,1,4,6,7,8,0,3,0,5,5,3,2,5,2,6,4,7,0,6,5,2,1,0,4,1,5,3,4,6,8,0,1,5,5,1,1,1,3,8,3,2,7,4,5,4,3,1,4,0,8,3,5,6,7,4,5,8,2,6,2,1,4,6,3,6,3,7,2,5,8,2,5,8,1,3,3,5,7,8,5,4,6,0,7,3,3,4,8,3,2,4,0,4,4,2,7,6,2,1,0,4,0,1,8,3,2,8,0,5,2,1,1,1,2,1,7,4,1,1,4,1,8,7,5,6,2,5,3,4,6,2,8,3,7,6,7,5,2,1,0,7,1,8,8,5,5,7,2,5,6,4,4,2,5,2,0,2,5,6,8,2,4,6,3,7,4,5,0,0,4,1,2,1,7,1,2,5,3,3,0,3,8,7,6,0,2,5,5,6,4,2,0,8,7,2,0,2,5,0,4,5,4,8,2,7,6,4,1,7,7,6,5,1,6,8,0,0,1,0,4,6,3,0,7,2,7,5,1,0,5,5,2,6,0,7,0,4,0,……

这个已经足够『随机』了，发现不了什么明显的规律，统计上也符合平均分布。要说规律也是有的，就像之前 mod 9 于是出现了 9 个一循环一样。在把常数增大以后，这个序列的循环也变成了 2³¹。

因为打地鼠游戏中的『随机』的要求，只是无法让玩家找到并掌握规律。任何一个玩家都不可能打上 2³¹ 只地鼠，所以这个算法生成的『随机』已经足够了，截取其中一段完全符合打地鼠的要求。

事实上， f_n+1 = (a * f_n+b) mod c 正是一种很传统的计算机随机数生成法，称之为线性同余法，是使用最广泛也是最古典的随机数生成算法之一。随着时代发展和实际需求不断加深，更加严格的算法被不断发展出来，但线性同余由于算法简单，计算性能高效而又能满足很大一部分一般需求，依然是大部分编程语言 rand() 函数的默认实现方式。从公式可知这些随机数并不是真正的随机，总是会在 c 的范围内循环出现。当

1
2
3

b 和 c 互素
a-1 可被所有 c 的质因数整除
如果 c 是 4 的整数倍，则 a-1 也是 4 的整数倍

时，输出序列的周期为 c。只要保证 c 足够大，那么一般情况下是不会遇到周期性重复的。

事实上 a=1103515245, b=12345, c=2³¹ 正是 C 语言标准函数 rand() 所使用的几个常数。rand() 函数包含于 stdlib.h 头文件库中。

种子

从算法可知，假如 X₀ 不变，那么每一次执行程序，得到的“随机数据”其实都是一样的。执行两遍程序，得到完全样同的数据，重开一次游戏，NPC 的行为一模一样，这感觉其实并不怎么好。但从数学的角度上看，既然算法是一定的，那么每一步得到的数据也必然是确定的，如果初始值相同，那么后续的值也一定是相同的。甚至即使一个序列中断了，只要后续重新设定的种子值与中断前的最后一个值一致，那么这个序列就可以原样继续下去。

换个角度看，只要用不同的初始值，我们就能得到不同的结果。

这一初始值，被称为算法的『种子』(Seed)。最常用的种子数据大概就是使用系统的当前时间了，这是一个简单易用，必然存在，而且还时时刻刻在变化的值。可以让每时每刻产生的随机序列都有所不同。稍复杂一些的有 CPU 当前温度，用户鼠标的移动轨迹，键盘的击键速度等，属于不可预测的 Seed。

『种子』这个词汇甚至不光是随机数据生成算法里有，加密解密算法、身份识别、图像算法等都有这一词汇的出现（当然下载界也有这个词）。对加密算法而言，种子数据往往是高度保密或者完全无法复现的了。前面说的鼠标键盘数据即属于此类。于是围绕种子值往往也会产生许多巧妙的奇思秒想与攻防破解，后文再述。

随机与伪随机

不光是线性同余，计算机里一切随机数生成方法实际上都是通过一定的算法生成的，区别只是在于算法复杂不复杂，种子的要求高不高，得出来的 结果能不能满足实际场景的需要。这些通过公式计算得到的“随机数”，有一个特定的名称『伪随机』(Pseudorandomness)。即，看起来像是随机的，实际却不是。但看起来随机往往就足够了。

在有些场景里，这种通过计算机生成的伪随机算法会变得无法符合真实需求。

大规模的理化生模拟实验，伪随机算法在统计上的瑕疵可能会影响到模拟实验的结果数据。

——由于实验可能会用到海量的随机数据，部分伪随机算法的规律性或者其它统计上的瑕疵正好撞上实验的检查项，就会导致实验结果的异常。
程序员开年会，了解了随机数原理的程序员们纷纷表示不能被一个确定的算法影响了自己的『强运』。

——由于对年会奖品抽奖程序的不满导致年会现场变成 Code Review 大会的事情简直随处可闻。
赌场这种胜负直接关系到利益的地方

——关于伪随机算法缺陷导致巨额损失的情况后文细讲。
涉及到窃听与加密、远程控制肉机等可能造成反复利用的情况

——往往破解出一种加密方法，就可以进入大量的服务器，产生巨大的利益。

这时人们会更倾向于使用常识中认为的『真随机数』，例如放射性衰变、电子设备的热噪音、宇宙射线的触发时间等等。比如专门提供这类服务的 random.org 网站，声称是通过测量大气噪音(Atmospheric Noise)获得的随机数据。相比于受到算法限制的数据，毕竟这些数据感觉更“随机”一些。

当然，使用环境数据，则会受到测量传感器采样率的限制，数据的生成速度会受到影响。同时，很多自然环境数据也是连续渐变，或者服从一些确定的分布，随机性可能没有预想的高。比如 CPU 温度之类，在一定时间内的变化总是一条较为连续平滑的曲线。

所以更务实的办法是混用两种情况，即使用一套设计良好的随机数生成算法，了解算法的适用场景，避开算法缺陷，同时使用环境数据作为 Seed。初始值『真随机』后，后续尽管是伪随机但也拥有了更大的不可预测性，在大量重复实验中会表现出来更多的随机性，也就有了更广泛的使用场景。

“更随机”与“不那么随机”

对『随机程度』概念的理解多少有点凭感觉。尽管数学上对随机和随机程度是有严格定义的，但引用《信息简史》里提及的，香农提出的例子，大概更容易让人理解『随机程度』的意思：

·零阶近似一一完全随机的字符，其中不存在结构或依赖：
XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD
QPAAMKBZAACIBZLHJQD.

·一阶近似一一每个字符与其他字符不存在依赖关系，各自的出现频率取在英语中的出现频率：字母 e 和 t 出现得较多，而 z 和 j 较少，且单词长度看起来也较接近现实。
OCRO HLI RGWR NIMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.

·二阶近似一一不仅单个字母，双字母组合的出现频率也符合英语的情况。
(香农从密码破解者所用的表格中，找到了所需的统计数据。英语中最常出现的双字母组合是 th ，大致每千个单词出现 168 次，紧跟其后的是 he, an, re, 和 er 还有相当数量的双字母组合的出现频率为零。）
ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN DILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.

三阶近似一一三字母组合也符合英语的情况。
IN NO 1ST LAT HEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.

一阶单词近似
REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE

二阶单词近似一一双单词组合以英语中期望的频率出现，所以不会出现上例中 “A IN” 或 “TO OF” 的情况。
THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED

衡量随机性的方法就是香农同学提出的信息熵概念。在这里没有必要展开论述计算方法，我们使用另一个例子来简单说明随机程度：

这是一个来自知乎的巧妙方法，尽管局限性很大，但却一目了然：

random

对于通过算法生成的随机数序列而言，在整个序列中多少会存在一定程度的『局部结构』。『结构』的存在和反复出现，就表明这一序列的随机程度较差。结构越多越密，随机度越差。上面两个例子都展示了这种『结构』的存在。结构是可以预测的，可预测的越多，随机性就越少。赌徒们大概更容易理解这点吧。

生成方法与评价方法

线性同余法

线性同余法的公式非常简单，如果已知了足够长的结果序列以后，三个参数 a, b, c 也很容易反推出来。从数学上讲，任何一个可以被计算机运行的算法都必然有有限大的取值范围，既然范围有限，到最后必然会出现周期性循环。尽管如此，2³¹（大约 21 亿）的循环周期也小了一点。尽管没人会去打 21 亿只地鼠，但是 21 亿粒子碰撞，21 亿次装备掉落等等都是很有可能出现的。线性同余法的优点在于高效简洁易于实现，能满足常规需求，但人们还是需要更复杂更随机的算法。

Mersenne Twister

维基百科上有比较详细的论述。它的循环周期为 2¹⁹⁹³⁷ − 1，这是个梅森数所以才叫“梅森旋转”，和梅森本人大概是没啥关系。算法优点一是循环周期大，二是可以通过一些比较严苛的随机数测试，三是可以实现 1 ≤ k ≤ 623 范围内的 32 位精度 k-分布。

缺点一是速度较慢，但在现有的计算机性能下常规运算不是太大问题。二是在一些特定的初始值下，输出的序列会有大量相似模式。也就是会出现初始值相似而输出序列大量相似的情况，这个比较要命。另外，它通不过 TestU01 等少数随机测试。

Multiply with carry
MWC 是 George Marsaglia 提出的方法，优点在于速度快周期特别大，大约有 2⁶⁰ 到 2^2000000。缺点维基上没写，我猜测大概是结构较为明显，不适合的场景较多吧。OpenCV 使用了 MWC 作为随机数生成器，在图像领域，速度和周期确实是最重要的，相比之下，结构导致的缺陷并不重要且容易规避。

其它
维基百科上有专门的目录页提到了伪随机数生成器：https://en.wikipedia.org/wiki/Category:Pseudorandom_number_generators，而很显然这并不是全部的随机数生成程序。每一种伪随机算法都有自己的优点和缺点，适用于不同的场景。在一些简单场景下，设计人员也会使用更简化的，可以通过互质齿轮组机械结构实现的随机，比如：

98aed764834fb9165ced3945b6bc87b2_b

算法评价

同时，当然也有各种针对伪随机数测试方法，去检验生成数据的质量（即随机性如何）。原理基本都是评测生成的序列是否符合必要的复杂性要求。这与无损压缩算法反而有某种异曲同工之处，毕竟压缩算法的目的就是寻找规律模式并且使用更短的片段去代替它。几乎所有的随机序列测试都是基于假设检验、广义傅立叶变换和复杂性测试，对一个已经生成的伪随机数序列进行检测，寻找模式，并评测结果。

最简单的理解，如果你用 int(rand(0,255)) 一百万次生成了一个 .bin 文件，扔进 Winzip 里，结果体积压缩了一半，那么这个随机数生成算法就是非常不合格的。这跟上面的点阵图方式很相似。

顺便附上还是从知乎同一问题下抄来的四原则：

K1——相同序列的概率非常低
K2——符合统计学的平均性，比如所有数字出现概率应该相同，卡方检验应该能通过，超长游程长度概略应该非常小，自相关应该只有一个尖峰，任何长度的同一数字之后别的数字出现概率应该仍然是相等的等等
K3——不应该能够从一段序列猜测出随机数发生器的工作状态或者下一个随机数
K4——不应该从随机数发生器的状态能猜测出随机数发生器以前的工作状态

作者：DD YY
链接：https://www.zhihu.com/question/20222653/answer/16482344
来源：知乎

说实话这四条只是原则，并不是任何一个实测的测试方法。单一的测试方法也无法涵盖各种可能性，所以一些比较有名的测试，Diehard Test、TestU01 等实际上都是测试包，包含了多种不同的方法，尽可能覆盖测试的方方面面。

回到游戏

计算机程序大部分都服务于确定的目的，不会有随机的成分存在。查字典不可能随机给解释，打字不可能随机出字，做帐目不可能随机变计算结果。那么什么地方需要随机？最常见的也就是游戏了，包括电子赌博。所以再回来说说游戏中的随机。

『乱步』

圆桌武士(Knight of the Round) 是个当年非常受欢迎的街机游戏，应该也是不少人的童年回忆。

knights001

这款游戏后来被有心人研究出来被发现者命名为『乱步』的方法，类似以下这些规则：

1.红色小兵（不戴头盔的，血少）
a.砍开箱子出 800 分宝箱，他在地上滚动的时候，砍开 800 分，出魔杖。
b.屏幕上如果有两个桶，先不开桶，等他在地上滚的时候，放血放死他，然后开另一个桶，再开 800 分的桶，再开 800 分，出魔杖。
2.绿色小兵（戴头盔的）
a.先吸引他跑动(不攻击)，如果他马上又跑动攻击的话，出刀时放血放倒但不要放死他，马上去开箱子。等他站起来踹气的时候，开 400 分或蔬菜盘，出地震法球(这种方法不能出杖，up)。
b.在他在地上滚动时，放血放死他，然后开一个箱子，开里面的分或血，再开 800 箱子，开 800 分，出魔杖。
3.胖子(Fatman)
a.走 C 步时( C 形状的步子，步子很小也很快，就那么一下)，放血放倒他，马上开箱子，在他起来踹气时开 800 分，出魔杖。
b.站在他前方等他冲跑过来攻击你，他冲的时候你马上站在他斜下的方向，他如果走向下走一步（只是 1 步），放血放死他，然后开两个箱子，再砍 800 分，出魔杖。
4.大剑(Swordman)
a.同样是观察它走 C 步，放血放倒它，马上砍 800 箱子，等它站起来就开 800 分，出魔杖。
…………

乱步的实质就是随机数规律被人掌握了。

受限于街机主板不高的性能，游戏开发使用了比较简单的一个随机数发生器，实际的重复周期很小。同时还将宝物掉落、敌兵行动、主角行动等一系列需要随机的行为，全放在同一个随机数序列中。每一个需要随机的行为，都让这个序列往后走一格，一轮序列走完再从头开始第二轮。

也是因此，玩家可以通过反复的的跳跃、放血大招等动作，来『快进』掉随机数序列中的若干位数字，到需要的位置，再劈砍宝箱，以获得指定的需要的宝物。如下图，当随机序列进行到 03 时，游戏中某个小兵根据该数字进行了冲锋动作，使用掉 03 这个数值。序列进行到 1C，被玩家用连续两次跳跃消耗掉两个随机数，使得随机序列当前值变为 0F。而 0F 对应于掉宝则为『魔杖』。

即，用户根据一些游戏内的特别现象，通过自己的操作控制了掉宝内容。

ranbu

可是主角行动是个受玩家操控的行为，并不是一个需要随机的东西，为什么还会在随机序列中并影响到掉宝结果？

有两个原因。一是为了让画面更富有表现力，游戏主角的动作会有多种画面表现。同样是跳，可以表现为前空翻跳，直立跳。同样是转身，一种先转头，一种先迈步，等等。而另一个原因仅仅是为了让序列更随机。没错，就像前文写过的那样，使用键盘击键、鼠标轨迹等算法外部的影响因素，可以让破解者更难以发现规律。当然，也可能两个原因都有。

我猜测圆桌武士这个游戏就是第二类情况。由于玩家行动，尤其是多人游戏，多位玩家同时行动时，玩家行为的不可预测性甚至比有限机能下内部的随机数发生器更有效，这可以避免简单地被玩家发现『如果做了 A 接下来一定是 B』的规律，也避免了敌人行动永远一致的囧境。事实上在它的游戏生命周期内，几乎是整个街机的商业周期内，都运作得很好。直到电脑模拟器时代，才由几个多年孜孜不倦研究的玩家发现并完善了这份随机表。

看起来，似乎让玩家动作可以影响随机序列是个坏主意，若玩家掌握规律，岂不是就可以通过自身动作来影响游戏掉宝等结果了么？但事实并非如此。『并非如此』不是说不影响结果，而是说在玩家动作里设置锚点以影响随机数序列，进而影响掉宝，并不是一个坏主意。

因为在有限的机能和简单的算法下，规律始终是容易被发现的（参考第一节的打地鼠）。假如没有玩家动作影响，规律性的掉宝会让玩家非常容易就总结出形如『第二个箱子不打则第五个箱子必出 +100% 生命大血包』的结论，这会极大缩短游戏寿命。而将玩家动作引入后，即使是同一个玩家玩同一个游戏，两次行动也往往并不一致，于是相同游戏进展也就可能掉出各种不同的宝物了。另外，因为玩家并不清楚哪些动作被埋入了影响因子，因此也很难一开始就针对性的调整动作来尝试『探宝』。

在引入玩家动作影响因素以后，什么时候规律才能被发现呢？一是某位玩家熟练到全套过关动作几乎一致时，他才容易发现掉宝似乎也表现出了某种规律性，从而开始探索对掉宝率的控制。这大概就是上面乱步表的由来。另一种是在游戏起始阶段，玩家的行为并不复杂，正好某个掉率也设置较高容易被随机到时，大量玩家的集体行为容易让规律暴露出来。一个第二关开头的水果盘砍出 +2 生命宝物的古老秘籍大概就是这么来的。

而随着硬件性能的不断提升，这种要依靠玩家行为来产生游戏不确定性的情况越来越少了。该方法毕竟是把双刃剑，在可以不用的时候就不必使用了。现在使用任何语言，都有足够多现成的算法可用，并且硬件性能也足以支撑大量的计算了。唯一还需要讲究的大概就是种子值了。

种子对齐

种子和密码正好相反，密码要求前后不变以供核对，而种子则最好每次都不同，因为相同的种子必然产生相同的『随机』序列。如果种子是预先定义好的固定值，服务器每次重启后跑出来的都是相同的序列，开出一样的奖，显然是不合适的。

相同的种子必然产生相同的序列。

发现什么了么？

这意味着，假如你知道某个随机算法的种子，你就拥有了预测能力，精确地知道每一次开奖的结果，就可以批量地安全地赢走电子赌博网站里所有的奖金。甚至就算你不知道种子，发现每次是相同的序列后，也会拿个纸笔记下来吧。在这层意义上，种子值和密码又有了相通之处——不能为人所知。

好办，只要每次种子值都不一样连程序作者自己都不知道不就行了？

——不是这样的。

前文提到最常用的随机种子是时间戳。可是你服务器总要维护重启吧，甚至可能还有自动重启。假如你在凌晨 3:05 重启，直到 3:15 重新开始赌博抽奖。我就知道你这台服务器的赌博程序一定是在 3:05-3:15 之间启动的。假如你真的使用了时间戳作为种子，也一定是在这 10 分种里取的。10 分种，600 秒， 60 万毫秒。大不了把这 60 万个时间全部作为种子挨个跑一遍看哪个能对上你重启后出产的随机序列就好了。能对上的那个序列，对应的时间戳就是你的种子。然后就是原本计划的那样，安全批量地赢走网站里的所有奖金。

好吧，不用时间戳了，使用 CPU 温度吧。同样也不安全，实际运行的机房计算机的 CPU 温度，我们就算它可能是 50℃ ~ 90℃ 吧，传感器温度有限，就算三位小数，那也就是四万种可能情况而已，挨个跑一遍就好了。奖金就到手了。

要知道，计算机不依赖第三方，内部可以提供的变化数据其实就那么几种，而随机算法也只有那么几种。圈定了一个大致的范围以后，『大不了全跑一遍』来反推种子值，其实是非常有效的。相同的随机算法，相同的种子，必然产生相同的序列，于是你就获得了神的预言能力。

那么假如使用外部数据呢，比如前文提到的 random.org。也可以通过 DNS 解析到假网站，提供自己预先准备好的『毒种子』进行攻击。尽管这个方法在 random.org 启用了 SSL 证书以后变得麻烦一些了，但还有更简单的攻击办法，就是让服务器无法访问该网站，直接让你拿不到网站提供的随机种子。

网站总是要经营的，如果服务器一直无法正常运作，损失不比奖金被赢走小。既然种子对齐的目的是赢走奖金，那么当破解难度大到一定程度时，各种攻击勒索就变成收益更高的方式了。

话题似乎跑远了，但其实本文讨论的核心是『计算机随机，够用就好』。当破解的难度大于勒索的成本，基本也就说明在随机算法这一层面，确实够用了。

感觉的随机

『够用』往往还有另一层意思。

我们还是从掉宝率开始，假如一样极品宝物，比如屠龙宝刀 ~~点击就送~~ 在游戏内的掉率为 1%，这意味着大约杀 100 次 boss 会掉一把。作为一个通过反复击杀 boss 获取的装备，掉率 1% 本就是定位于每个人都能获取的高级装备。只要统计一下整个网游的怪物击杀量，就知道那是多么大一个天文数字.如果真要定位为全服稀有，那么掉率必然是几乎接近于零的。

既然是普及型稀有装备，假如一个玩家每天可以杀 boss 一次，那么大约 100 天期望时间也就是三个月左右会掉一把，这也比较符合网游的更新周期。假如有 10 万人玩游戏，那么平均每天大约有 1000 人会获得该武器，通过游戏社区也会刺激其它玩家的游戏动力。随着游戏进程玩家的装备变好，击杀 boss 的速度越来越快，在版本的最后阶段变成例行公事一般，也可以满足游戏运营方对上线率存留率方面的要求。

如果只计算粗放数据，以上一切看起来都很美好。但事实是：

大约有 10,0000 * (1-1%)¹⁰⁰ = 36603 名玩家在三个月以后依然没有获得宝刀；
大约有 10,0000 * (1-1%)¹⁵⁰ = 22145 名玩家在五个月以后依然没有获得宝刀；
大约有 10,0000 * (1-1%)²⁴⁰ = 8963 名玩家在八个月以后依然没有获得宝刀；
大约有 10,0000 * (1-1%)³⁰⁰ = 4904 名玩家在十个月以后依然没有获得宝刀；
大约有 10,0000 * (1-1%)³⁶⁵ = 2552 名玩家在一整年以后依然没有获得宝刀；

对于这几千名玩家而言，怀疑游戏开发商虚假承诺数据做假，完全合情合理。在没有附加条件的 1% 随机掉率下，第一天拿到宝物的就有 1000 名玩家，而运气不好刷一整年都不出的有 2552 名玩家。如果我们考虑得更实际一点，不是每个人都天天刷游戏，实际都是新版本刚开火热一点，后面就是有时间上线没时间算了。那我们假设第一周七天天天刷，第一个月每周刷三次，之后丧失新鲜感失望情绪蔓延，每周只上线一次。则：

大约有 10,0000 * (1- 99%⁷) = 6793 名玩家在第一周拥有了宝刀，一人多刀没用只算一把，每百人有 6.7 把。
大约有 10,0000 * (1- 99%¹⁶) = 14854 名玩家在第一个月拥有了宝刀，每百人里有 14.8 把宝刀，三周涨了 8.1。
大约有 10,0000 * (1- 99%²⁴) = 21432 名玩家在三个月内有了宝刀，每百人里有 21.4 把宝刀，两月涨了 6.6。
大约有 10,0000 * (1- 99%⁶⁴) = 47440 名玩家在一年内有了宝刀，每百人里有 47.4 把宝刀，九月涨了 28.0。

总比例造成未获得者的不快感蔓延，由于击杀频率的减少也导致存量增长下降。游戏根本撑不到一年。

无标题

假如我们可以付费买 boss 复活再次击杀获得额外一次掉宝机会——就是花钱开宝箱，则需要 chance = 1146 才能使得 10,0000 * (1-1%)^chance < 1，也就是说运气最差的哥们需要开一千多个箱才能获得这个 1% 几率的宝物。对他而言，这根本就是千分之一的几率。

不患寡而患不均。不加限制条件的纯随机，对那些一次就出的幸运儿很不错，但整体而言其实给玩家的体验并不怎么好。如果有 10% 的几率，玩家可以容忍 20 次甚至 30 次不出，但如果 1% 的几率，能容忍 200 次的都是凤毛麟角。而前者 20 次不出的几率是 12.15%，后者 200 次不出的几率为 13.40%。越是低的掉率，无限制纯随机给玩家的体验就更不好。究其原因，在于人的感觉与概率的实际表现之间存在差异。人人都不觉得自己是最差的那个倒霉蛋，但总有人会填上这个位置。

有两种截然不同的办法去解决这个问题。

一种是尽量去掉这个位置，比如『积累胜率』。当玩家在一次抽奖不中后，略微提升下一次的中奖几率，如若继续不中，则继续提升，直到 100% 必中为止。例如初始 1% 每次提升 1%，那么再倒霉的人在第 100 次开奖时，面对 100% 的中奖几率也该中了。这样的 100 次才中的倒霉蛋，每十万人里大概会有 9.33×10 ^-38 人…… 嗯，十万人中最倒霉的倒霉蛋大约也会在第 45-50 次开奖时得到顶级装备，到不了 100 次。魔兽世界里 “幸运币” 的积累机制就是这么做的。

另一种是分割并加大随机性，让这个倒霉蛋的位置被切分到几乎不可感知。暗黑破坏神 3 里的装备随机属性和随机掉落机制是这种方法的例子之一。对于暗黑 3 而言，一个人物身上有 13 件装备位置，每个位置都有十几种可能的掉落，但最合适的只有一种。而对于每一件特定装备，又是在十几种不同的属性列表中随机获得四到六种属性，每种属性又是在既定的数值上下限区间随机确定某个值。同时对于一个玩家而言，正常游戏在一小时内即可获得十来二十甚至更多的装备。

尽管绝大部分装备都免不了被嫌弃，但通过这种多装备+多掉落+极大随机的模式，成功地把倒霉蛋的感觉切分到几乎不可感知了。玩家依然可以在论坛上看见别人的极品装备，但对于自己而言，身上也往往会有几件装备是过得去，勉强能让自己满意的，这已经能极大抚慰倒霉蛋们的感受了。

所以有时候，我们反而需要减少一定程度的随机性，使得它感觉起来更随机。

『We’re making it less random to make it feel more random.』

英文那句不是我说的，是乔布斯说的。

在一个既定音乐列表随机播放时，如果是不加限制的随机，经常会出现同一首曲目连续播放两次甚至更多次的情形。这事实上是很正常的事情，如果每次切歌都是从同一个长度为 n 的列表里选取一首，就意味着每次都有 1/n 的几率选到和上一首相同的歌，于是就重复播放了。直接从播放清单移除听过的歌曲可以解决问题，但就和打乱列表的顺序播放没什么区别了。

根据一些访谈所述，苹果 iPod 的随机播放程序是将不同歌手、不同曲风交错播放，让使用者感觉到每一首歌之间毫无关联，相当的“随机”。

所以你看，科学计算需要的随机，和游戏需要的随机，和播放器需要的随机，和自然界的随机，其实都各有不同。

算法服务于目的。

VMWare 安装 Ubuntu 的一些豆知识

发表于 2016-04-18 分类于命令行

1. Ubuntu Family Mini ISO

如果网络条件不错的话，安装虚拟机可以使用适用于 Ubuntu 全家族（Kubuntu、Lubuntu、Xubuntu、Edubuntu、Mythubuntu 等）的通用迷你 ISO。32 位或 64 位都有。

https://help.ubuntu.com/community/Installation/MinimalCD （32 位或 64 位）

这个 ISO 只有不到 40MB，在安装过程中会自动从网上下载需要的文件，并在某个步骤让用户选择桌面环境。本来 desktop 版 ISO 在安装时也会上网更新，所以这个 Mini ISO 能节约的时间还是不少的，体积小还易于本地保存。我的网络带宽上限速度大约是 2MB/s，apt 源实际速度大约是 1MB/s 安装完成费时和先用迅雷下完整 ISO 再安装再 update 差不多。顺便还能满足软件洁癖们。

其实就是 Tasksel 整合安装器

缺点也是有的，界面和 Server 版映像文件一样是纯英文，且有些步骤的默认选择是<No>，不能一路回车到底。所以得能看懂提示。安装步骤倒是和 desktop 版没区别，无非是语言地区、分区、用户名密码这几个选项。

2. 命令行安装 VMWare Tools

使用虚拟机下拉菜单的『安装 VMWare Tools』只会自动载入 VMTools 的 ISO 文件，需要自行解压 VMTools 安装包。

cd ~ --当前目录
sudo mkdir /mnt/cdrom --建立目录
sudo mount /dev/cdrom /mnt/cdrom --加载光盘内容到这个目录
tar -zxpf /mnt/cdrom/VMwareTools-*.tar.gz --解压到当前目录
cd vmware-tools-distrib --进入安装包目录
ls

Ubuntu 64-2016-04-18-15-58-27

可以看到 vmware tools 安装包目录下有 vmware-install.pl，有时还有 vmware-install.real.pl。但由于 vmware tools 需要 gcc 来重新编译，所以在安装 vmware tools 前需要先确保 gcc 已经安装：

1 2	sudo apt-get update sudo apt-get install build-essential

然后再安装 vmware tools

1	sudo ./vmware-install.real.pl

第一个问题问，现在有 open-vm-tools 了，是否还要用这个老的，默认是 no，选 yes。我试用了一下 open-vm-tools，缺陷依然太多，没法用。

然后一路回车到结束。安装完成时提示你，如果是图形界面的话，需要手动启动 /usr/bin/vmware-user，然后注销重登录。其实这步作用不大，系统关机下次再开效果是一样的。

Ubuntu 64-2016-04-18-16-37-35

如果之前没有安装 gcc，有时就会出现以下情况：

Ubuntu 64-2016-04-18-15-59-02 gcc 路径为空，无限循环无法往下

这时需要用 Ctrl+C 中断，安装 gcc 后重新安装 vmware tools

3. 安装 Google Chrome 不用翻墙

因为下载浏览器的实际域是 dl.google.com，没有被墙。（北京联通）当然这个域名用浏览器是打不开的，因为它只提供下载，但知道路径的话就可以用 wget 直接下载了。

wget https://dl.google.com/linux/direct/google-chrome-stable_current_amd64.deb --64位
wget https://dl.google.com/linux/direct/google-chrome-stable_current_i386.deb --32位
sudo dpkg -i google-chrome*.deb
sudo apt-get install -f

4. 压缩虚拟磁盘，减少宿主机磁盘占用。

虚拟机用得时间长了，虚拟硬盘文件会变大。VMware 提供了清理磁盘功能释放空间，在 Windows 下很正常，但在 linux 下提供的 vmware-toolbox-cmd 有 bug，并不能起到压缩作用，需要先用零数据覆盖磁盘，再使用 vmware tool 的磁盘清理功能。

1
2
3

sudo dd if=/dev/zero of=zerowipe bs=1024x1024
sudo rm zerowipe
sudo vmware-toolbox-cmd disk shrinkonly

检查语言支持并补充安装，特别是使用 Minimal CD 在线安装的系统。
安装语言选择控制面板：

1	sudo apt-get install language-selector-gnome

检查缺失语言：

1	sudo apt install $(check-language-support)

5. 减少 /var/log 体积

1	sudo journalctl --vacuum-time=1d # 普通用户不看日志。要延长就改成 7d 或 30d

HeidiSQL 的 SSH Tunnel 连接方式

发表于 2016-04-09 分类于软件使用

heidisql_logo

HeidiSQL 是个挺好用的 Windows 下轻量级 MySQL / Ms SQL / PostgreSQL 客户端。官网地址：http://www.heidisql.com/ 。功能不写了，反正都差不多。它提供的 SSH Tunnel 连接方式这里记一笔备忘。

HeidiSQL 的 SSH Tunnel 连接方式其实就是先 SSH 连接到目标主机，再以目标主机的身份，连接到 MySQL 服务器。这有两种情况，一种是出于安全因素，数据库只允许本机或者有限几个 IP 访问，另一种是 MySQL 服务器和 SSH 目标主机在同一局域网内，而该局域网的多台机器只有 SSH 主机可以被外界直接连接。总之就是 MySQL 机无法被直接连接到，要通过 SSH 主机中转。

未命名

在中小网站中，数据库只允许 localhost / 127.0.0.1 连接是很常规的安全配置。但往往又存在需要后台操作数据的时候，于是有时会搭配 phpMyAdmin 这样的网页端方案，或者就是用 SSH Tunnel 这样的变通远程连接。

所以 HeidiSQL 的连接设置在选择网络类型为『MySQL (SSH Tunnel)』时也有所不同，除多出一个『SSH 隧道』选项页外，填写的参数也有变化。在 SSH Tunnel 模式下，设置页填写的是 SSH 主机如何连接到 MySQL 服务器.

无标题 SSH 主机（不是本机）如何连接到数据库，很多中小网站的数据库只允许本地访问，则这里应当填写 127.0.0.1

而 SSH 隧道页填写的则是 本机如何连接到 SSH 主机，由于 SSH Tunnel 依赖 Putty 软件包中的 Plink.exe 程序，所以需要指定 plink.exe 的位置，或者索性复制一个到 HeidiSQL 同目录下。同时，SSH 除用户名密码连接方式外，还有公私钥系统的连接方式，需要通过 Putty 软件包的 puttygen.exe 将私钥文件转成 Putty 专用的 .ppk 格式。

无标题本机如何连接到 SSH 主机

填写连接到 SSH 主机的用户名、密码，如果使用私钥文件的话，密码可以为空。

保存以后配置就完成了。并不需要去配置 Putty.exe 的任何内容。不知道为什么百度搜出来的好多博客都花了不少篇幅去写怎么配置 Putty，略扯淡。配置 Putty 与使用 HeidiSQL 并无直接关系。

一句话总结：

在普通模式下设置页填写的是运行 Heidi 的机器如何连接到目标 MySQL 服务器，而在 SSH Tunnel 模式下，需要先从运行 Heidi 的机器连接到 SSH 主机，再以 SSH 主机的身份连接到数据库服务器。

AWS Ubuntu 安装 PPTP VPN

发表于 2016-04-08 分类于命令行

AWS 现在提供新注册帐号一年免费服务，1台1G内存30G硬盘的 VPS，每月 15G 流量，可以用来架 VPS 或者博客主机，虽然流量不大，但日韩机房的速度很不错。

首先需要在主机配置面板的安全设置中，把入口流量防火墙的 1723 端口打开。否则配置正确也会被防火墙挡上。

安装 PPTPD 服务。

1 2	sudo apt-get update sudo apt-get install pptpd

编辑 pptpd.conf 配置文件。
1
sudo vim /etc/pptpd.conf

#其它的不用动，注意 option、localip、remoteip 三项即可
option /etc/ppp/pptpd-options
localip 192.168.9.1
remoteip 192.168.9.11-30

编辑 pptpd-options 配置文件。
1
sudo vim /etc/ppp/pptpd-options

#refuse,require 五项通常都是默认的
refuse-pap
refuse-chap
refuse-mschap
require-mschap-v2
require-mppe-128
#添加 Google DNS
ms-dns 8.8.8.8
ms-dns 8.8.4.4

编辑 chap-secrets 配置文件，添加 VPN 用户名和密码。
1
sudo vim /etc/ppp/chan-secrets

# Secrets for authentication using CHAP
# clientserver secret IP addresses
# 从前到后四项分别是用户名、PPTP/L2TP 选择、密码、允许连到该 VPN 的 IP 段，用空格或者 tab 分隔，用 * 表示通配
kaikai * 123456 *

打开 IP 转发
1
sudo vim /etc/sysctl.conf

1	net.ipv4.ip_forward = 1

需要重启服务：

1	sudo sysctl -p

添加 iptables 规则，这句根据服务商的不同会有不同，本句适用于 AWS
1
sudo siptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

并添加到启动项中，以便服务器意外重启后继续正常工作：

1	sudo vim /etc/rc.local

1 2	iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE exit 0

配置完成，重启 pptpd 服务
1
sudo service pptpd restart

3 逗还是 4 逗？

发表于 2016-03-15 分类于唠唠叨叨

为方便位数较长的数字，我们经常会加上一些逗号或者故意在若干位数之间加大间隙以方便阅读。比如：

8326cffc1e178a82fd70f340f303738da877e886 100 万亿元津巴布韦币

这里的 100 万亿尽管没有直接加逗号『,』，但在每三位数字之间加大了间隙，所以如果学过英语，就可以比较方便地数出 Thousand, Million, Billion, Trillion 四级单位，所以这张钱是 One hundred trillion dollars。但这是使用英语度量衡的国家，他们的语言以千为一级，所以以 3 位一级标比较方便，而中文是以 4 位一级的，这意味着在数数量级单位时，我们的思维变成了『千，百万，十亿，万亿』，于是得到『一百万亿』这个表达。

在汉语语系下，这个划分并不方便。直观的显然应该是 4 位一级，也就是『万，亿，万亿，兆，…… 』下去。比如：

三位一级：100,000,000,000,000

四位一级：100,0000,0000,0000

看起来显然是 4 位一级更直观。

接下来又到了是民族还是世界的争论，我认为在这种鸡毛蒜皮的『3 逗还是 4 逗』问题上，以下的见解是可以达成一致的：

这个标记本来就是辅助阅读用的小改进。除了它应当承担的用途外，不承担别的用途。
无论 3 逗还是 4 逗，即使不熟悉的人，阅读起来也并不会造成障碍。本来这就是个辅助阅读的事情，辅助不了就当它不存在。
对于相应语言体系下的人，只有熟悉的分法才有较好的辅助作用。

所以我的结论是，如果作者和可以预知到的读者群体，都更熟悉 4 逗的话，那么相应的文字应该以 4 逗优先。反之 3 逗优先。假如某种文化是 5 位一个数量级的话，他们的出版物显然应该以 5 逗优先。如果作者与读者群的习惯不一致并且可以预期这种不一致的话，我觉得应该以读者优先。如果不可预知，那就是看作者个人习惯了。

于是，在我的博客和我可能的译作（英译中）的相关文字里，我都会尽量以 4 位为大数划分数量级。而若写的是英文博客的话，则会以 3 位划分。

说白了这就是个习惯问题，中文环境中并不需要强求以 3 位划分为准，4 位更习惯就用 4 位吧。

据我所知日语也是 4 位一级单位的，那么想必中国周边受中华文化影响的应该都是 4 位，大概。

Excel 计算缺陷与大数计算

发表于 2016-03-14 分类于软件使用

Excel 很多时候可以当作一个简易的数学计算程序，代替 Mathematica 或者 Matlab 之类的专业软件进行一些不算太复杂的数值运算。但 Excel 的数据处理存在很多弱项，在遇到时需要相应作一些处理。

问题一：有效位数大约只有 15-16 位，更多的位数只会用 0 填充了。

精确计算的 2ⁿ 的尾数不会是 0，始终是 2→4→8→6→2…… 的循环，但从截图上可以看到，Excel 在计算 2⁵⁰ 时，就遇到了有效位数问题，使得末尾出现了数字 0。

关于问题一的应对：

从例子中可以看到，Excel 提供了 15 位的精度，这意味在在『千万亿』这个级别上 Excel 依然可以进行精确的计算。相当于以小数点后 4 位精度，即 0.0001 元 = 0.01 分的精度下，处理九千亿人民币以下的财务数据。处理全国 GDP 的数据也可以精确到分，以米为精度可以让光跑一个月，以毫秒为精度覆盖三万多年。

但是如果你真觉得不够，就需要自己用公式实现进位，使用多个单元格作为『数字段』，来确保每个单元格内的数字长度不超过 15 位。

以 2ⁿ为例，其计算由两部分组成：

最右一列公式为：

Z1=2
Z2=TEXT(RIGHT(Z1*2,12),"000000000000")
Z3=TEXT(RIGHT(Z2*2,12),"000000000000")
Z4=TEXT(RIGHT(Z3*2,12),"000000000000")
……

其中，Right 函数保证每个单元格只取结果的最右 12 位，让精度始终符合 15 位上限的要求。而 Text() 函数则保证当截取 12 位数字时，不会将原来在中间位置的 0 因为截取而成为首位 0 消失掉。例如，2⁶³ = 461,1686,0092,1369,3952，当截取 12 位时，会获得 0092,1369,3952，如果不通过 Text() 函数保存首位的 0，则最后合并回去时就会产生错误。

左边每一列的公式均为：

X2=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Y1*2,LEN(Y1*2)-12)),0),12),"000000000000"); Y2=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Z1*2,LEN(Z1*2)-12)),0),12),"000000000000")
X3=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Y2*2,LEN(Y2*2)-12)),0),12),"000000000000"); Y3=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Z2*2,LEN(Z2*2)-12)),0),12),"000000000000")
X4=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Y3*2,LEN(Y3*2)-12)),0),12),"000000000000"); Y4=TEXT(RIGHT(Y1*2+IFERROR(VALUE(LEFT(Z3*2,LEN(Z3*2)-12)),0),12),"000000000000")
                                                                              ……;                                                                               ……

这个公式同时适用于左边任意多列，使得只要电脑性能过关，尽可用尽 Excel 的所有列（一共 16384 列）。

公式略复杂，以 Y2 为例：

1	Y2=TEXT(RIGHT(Y12+IFERROR(VALUE(LEFT(Z12,LEN(Z1*2)-12)),0),12),"000000000000")

最外层 Text() 依然是为了保留首位 0。Value(Left()) 用于提取右边列的进位数字，即当前列的右侧列如果出现超过 12 位的数字时，则截取头部进到本列。Iferror() 用于检测是否进位。将进位数字和本列上一行数据乘二的结果相加后，再检测是否本列也多于 12 位，如果多则截取。公式引用关系如下：

I9N46D5M6%U}E@8IXWXS8CU

使用类似思想，可以精确进行一次数值变化不超过 10¹⁴ 的大部分大数计算。需要注意的是，假如一次数值变化较大，则每单元格所能保留的位数就相应变小，不一定是 12 位了。

应对问题一的要点有二，一是自行实行截取与进位，二是利用 Text() 公式特性，保留截断后的首位 0 不丢失。我通常把这种处理办法称为『大数多列化处理』。

问题二：数值上限大约在 2¹⁰²⁴-1，由于有效位数限制，实际上限更小一点，大约在 2¹⁰²³+2¹⁰²²+……+2⁹⁷¹ ≈ 1.7977e308 左右。

这与问题一不同点在于，这个问题不关注精确展开，而更关注公式计算过程中的上限值。当然，使用问题一中的办法也能解决本问题中的部分情况，但对于更大的数字，例如用尽 Excel 所有列（16384 列）也写不下的数字，大约 10^16384*14 = 10²²⁹³⁷⁶，问题一中精确展开的解法就无能为力了。况且在实际展开中，在装满 Excel 前就早早会遇到内存和 CPU 瓶颈了。问题二的解法注重于在有限的计算资源下计算尽可能大的数字。

我们以计算 361 的阶乘为例，如果使用 Excel 公式直接输入 =Fact(361) 则只会得到一个 #NUM! 的结果。意即该计算的值或者计算过程中已经出现了超过 Excel 单元格所能容纳的最大值。

关于问题二的应对：

我们在 Excel 中准备三列数字，A 列为从 1-361 的展开。C1 公式为 =FLOOR.MATH(LOG10(A1))，B1 公式为 =A1/10^C1。

从 C2 起公式为：

C2=FLOOR.MATH(LOG10(B1*A2))
C3=FLOOR.MATH(LOG10(B2*A3))
C4=FLOOR.MATH(LOG10(B3*A4))
……

从 B2 起公式为：

1
2
3

B2=B1*A2/10^C2
B3=B2*A3/10^C3
B4=B3*A4/10^C4

于是形成如下形式：

![1~P8Q1T0%@[@S4J1CS4Y`U9](../attach/2016/03/1P8Q1T0@@S4J1CS4YU9.png)

即 B C 两列形成了类似科学计数法的 b × 10 ^c 的数列。但不同之处在于，C 列的所有值全部相加，才是整个计算过程的最终解，如图：

EXWL~KE6X(5_2I4BLEN}%E5

即：361! = B361 × 10 ^SUM(C1:C361) = 1.43792325888489 × 10⁷⁶⁸，和上一篇博客对照一下，结果还是很精确的。

仔细观察 B、C 两列数值，其实原理就是每当一个新的 A 乘进来，都对结果作一次科学计数法处理，形成 b × 10 ^c 结构，确保每一次都有 1<b<10，然后把乘方 c 扔在一边最后再相加。

这一解法的关键在于在计算的每一步都即时处理，避免单元格数字过大而『爆掉』。通过这种方法，Excel 的可计算数域范围从大约 10³⁰⁸ 变大到了大约 10^{1,0000,0000,0000,0000}，更大的数字则会产生 10 ~1000 倍甚至更大的误差。但如果对 C 列的数字再作问题一解法中的多列化处理，则可计算数上限大约会变成 10^{10²²⁹³⁴⁸} ，这里被迫用了幂的幂。这个数字相当大，并且实际不可能用到。早在这个极限之前，你的电脑内存估计就会挂掉。

当然，因为有 VBA，Excel 理论上也可以做复杂大数字计算，但考虑到学习成本和应用场景，不如学习 Mathematica 来得方便了。一般使用 Excel 做计算，都仅限于操作单元格和自带公式可以解决的问题。

……数零与进位

发表于 2016-03-14 分类于硬用数学

最近 AlphaGo 与李世石的人机围棋大赛很火，也蹦出一大波跳梁小丑。你会发现什么热点事件都少不了这种人，总是挡在路上污人视线，比如那个输入法王。我记得上次 SoloLens 它也跳出来大谈 Matrix 来着。

牢骚完毕，这次深夜短篇不是写围棋也不是写计算机的，只说数数，更严格的说，只是数『0』。比如：

围棋棋盘共有 19×19 个点，每个点有『无子』、『黑子』、『白子』三种可能性。不考虑无气提子等特殊情况，则一共有 3^361 种盘面。如果考虑到下子进程，则有 361! 种棋谱。

因为有围棋规则在，实际数字会小一些，但这不是本文重点。这两个数字分别是一个 173 位数和一个 769 位数：

1
2
3

3^361=17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603

361!=1437923258884890654832362511499863354754907538644755876127282765299227795534389618856841908003141196071413794434890585968383968233304321607713808837056557879669192486182709780035899021100579450107333050792627771722750412268086775281368850575265418120435021506234663026434426736326270927646433025577722695595343233942204301825548143785112222186834487969871267194205609533306413935710635197200721473378733826980308535104317420365367377988721756551345004129106165050615449626558110282424142840662705458556231015637528928999248573883166476871652120015362189137337137682618614562954409007743375894907714439917299937133680728459000034496420337066440853337001284286412654394495050773954560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

呼应本文标题的问题来了——这两个数字末尾各有多少个『0』？

你当然可以靠眼力劲儿去数，前者容易看出末尾没有 0，后者大概费些功夫能数出有 88 个 0。当然你也可以使用查找替换，数起来方便些。

但是如果没有事先把总数算出来，又如何数出一个数的末尾有多少个 0 呢？毕竟连乘 300 多次算个 700 多位的数字恐怕是更累的一件事情。能少算就少算点吧。

办法是有的，数质因素 5 就可以了。

要注意到，无论多少个数连乘，只有 2×5 才会在末尾添加一个 0。有人说 8×5 也会出 0，4×25 会出两个 0。但 8×5=40=2²x2x5，有两个 2 其实浪费掉了。而 4×25 = (2×5)²，本质上正好是两对 2×5 相乘，完全符合之前的设定。又因为在阶乘中，2 作为质因数的出现次数远远超过质因数 5 出的次数。每个偶数都能至少贡献一个质因素 2，而每个 5 个数字才能贡献一或若干个质因数 5。因此可得结论：

只要数清连乘中一共有多少个质因数 5，就知道最终数字末尾有多少个 0 了。

对于 3^361，显然一个质因数 5 都没有。所以末尾没有 0。

对于 361!，

每隔 5 个数字，可以提供一个 5。即 5, 10, 15, 20, 25, 30, ……, 360。一共 361 / 5 向下取整，有 72 个。
每隔 25 个数字，可以一次提供两个 5。即 25, 50, 75, ……。一共 361 / 25 向下取整，有 14 个。由于上一条已经重复计算一次，因此这里的 14 不必再翻倍了。
每隔 125 个数字，可以一次提供三个 5。即 125, 250。一共 361 / 125 向下取整，有 2 个。由于上一条已经重复计算一次，因此这里的 2 不必再翻倍了。

再上去是 625，直接超了。于是数 5 活动就此停止。

一共有 72+14+2=88，而 2 的数量肯定是足够的，于是会产生 88 组 2×5，即末尾有 88 个『0』。

这个方法可以广泛用于各类无聊的数 0 活动中，例如：

任取一个足够大的数字 N，比如 10¹⁰⁰ 即 1 googol，把小于 N 的所有素数乘起来，那么多素数的乘积的末尾有几个 0？

——答案是只有一个 0，算对了么？

那么第二个问题来了，为什么数 5 知 0？

答案是，这个和 10 进制有关。

仔细思考，『进制』的本义就是每满多少就 归 0 进位。换句话说，如果 要让末尾为 0，就必须不多不少，最末尾那些余量恰恰等于当前进制。这个『余量』不是严谨的用词，意会即可。在 10 进制里，你总要正好凑出 10 个或者 10 的倍数个，才能让末尾是 0。在 8 进制里就要凑 8 的倍数个让末尾是 0。16 进制凑 16，N 进制凑 N。

所以归根结底，要让若干个数连乘得到末尾零，就是看能凑出几份当前进制。10 进制就是要凑 2×5，8 进制要凑 2x2x2，每三份质因数 2 会多一位尾 0，只看 2，别的都没用。

既然 10 进制下，10 的唯一质因数分解就是 2×5，而 2 又远多于 5，所以数 5 知 0 就变成了最简单的办法。

理解了这些，下面这些问题也不难回答了：

3³⁶¹在 3 进制下，末尾有几个 0？

答案是 361 个 0。这个问题等效于 10 进制下 10³⁶¹末尾有几个 0，等效于 N 进制下 N³⁶¹末尾有几个 0。——都是361个。

2¹⁰²⁴在 16 进制下，末尾有几个 0？

答案是 256 个。因为 16 = 2⁴，1024 / 4 = 256。

最后一个问题：

3¹⁰²⁴在 2 进制下，末尾有几个 0？

HTML5 <audio> 粗考

发表于 2016-03-14 分类于前端新手菩萨保佑

HTML 5 提供的 <audio> 给了前端相当多的方便，不再需要 js 库和 swf 作为播放器。但是新带来的坑也是坑得我要死要活的。

这是 W3School 提供的一张简表：

Browser	MP3	Wav	Ogg
Internet Explorer	YES	NO	NO
Chrome	YES	YES	YES
Firefox	YES	YES	YES
Safari	YES	YES	NO
Opera	YES	YES	YES

信了你就掉坑了。

HTML5 的 <audio> 有着比看起来的大得多的坑。主要在于各浏览器的实现上有区别，自带的音频解码器各有不同，导致实际支持的格式各有不一。

并且，在宣称支持的格式里，各浏览器也只支持其中一部分编码格式。例如：

Firefox、Chrome 可以正常播放 Microsoft PCM, 16 bit, mono 8000 Hz 的wav，但是无法播放 GSM 6.10, mono 8000 Hz 的wav

以及来自于这篇文章的：

Playing MP3 files in Firefox is actually OS/hardware dependent. That’s right, instead of using a built in, true native support, we have to rely on outside variables that we have no control over. Kind of defeats the purpose of that whole no extensions, native support thing that HTML5 is good for. Yes, this is to avoid patent issues (and so Mozilla doesn’t have to pay licensing fees). If you are serving to a lucky person below, here’s the real MP3 support for Firefox:

Windows 7+ (Firefox 21.0)

Windows Vista (Firefox 22.0)

Android (Firefox 20.0)

Firefox OS (Firefox 15.0)

OS X 10.7 (Firefox 22.0)

大意是 Firefox 的 MP3 播放支持其实是依赖于系统和硬件的，这样可以免去专利费。相应的，支持列表就变得有点复杂了。

这里有几个测试页，可以大致用来测试主流浏览器的音频文件支持情况，但是也不完全。就如上文所述，Chrome 对 wav 文件只能说部分支持。

测试页一：http://hpr.dogphilosophy.net/test/

测试页二：https://html5test.com/

所以在实际测试中，某浏览器播放不了指定音频有两种可能性：

音频格式不支持
音频编码格式不支持

对于相关的编码格式，大致查了一下，列表如下：

OGG

同样后缀名为 .ogg 的音频文件，可能有以下几种编码格式： Vorbis, speex, OggPCM, FLAC，其中，Vorbis 是被建议的。

WAV

.wav 文件通常被理解为原始采样，未经压缩。但其实并不一定如此。最广泛标准的 .wav 文件是指微软 PCM 编码的音频文件（其实也已经编码过了，毕竟从模拟信号转数字信号无论如何都会有一个采样过程。）PCM 细分又可分为定长（16bit、32bit 等）和浮点两类。另外.wav 还可能是 GSM 编码格式，这种格式广泛使用于通讯网络，但在互联网上并不常用，最有可能的来源是电话录音导入电脑。

MP3

MP3 规范并没有详细规定如何编码，但却有细致的解码定义。也就是说『符合这一类规范的才叫 MP3』。因此，MP3 的格式反而才是最一致的，除了采样率、变长/定长和声道数量外，不存在其它变化。

Opus

Opus 是设计为同时包含音频和视频的编码格式。* 可以取代复杂的编码后封装方案。但实际上普及率很低，支持也不好。

AAC

AAC （Advanced Audio Coding）主要是得到了苹果的支持。但除此以外，在互联网的使用并不广泛。

Mozilla 提供了另一张更为详细的表格：（注意这个表还是只能作为参考）

Feature	Chrome	Firefox (Gecko)	Internet Explorer	Opera	Safari
Basic support	3.0	3.5 (1.9.1)	9.0	10.50	3.1
<audio>: PCM in WAVE	(Yes)	3.5 (1.9.1)	Not supported	10.50	3.1
<audio>: Vorbis in WebM	(Yes)	4.0 (2.0)	Not supported	10.60	3.1
<audio>: Streaming Vorbis in WebM via MSE	?	36.0 (36.0)	?	?	?
<audio>: Vorbis in Ogg	(Yes)	3.5 (1.9.1)	Not supported	10.50	Not supported
<audio>: MP3	(Yes)	(Yes)	9.0	(Yes)	3.1
<audio>: MP3 in MP4	?	?	?	?	(Yes)
<audio>: AAC in MP4	(Yes)	(Yes)	9.0	(Yes)	3.1
<audio>: Opus in Ogg	27.0	15.0 (15.0)	?	?	?
<video>: VP8 and Vorbis in WebM	6.0	4.0 (2.0)	9.0	10.60	3.1
<video>: VP9 and Opus in WebM	29.0	28.0 (28.0)	?	(Yes)	?
<video>: Streaming VP9 and Opus/VP8 and Opus in WebM via MSE	?	36.0 (36.0)	?	?	?
<video>: Theora and Vorbis in Ogg	(Yes)	3.5 (1.9.1)	Not supported	10.50	Not supported
<video>: H.264 and MP3 in MP4	(Yes)	(Yes)	9.0	(Yes)	(Yes)
<video>: H.264 and AAC in MP4	(Yes)	(Yes)	9.0	(Yes)	3.1
any other format	Not supported	Not supported	Not supported	Not supported	3.1

所以解决方案大概就是先通过测试确定一两种被绝大部分浏览器支持的音频编码格式，然后服务器后端将音频文件转码为这一到两种适用的音频格式再传递给前端。

看起来最通用的是 MP3？简单地说，是的。但要注意的是不是任意一种 mp3 编码格式都支持，最优化编码的 VBR 支持性就存疑。同时，由于 Firefox 的 MP3 支持是基于系统的，所以假如 Ubuntu 没有安装 ubuntu-restricted-extra 包也可能出现支持性问题。

* 附：

更复杂的是 <video> 标签，由于视频通常是包含声音和图像两部分的，因此实际上视频文件数据是由已经编码的视频数据和已经编码的音频数据，再次进行数据交错编制而成的。因此除 编码格式 外，又衍伸出 封装格式 的概念。深受大家喜爱的 .avi 格式，即 Audio Video Interleave 的简写，就是一种封装格式。当你使用 avi 封装器折开文件后，就会见到一个无声的视频文件和一个无图像的音频文件。至于各自的编码格式又五花八门了。因此对于 <video> 标签的支持更加混乱，几乎必然需要通过服务器转码才能确保在尽可能多的浏览器上前端一致，这也是各视频网站为什么会有大量集群转码处理用户上传的视频的原因。

VMWare 安装 Ubuntu 出现『默认声音设备无法打开』的原因与解决办法

发表于 2016-02-27 分类于软件使用

Update: Ubuntu 16.04 系的解决了这个问题。此文终结。

无标题

这个 Bug 出现在几乎所有版本的 VMWare Workstation、VMWare Fusion 而且按原理来说似乎也会出现在 VirtualBox 上（未验证）。用户选择右键点击喇叭图标手动连接，则可以使用一段时间，Rhythmbox 之类的也可以正常播放声音，但只要打开声音设置或其它类似操作就又会断开。

遇到这种情况，可以先尝试在宿主机接上麦克风/耳麦，随便弄个录音设置，或者把普通耳机插头插进录音孔也行。对的，尽管实际上录不了音，但只要让录音孔插着东西就行。无标题

然后重启虚拟机，如果一切正常该提示不再出现，就继续往下看真·解决办法，如果依然不行，很抱歉你的问题不是这篇文章所能解决的。

这个问题的真正原因是：Ubuntu 默认会检测音频硬件设备，包括音频输入和输出两种设置，但 VMWare 不能正常反馈宿主机声卡的状态。感觉更多的是 Ubuntu 的锅，它没有检测设备存在就直接调用录音设备。

解决办法：

1	sudo apt-get install pavucontrol

安装 pavucontrol 软件包，然后在 Term 中输入 pavucontrol 启动旧版的音量控制：

Ubuntu 64-2016-02-27-20-44-14

在音量控制界面，选择『配置』选项卡，选择『模拟立体声输出』，不要选任何带“输入”的项。然后注销用户再重新进入桌面。

Ubuntu 64-2016-02-27-20-45-50

以上，VMware Ubuntu 就可以正常出声了。

无标题

细则：

标签：