[数学]一道关于硬币的概率题

硬币不知道fair还是不fair,第一次扔是head,第二次让你赌,你赌哪个,概率多少? zz from mitbbs
SOL: 采用Bayes. 设硬币得到head的概率为p. 因为硬币不一定是fair, 所以这里p实际是一个随机变量. 在没有其他信息的情况下,我们假设p的先验是一个0到1之间的均匀分布,即U[0,1]. 这种情况下, 得到head的概率为:

P\{head\} = \int_{p=0}^1P{head|p}\mathrm{d}p = \int_{p=0}^1p\mathrm{d}p=\frac{1}{2}

投掷硬币得到head, 在这种情况下,p的条件概率密度函数f(p|head)就不再是U[0,1]. 这是因为p越大越容易得到head,因此得到head的时候以更大可能观察到比较大的p而不是等概率.f(p|head)的密度由下式求得.注意这里f(p)=1(均匀分布),以及P{head|p} = p.

f(p|head) =\frac{P\{head|p\}f(p)}{P\{head\}}=2p

所以给定head情况下,p的点估计:

\hat{p} = \int_{p=0}^1 2p p\mathrm{d}p = 2/3

再来一道类似的:6个小孩,3女2男,还有一个性别未知.随机选择6人中的一个,发现是男孩.那么未知的那个小孩是男孩的概率?
SOL: 假设未知的那个小孩是男孩的概率是p. 假定p=1/2
选出来的小孩是男孩的概率是
P{pick a boy}=P{pick a boy|unknown=boy}P{unknown=boy}+P{pick a boy|unknown=girl}P{unknown=girl}
=3/6*1/2+2/6*1/2=5/12

则
P{unknown=boy|pick=boy} = P{pick=boy|unknown=boy}P{unknown=boy}/P{pick a boy}=3/5

[Latex]支持中文方案1:CJK

update @ 2009/6/9:经过比较我还是觉得用xetex来支持中文更加简单.可以见本blog中的:Xetex起步
决定写一些中文文档，所以要装Latex的中文支持。在ubuntu上很简单：
我已经安装过了 texlive-full (没有的请先安装)，所以就只需要从源里安装latex-cjk-chinese(只针对中文，如果你还需要日文韩文，请安装latex-cjk-all)。
然后就可以试一下中文的latex文档了。
记住用

\begin{CJK}{编码种类}{字体种类}
\end{CJK}

把用到中文的地方包围起来就可以了。这里CJK环境可以换成CJK*环境，区别是CJK环境里中英文间会有空格而CJK*没有。编码种类可以是GB，Big5 也可以是UTF8，取决于你自己的locale设定。我是用的纯英文环境，所以都上的是UTF8。默认情况下字体种类选择不多，可以是gbsn(gb宋体)，gkai(gb楷体)，bsmi(big5宋体)，bkai(big5楷体)
可以实验一下这个文档：

\documentclass{article}
\usepackage{CJK}
\begin{document}
\begin{CJK*}{UTF8}{gbsn}
您好!
\end{CJK*}
\end{document}

[数学]一道小学应用题

近日，网友“跳水白菜”在天涯重庆上发帖，希望借网友的智慧，解答出一道小学六年级的数学题。

“一辆大客车和大货车分别从甲乙两地出发，经过7个小时相遇，然后仍按各自的速度前行，3小时后，大客车距乙地120公里，大货车距甲地 160公里，求甲、乙两地的距离是多少千米？”

解答出这样一道数学题，在最初回答问题的网友看来，似乎是一件很简单的事情。众多网友都给出了步骤和答案，但大多都采用了2元1次方程式，甚至3元1次方程式。有网友提出了尖锐的问题：小学生是没有学习过2元1次方程式的，更别谈3元1次方程式，这样的题目就不能使用这种方式解答。面对这样的题目，其内容和解答方式雷翻了众多的网友。

SOL:其实这道题不需要用到方程.我从小就喜欢把那些看似要用解方程才能做出来的题目硬是分步计算出来.这里给出这道题目的分步计算方法:
甲乙两地距离=甲速*7+乙速*7,同时又有 甲乙两地距离=甲速*3+乙速*3+120+160
我们可以得知 (甲速+乙速)*4 = 280 => 甲速+乙速 = 70 (公里/小时)
甲乙两地距离=70*7 = 490 (公里)

