1 某机器需要处理n个请求，每个请求都有其运行所需的存储空间(R[i])及运行之后输出所占用的存储空间(O[i])，且O[i]小于r[i]。假设CPU只能同时处理一个请求。现在该机器共有m个存储空间，请设计一个算法来安排这n个请求的处理顺序，使得所有请求都能被处理。并简要说明该算法的正确性。如果无论如何安排也不能处理完这些请求，算法也应能给出判断。SOL: 贪心法， 按照R[i]-O[i]降序排列请求
2 在一个空间里有m（m为偶数）只老虎，n只兔子，还有一个你，总共m+n+1只东西（什么，你说你不是东西？）每次随机地抽出两只东西发生互动（通常造成可怕的结果），幸存者再放回去。具体规则如下：
1）老虎和老虎->两相残杀
2）老虎和兔子->老虎吃掉兔子
3）兔子和兔子->没事
4）老虎和你->你成为老虎的美餐
5）你和兔子->你可以选择放回去或煮了兔子
问题是：最后你虎口余生(即，出现山中无老虎，猴子称大王的局面）的概率是多少（你需要在兔子问题上作出最优决策使此概率最大）
SOL: 1/(m+1) 本题最大的trick在于认识到兔子的存在其实根本不影响最后结果，可以直接忽略所有的兔子。剩下m只老虎和一个你。所求概率相当于你排在最后一位的概率。
3 16个人背后各贴一个数字，每个数字都可能取1到16的任意整数值（即可以重复，可以有数字不出现），每个人可以看到其他人的数字，但看不到自己的，贴好数字之后不可以进行任何形式的交流（诸如使用排队次序传达信息之类的伎俩无效），每人猜一个数字，问事先如何安排可以保证至少有一人猜中自己的数字。
SOL: 16个人每个人分别猜自己背后的数字,也就是16个人分别猜16个1-16的数字,显然无法保证一定一人猜中。但是如果16个人集中猜同一个1-16的数字X则能保证一定有一个人猜中, 方法是每一个人分别猜一个数，遍历解空间。这里我们这样人为制造出X:X = X1 xor X2 xor X3... xor X16 (X_i是第i个人背后数字).所以这个X对于所有人是一样的.于是可以第i个人可以猜测一个数Yi,这个数Yi满足和其他所有能看见的人背后的数字的xor之和为i.
Tuesday, April 28, 2009
Wednesday, April 15, 2009
[Emacs]调整字体
update @ 2009/6/09
对于最新的emacs 23版本,字体描述格式,已经从X Logical Font Description (XLFD)转变为更为简单的fontconfig方式.关于两种字体系统,可以参见本blog里这个帖子.不过为了向前兼容,XLFD依然被支持.比如同是描述13pt的Courier New字体,两种格式分别如下:
对于emacs22以及更早版本的字体设置如下:
-------------------------------------------------------------------------------
说实话emacs里要调整个字体什么的还真挺麻烦的。一般的基于GUI的editor都比它来的简单直接。
1 关于Linux下的字体
使用xlsfonts来查看系统里有哪些字体
可以通过xfd来预览你想尝试的字体， 比如
2 回到Emacs
可以通过M-x set-default-font 然后输入字体名称(如果不知道可以用tab来complete)来设置当前字体。如果需要固定下来，可以在~/.emacs当中加入:
需要额外指出的是，这里我设置成了dejavu的等宽字体。不过我发现使用了这种字体以后，line spacing显得过大了，所以可以用以下语句来调整：
3 几个字体设置的小tip
[1] http://www.linuxquestions.org/questions/linux-software-2/emacs-changing-default-font-size-and-font-type-489000/
[2] http://www.yuanma.org/data/2006/0503/article_355.htm
[3] http://www.gnu.org/software/emacs/windows/Fonts-and-text-translation.html
对于最新的emacs 23版本,字体描述格式,已经从X Logical Font Description (XLFD)转变为更为简单的fontconfig方式.关于两种字体系统,可以参见本blog里这个帖子.不过为了向前兼容,XLFD依然被支持.比如同是描述13pt的Courier New字体,两种格式分别如下:
XLFD: -*-Courier New-normal-r-*-*-13-*-*-*-c-*-iso8859-1
Fontconfig: Courier New-13
(add-to-list 'default-frame-alist '(font . "DejaVu Sans Mono-14"))这样普通和daemon模式就都可以正确设置字体了.
对于emacs22以及更早版本的字体设置如下:
-------------------------------------------------------------------------------
说实话emacs里要调整个字体什么的还真挺麻烦的。一般的基于GUI的editor都比它来的简单直接。
1 关于Linux下的字体
使用xlsfonts来查看系统里有哪些字体
$xlsfonts得到像如下格式的输出
-adobe-courier-medium-r-normal--17-120-100-100-m-100-iso8859-1每一行都是一种系统支持的字体。每一行的格式参见 Font specification , 简单说来遵循“-maker-family-weight-slant-widthtype-style-pixels-height-horiz-vert-spacing-width-registry-encoding"这样的格式。需要特别指出的是pixels代表的是字体的高度(单位是像素)，height代表的是字体在屏幕上的高度*10(单位是磅), pixels和height两个当中通常只指定一个值，另一个用*代替。另外我们注意到列出来的字体当中有些字段为0,这说明这些字体是矢量字体。对于这些字段我们使用的时候需要用数字或者*来替换。
-dejavu-dejavu sans mono-medium-r-normal--0-0-0-0-c-0-iso8859-1
可以通过xfd来预览你想尝试的字体， 比如
$xfd -fn "-dejavu-dejavu sans mono-medium-r-normal--16-*-*-*-c-*-iso8859-1"
2 回到Emacs
可以通过M-x set-default-font 然后输入字体名称(如果不知道可以用tab来complete)来设置当前字体。如果需要固定下来，可以在~/.emacs当中加入:
(set-default-font "-dejavu-dejavu sans mono-medium-r-normal--16-*-*-*-m-*-iso8859-1")
需要额外指出的是，这里我设置成了dejavu的等宽字体。不过我发现使用了这种字体以后，line spacing显得过大了，所以可以用以下语句来调整：
(setq-default line-spacing 0)另外我这里的emacs有一点小bug所以set-default-font以后会有好几秒钟的延迟，需要在~/.emacs开头加入
(modify-frame-parameters nil '((wait-for-wm . nil)))
3 几个字体设置的小tip
- M-x describe-char 我们可以使用这个命令查看光标所在的字符采用的是什么字体。
- M-x describe-fontset 这个命令用来查看各个字符集分别采用了什么字体。
- 在*scratch* buffer中输入(frame-parameter nil 'font) 光标放在行末按C-x C-e就可以看到当前字体
- Shift + MouseLeftClick可以出来字体选择对话框;
- M-x describe-font可以查看当前字体描述
- M-x set-default-font
可以看到可以选择的字体。
[1] http://www.linuxquestions.org/questions/linux-software-2/emacs-changing-default-font-size-and-font-type-489000/
[2] http://www.yuanma.org/data/2006/0503/article_355.htm
[3] http://www.gnu.org/software/emacs/windows/Fonts-and-text-translation.html
Sunday, April 12, 2009
[Python] Yaml与Json
Python2.6开始支持Json，见Json库。
Yaml的Python库见PyYaml
简单说起来:
关于两者详细的关系和区别，这里有一片英文的文章讨论yaml与json的关系
Yaml的Python库见PyYaml
简单说起来:
- Python的json库在默认设置下输出的是Yaml语言的子集
- 两个库的语法基本一致。不同的是yaml的dump输出的直接为字符串，json的dump还需要指定一个stream object。如果要输出为字符串，得使用dumps
关于两者详细的关系和区别，这里有一片英文的文章讨论yaml与json的关系
Saturday, April 11, 2009
[MacOS] MacOS系统使用经验笔记
- 在Finder中找隐藏目录的热键: shift+command+G。默认的finder界面里是不会显示隐藏目录的。所以用上述热键然后手动输入路径
- MacOS X中设置环境变量和普通Unix/Linux的方法略有不同。你依然可以像在Unix/Linux 中那样在
~/.cshrc(tcsh)或者~/.bashrc(bash)里设置环境变量，对于terminal中的程序完全没有问题。但是对于基于Carbon或者Cocoa的Native Mac程序(比如Carbon Emacs)来说是没有用的。它们不会从shell中继承环境变量。一个方法是把$PATH, $PYTHONPATH等环境变量设置在~/.MacOSX/environment.plist这里。可以用(a) "/Developer/Applications/Utilities/Property List Editor.app"这个工具修改. 也可以(b) 用defaults 命令:
defaults write ${HOME}/.MacOSX/environment PATH "${HOME}/bin:/usr/bin:/bin:/usr/local/bin"
为了在系统中使用统一的设置，在~/.cshrc中， 使用如下命令:
setenv PATH `defaults read ~/.MacOSX/environment PATH`
注意： 需要重启以使改变生效
Updated on Aug 27, 2012:~/.MacOSX/environment.plist已经deprecated了. 新的方法是修改/etc/launchd.conf使得所有Unix 环境变量在GUI中可见 参考Accessing the Unix environment from emacs and Cocoa apps in OS X Mountain Lion
- 显示Mac里系统相关信息
查看总体的系统信息$ system_profiler
查看CPU信息$ sysctl -a machdep.cpu
或者$ sysctl -n machdep.cpu.brand_string Intel(R) Core(TM) i5-2435M CPU @ 2.40GHz
-
如果从打开Terminal开始到出现提示符为止的等待时间过长, osxdaily说这是由于系统的login process会读取/private/var/log/asl下所有的系统日志文件.所以我们可以把这些日志删除来加速login过程
sudo rm -rf /private/var/log/asl/*.asl
- 用命令行打印文件
$ lpstat -a GHC6107_BW accepting requests since Sun Oct 28 15:30:42 2012 GHC9206_BW accepting requests since Mon Oct 29 12:48:11 2012 GHC9206_COLOR accepting requests since Mon Nov 28 13:00:02 2011 $ lp -d "GHC9206_BW" -o sides=two-sided-long-edge *.pdf request id is GHC9206_BW-82 (6 file(s))
- 在Lion以及Mountain Lion中关掉ipv6
$ networksetup -setv6off ethernet $ networksetup -setv6off wi-fi
Subscribe to:
Posts (Atom)