Tuesday, January 19, 2010

[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n 也就是出现第i种新coupon的概率.
E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n


该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:
\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}

Sunday, January 17, 2010

[Emacs]我总结的Emacs Cheating Sheet

这有一个不错的pdf版本cheat Sheet:Emacs Cheat Sheet

C代表Ctrl键, M代表Meta键, ←和→是右箭头和左箭头
基本操作
这里总结的是基本操作,大多数mode下都可以用
在文本中移动
C-f, C-b 向前(C-f)或是向后(C-b)移动到下一个字符.
M-f, M-b 向前(M-f)或是向后(M-b)移动到下一个单词.
C-M-f, C-M-b 在一对匹配的括号间,向前(C-M-f)或是向后(C-M-b)跳转.
C-a,C-e 移到当前行首(C-a)或者行尾(C-e).
M-a, M-e 向前(M-a)或是向后(M-e)移动到下一个句子.
C-x C-space 跳转到上一个mark的地方
C-v,M-v 向前(C-v)或是向后(M-v)翻页
M-<, M-> 移动到buffer首/尾
M-m 移动到第一个非空格字符。(back-to-indentation)
M-r 加参数,移动到窗口里的某一行。不加参数缺省移动到窗口中间。
M-x goto-char 到文件的第 N 字节。
M-x goto-line 到文件第 N 行。
C-x C-n 设定 goal-column.
C-u C-x C-n 取消 goal-column.
M-g g 移动到指定行

编辑文本
C-o 当前位置插入一行
M-Delback,M-d 以word为单位的前删/后删
C-d 删除后面一个字符且不放入kill-ring
C-M-k 向前删除直到匹配括号
Esc-C-Del,Esc-C-Backspace: 先后删除到匹配括号
M-z : 删除到下一个出现的位置

大小写转换
从光标位置开始,处理单词后半部分
capitalize-word (M-c) -- 首字母改为大写
upcase-word (M-u) -- 全部改为大写
downcase-word (M-l) -- 全部改为小写
从光标位置开始,处理单词前半部分
negtive-argument; capitalize-word (M-- M-c)
negtive-argument; upcase-word (M-- M-u)
negtive-argument; downcase-word (M-- M-l)
改变选定区域的大小写 downcase-region (C-x C-l) -- 选定区域全部改为小写
upcase-region (C-x C-u) -- 选定区域全部改为大写


设定Marker
C-空格,C-@ 设定一个mark
C-x h 整个缓冲区全部mark