[算法]拳皇友谊赛

这两天看到的一道蛮好玩的题：
变态的比赛规则：为了促进各部门员工的交流，百度(baidu)举办了一场全公司范围内的"拳皇友谊赛"，负责组织这场比赛的是百度的超级"拳皇"迷W.Z. W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。

比如4个人，编号为1--4,如果分为两个组并且1,2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是1,2,3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4.

很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能只需要1场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

输入
每行为一组数据，包含两个数字 N, K

输出
对输入的N,K 如果N个员工通过一定的分组方式可能会一共需要K场比赛，则输出"YES",否则
输出"NO",每组数据占一行。所有的输入输出均为标准输入输出。

SOL:这道题是一道潜伏很深的动态规划。先建一下模：N个人，如果分成m组，每组x_i人，那么需要打的比赛场数是

\sum_{i\neq j} x_ix_j

。所以本题就是给定N,看是否能找到一个组人数划分使得上式等于K。

做一下变化:

K=\sum_{i\neq j} x_ix_j = \frac{(x_1+\ldots+x_m)^2-\sum_ix_i^2}{2}=\frac{N^2-\sum_ix_i^2}{2}

所以这里我们把这道题变成了如何找到m个数使得这m个数的和等于N，平方和等于N^2-2K。

令T(s)为所有"平方和为s的一组数的和"的集合，即:

T(s)=\{x_1+\dots+x_m|\forall \sum_ix^2_i=s\}

所以T(5)={3,5}，也就是说5可以分解为1+1+1+1+1也可以分解为1+2^2。
关于T(s)的递推式为

T(s)=\left\{\begin{array}{ll}
(\bigcup_{i=1}^{s/2} (\{t\} \cup T(i))\odot T(s-i)) & i=t^2\\
\bigcup_{i=1}^{s/2} T(i)\odot T(s-i) & \textrm{otherwise}
\end{array}
\right.

这里定义

A\odot B = \{ a+b | \forall a\in A, b\in B\}

边界条件: T(1)={1}

[算法]找树的重心

以前算法课作业做过这道题。今天在网上又碰到了。

给一个有n个结点的树，每个节点i都有一个正权重w(i),每条边j也有一个正权重c(j). 要求给出一个线性复杂度的算法，找出一个结点u，使得对其他所有结点i，w(i)*L(i)的总和最小，其中，L(i)为i到u路径上的所有边的权重和.

SOL: 本题贪心就足够了。记sumW为树上所有节点权重和(仅仅节点)以及WC_i[p]为以p为根的第i颗子树中所有节点权值和(仅仅节点)。如果P是重心，则　"sumW>2*WC_i[p]" 对于所有P的子树i成立--所有子树的权重都小于所有节点权重和的一半。为了找到满足这个条件的节点 用贪心就足够了。随便从一个节点开始，看到哪个子树的权重和超过所有节点权重和一半，就往那个子树移动。直到不能移动位置为止。

[Linux]抛弃scim投奔ibus输入法啦

网上面对于ubuntu大多数人推荐使用scim输入法。我一直用的就是scim-python。无奈它兼容性还是有问题，qt程序底下总是没法用热键切换。最近我的pidgin也老和它冲突。于是上网一搜，发现进来新的ibus输入法很流行。是scim-python的原作者写的。于是就去装了一个下来。对于ubuntu用户，步骤很简单。直接apt-get install ibus就可以了。好像官方源里暂时还没有ibus，我是添加了ppa的源。步骤可以参见这里。

除去ibus这个平台，还需要安装具体的输入法。比如我安装了ibus-pinyin 也就是拼音。还有ibus-table包括了五笔等输入法。由于我是gnome的桌面，还安装了ibus-gtk这个库，后面要用到。

然后就用im-switch -s ibus把输入法设置为ibus。没有im-switch的可以装一下，这样比较干净。不用再去profile里设置环境变量。然后重启看一下效果吧。这个ibus用起来很舒服， 有种在windows底下用google输入法的感觉。


另外我是emacs用户，所以一般都把默认的切换热键ctrl+space换成alt+shift。可以在ibus的preference里设置。需要注意的是alt+shift要加上release（键松开）的修饰，不然不行， 不知道为什么。