分类存档: Math

用六面不均匀的骰子模拟一只六面均匀的骰子

作者: 日期: 2017 年 9 月 21 日 没有评论

最近被问到了这么一个问题，蛮有意思的. 这里可以做一个额外的限定：在有限的步骤内精确地将发生的事件分割成六个概率为 1/6 的部分，而不是随着操作次数的次数增多趋近 1/6.

经过了一段时间的探索之后，我发现想要通过重复掷固定次数的骰子来达成这一目标，在知道六面各自的概率后，是不存在一个策略可以把所有发生的事件精确地分割成六份的.

我将借助超越数，使用反证法来证明这一点.

为了证明这一点，首先可以做一些化简. 六面的骰子过于复杂，可以先尝试减少到两面，也就是把骰子简化成硬币. 假设这样的策略是存在的，也就是给定一个六面概率不一的骰子及其各面概率后，就可以得到一个正整数 n，然后掷这个骰子 n 次，根据每次掷的结果将结果分为等概率的六份. 然后假设存在一种只有两面的各面概率不一的骰子.

首先，这个两面骰子可以做到六面骰子的效果. 方法是掷三次两面骰子，可以得到八种不同的结果，将这八种结果分为六份（不能有任何一份是空的），就可以得到六个概率不一的事件集. 而根据刚才的假设，知道了六种结果的概率后，把它当作一个六面的骰子，重复 n 次掷骰子的操作，然后就可以得到均匀概率的六组结果. 最后，将这六种结果的其中三种分为一组，另三组分为一组，这样就得到了均匀概率的两组结果. 也就是说，当六面骰子的策略存在的时候，两面骰子的策略也同样存在.

继续阅读 »

Lambert W function 数值计算

作者: 日期: 2016 年 12 月 6 日 没有评论

由于一些很蠢的原因，我写了一份完全用不着的用于计算 Lambert W function 的 C# 代码. 具体原理是很粗暴的牛顿法求解，但有几个特别处理的地方：

首先是估算. W0比较好处理，其实随便给个初始值就好，我这里选择了偏移后的 ex. 而 W-1 则比较特殊，首先在 x < -2 的部分变成了 concave 的，而且越往左斜率越小，所以一律从 x = -2 开始尝试；而在 -2 < x < -1 的区间内其实也是随便给个初始值就好，我这里选择了偏移后的 cos 函数.

其次是精度处理. 通过 log2x 做差可以求出二进制下的有效数位，然而当 y 值较大的时候其实并不能把完整的 52 位双精度浮点数的小数部分求完整，大概只能求到 47 位左右，所以这里我保守选择了 42 位有效数字.

继续阅读 »

舒兵的教师节礼物 —— Tupper’s self-referential formula 使用实测

作者: 日期: 2012 年 9 月 15 日 6 条评论

Tupper's self-referential formula（图片来源：wikipedia）

教师节那天中午vIstaswx跑过来跟我讲教师节要送给舒兵（怎么又是舒兵= =）一个图像是”SB”的函数，然后把 Tupper’s self-referential formula 丢给了我。我们首先确定了其中的k值是一段二进制数据，只是排列方式未知，所以首先开始找出这个函数的工作原理：

继续阅读 »

关于“完全无匹配”问题的通式

作者: 日期: 2012 年 6 月 20 日 没有评论

今天舒兵课末讲了一个“完全无匹配”问题（即有N个对象A和N个对象B分别编号 1,2,3,…,N ，A与B一一组合，要求A与B编号不相同），于是全班陷入了通式计算的苦战中..

在又报废两页草稿纸之后终于得出一个好吓人的通式：

Expression

大致意思是这样：首先求出包括任何匹配的所有情况，然后减去匹配1对的总数，减去2对的，……，减去N对的，最后的结果就是完全无匹配的总数。但是由于计算N对的时候仍然需要用到一个更小范围的完全无匹配，因此这个算法变成了递归算法，只能用计算机求解了。

代码编写上增加了一个缓存，防止重复运算，毕竟输入唯一值输出也是唯一值，而且运算量很可观。

以下是在线计算。注意：由于运算位数不够最高只能求到170，并且23及以上只能用指数方法表示浮点数。

请在上方输入要运算的完全无匹配对象的总数

2016.10.27 更新：通解记作 !n （Derangement/subfactorial） 更简单的递推公式见 http://www.matrix67.com/blog/archives/6665 第二题.