对齐 (http://www.emacswiki.org/emacs/AlignCommands#toc2)
M-x align 对齐当前选择
M-x align-current 对齐当前section
M-q fill-paragraph 对一个段落排版

获取帮助
C-h c 简要描述给定键绑定
C-h k 详细描述给定键帮定
C-h f 描述给定函数
C-h v 描述给定变量
C-h m 描述当前mode
键/键组合 C-h 以当前键/键组合开头的绑定
M-x `finder-commentary' RET foo RET.

查找
C-s 向前方查找
C-r 向后方查找

注释
M-; 注释一个区域或者去掉区域的注释 (需要开启transient-mark-mode以后)

操作矩形
首先Set Marker然后移动光标围成一个矩形区域
C-x r k 删除矩形区域
C-x r t 矩形区域中插入文本

切换不同窗口
C-x 0 删除当前窗口(注意是零不是o)
C-x o 把光标在屏幕上的窗口间进行切换。记忆方法:其它(other)窗口。
C-x 1 把当前光标所在的窗口放到最大,隐藏其它所有的窗口。记忆方法:只剩一(1)个。
C-x 2 水平切分屏幕
C-x 3 竖直切分
C-x w r 1 存储当前窗口layout到寄存器1(可以为其他数字)
C-x j r 1 读取寄存器1(可以为其他数字)中的窗口layout

切换不同buffer
C-x b 缓冲区名称. emacs会提供一个缺省的缓冲区,一般是上一个用到的.如果不行,手动输入缓冲区名称,支持和自动补全.
C-x C-b 列出缓冲区菜单. 但这个命令不会将光标移动到缓冲区菜单的窗口中,需要C-x o命令切换过去.
C-x →,C-x ←. 循环切换到前一个(后一个)缓冲区
C-x k 杀死一个缓冲区(默认是当前缓冲区)
C-x C-s 保存当前缓冲区

切换不同frame
C-x 5 0 切换frame

在Emacs中使用Shell buffer
M-x ansi-term 带有色彩支持的term
M-x shell 系统默认shell
M-x eshell emacs自带shell

参数
M-<数字> : 执行 <数字>这么多次
C-u <数字> : 同上



常用Mode下的操作
AucTex LaTeX mode
C-c C-b 编译buffer / 预览编译结果
C-c C-r 编译选定的region
C-c C-c 运行定义好的命令比如 latex, view, bibtex
C-c C-v 查看当前的output file
C-c C-e 添加指定的环境
C-u C-c C-e 替换当前的环境
C-c ] 添加\end{...} 来匹配当前环境
C-c ; 注释选定区域,再操作一次就是去除选定区域的注释

CC mode
子模式:
auto-state 当你输入时自动缩进,自动换行
hungry-state 当你Backspace时,自动删除尽可能多的空白和空行
C-c C-t 同时转换(开/关)auto-state和hungry-state子模式
C-c C-a 转换 auto-state 子模式
C-c C-d 转换 hungry-state 子模式

M-/ 自动补齐(缓冲区中能找得到的串)
M-; 行尾加入注释
C-c C-e 扩展宏
C-c C-c 注释掉整个区域
C-c C-\ 将区域中的每一行结尾都加入一个'\'字符

cc-mode下的缩进
C-c . 设置缩进风格(按TAB键可列出可用的风格,缺省的为gnu,其 缩进为2个字符;linux为8个;k&r为5个…)
C-c C-q 缩进当前函数
C-M-q 缩进当前表达式
tab 缩进当前行
C-x h C-M-\ 缩进当前buffer
C-M-u C-M-q 缩进当前block

Lisp mode (http://www.delorie.com/gnu/docs/emacs/emacs_329.html)
C-: 执行一行lisp
C-x C-e 执行光标前的lisp

VC (version control) mode(http://lifegoo.pluskid.org/wiki/EmacsVC.html ,http://lifegoo.pluskid.org/wiki/EmacsVC.html , http://www.credmp.org/?p=65)
C-x v i 添加当前buffer的文件到version control当中
C-x v v 下一个合理的version control 动作(通常在一个状态下只有一个合理动作)
C-x v m 更新当前文件
C-x v + 更新当前文件集合
C-x v d 显示一个目录下所有注册到版本控制下的文件
C-x v l 查看log
C-x v = 和repository上代码作比较
C-x v ~ 查看以前版本

org mode (官方手册 , 中文教程)
Org mode是Emacs上一个用于组织信息,管理信息,撰写大纲的利器.可以帮助你非常快速的组织思路,查找信息.
C-c C-t Rotate the TODO state of the current item among
C-Shit-Enter 新建一个TODO 项目
Shit+Tab 切换view
链接:
[[链接地址][链接名称]]比如 [[http://www.gnu.org/software/emacs/][GNU Emacs]]
或者 [[链接地址]]如果你不需要名称


Cscope Mode
C-c s a 设定初始化的目录,一般是你代码的根目录
C-c s I 对目录中的相关文件建立列表并进行索引
C-c s s 序找符号
C-c s g 寻找全局的定义
C-c s c 看看指定函数被哪些函数所调用
C-c s C 看看指定函数调用了哪些函数
C-c s e 寻找正则表达式
C-c s f 寻找文件
C-c s i 看看指定的文件被哪些文件include

Dired mode (http://jamesthornton.com/emacs/node/emacs_396.html#SEC396 , http://www.20seven.org/journal/2008/11/emacs-dired-directory-management.html)
Dired mode用于文件管理
C-x d/M-x dired 进入Dired模式
C copy
D delete
# 标记所有atusave文件
R rename
s sort

iBuffer mode (http://www.emacswiki.org/emacs/IbufferMode)
和Dired mode相仿,但是用于buffer管理
M-x ibuffer 进入ibuffer模式
m 选定当前位置buffer
u 去除选定当前位置buffer
t 改变buffer list里每个buffer的选定状态
D 删除当前选定的buffer(们)
g 刷新
% n 选定所有那些buffer名称符合给定正则表达式的
% m 选定所有那些mode名符合给定正则表达式的
% f 选定所有那些文件名符合给定正则表达式的

GDB
M-x compile RET 编译
M-x gdb RET 调试
gdb --annotate=3 a.out 或者 gdb -i=mi a.out
C-x ` (出错信息中)下一个错误,一个窗口显示错误信息,另一个显示源码的出错位置
C-c C-c 转到出错位置

启动gdb调试器后,光标在源码文件缓冲区中时:
C-x SPC 在当前行设置断点
C-x C-a C-s step
C-x C-a C-n next
C-x C-a C-t tbreak
C-x C-a C-r continue

其他一些七七八八的

设置AucTex中的viewer. AUCTeX以前是通过设置TeX-output-view-style和TeX-view-style来决定如何根据output文件的后缀来用不同的viewer打开output文件. 新的实现是通过设置TeX-view-program-list和TeX-view-program-selection两个变量来实现:
比如把pdf和dvi文件关联到Evince.
(setq TeX-view-program-list '(("Evince" "/usr/bin/evince --page-index=%(outpage) %o")) )
(setq TeX-view-program-selection '((output-pdf "Evince") (output-dvi "Evince")) )

--could be out of date---
改变AUCTeX默认pdf viewer:
"Customize group - Auctex - Tex Command" entry for the "^pdf" extension in
"Tex Output View Style" => "evince %o"

重要变量
major-mode: 当前mode

载入.emacs文件
M-x load-file RET ~/.emacs RET Reload .emacs without restarting

check the value of your load-path by asking for help on the variable: ‘C-h v load-path RET’

By default Emacs doesn’t include subdirectories of a directory which is added to load-path. But you can do it by issuing a command in startup file:

(normal-top-level-add-subdirs-to-load-path)

Recover Data
M-x recover-file <ret> foo.c <ret>
yes <ret>
C-x C-s

查看package路径
M-x locate-library

在eclipse当中绑定emacs键位设定
Window->Preferences->General->Keys Scheme中选emacs

强制使用某种mode 比如xxx-mode
M-x xxx-mode

刷新当前文件
M-x revert-buffer
刷新所有已经打开的文件
M-x revert-all-buffers

去除所有结尾的whitespace
M-x delete-trailing-whitespace

绑定key http://www.xemacs.org/Links/tutorials_2.html http://www.gnu.org/s/emacs/manual/html_node/elisp/Key-Binding-Commands.html
(global-set-key (kbd "C-x C-\\") 'next-line)

显示行号(类似vi中的 :set nu)
(global-linum-mode t)

如果希望emacs帮你自动wrap line,
M-x auto-fill-mode

判断当前系统
(if (eq system-type 'windows-nt) do-what-you-like)
如果是MacOSX, 把'windows-nt换成'darwin

C-\ 切换 "拼符"输入法