递归的威力，以project euler 31为例
2014-04-27 by 煎挠橙最近刚开始算法学习，对递归思想非常着迷，做project euler时遇到题目就想用递归处理一下，但总的来说吃力不讨好。倒是今天给我找到一个绝佳的例子，相比于暴力破解，用递归重写后的代码轻巧了许多，可读性也增强了。
题目
project euler 31题:
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
暴力破解1
看到题目最自然的想法是穷举一下所有的组合，检测和是不是200。
这是非常原始的暴力破解方法，好处是不需要进一步的思考，非常容易写，且保证能得到正确结果。这几点好处——尤其是保证能得到正确结果是后面优化的基石——使得这种粗陋的代码也有写出来的价值。
当然，缺点是效率不理想，一般不会作为最终版本来使用。这里还好，只用了三四分钟，有时则可能要几个月，那就不得不立刻开始优化了。
代码：
def coin():
counter = 0
for i100 in range(3):
item100 = 100 * i100
print "100:", i100
for i50 in range(5):
item50 = 50 * i50
print "50:", i50
for i20 in range(11):
item20 = 20 * i20
for i10 in range(21):
item10 = 10 * i10
for i5 in range(41):
item5 = 5 * i5
for i2 in range(101):
item2 = 2 * i2
for i in range(201):
if item100 + item50 + item20 + item10 + item5 + item2 + i == 200:
counter += 1
return counter
上面的代码没有考虑只取200分的情况，所以得到的结果加上1才是正确答案。
暴力破解2
project euler前面的题目都比较简单，根据经验，算法得当的话运算时间都可以轻松压在毫秒级，上面的代码算了几分钟是不可忍受的。
问题显然在于计算了太多本不需要的计算的可能，所谓优化，不过是不需要算的部分直接不算了，具体到这个问题上，上面是先列举可能，再测试是否符合要求，其实可以反过来处理，你不是要200吗，那就从里面往外减，什么时候减没了算完。
所以代码可以写成：
def coin2():
counter = 0
item200 = 200
while item200 >= 0:
item100 = item200
while item100 >= 0:
item50 = item100
while item50 >= 0:
item20 = item50
while item20 >= 0:
item10 = item20
while item10 >= 0:
item5 = item10
while item5 >= 0:
item2 = item5
while item2 >= 0:
counter += 1
item2 -= 2
item5 -= 5
item10 -= 10
item20 -= 20
item50 -= 50
item100 -= 100
item200 -= 200
return counter
好消息是效率提升不少，现在只需要16ms就可以搞定。
但依旧是8曾循环嵌套，烧脑子可读性差容易出错就不说了，这里问题简单些只要8层就能解决问题，可如果遇到更多的呢？你能写出来解释器也吃不消吧。
递归
这种问题很适合用递归来处理，先不多说，看代码：
def coin3(l=[200, 100, 50, 20, 10, 5, 2, 1], target=200):
counter = 0
if len(l) == 1:
return 1
while target >= 0:
counter += coin3(l[1:], target)
target -= l[0]
return counter
刚写出来的时候我也不相信，之前繁琐的代码竟然可以变的如此漂亮，但算出来的答案是一样的，不骗你。唯一的缺点是用递归慢一些。
那这是怎么正常工作的？
设想我们有一个一般化的处理方案，函数coin(l, target)，吃进去一个包含了所有可取的硬币额度和一个最终需要的总数，吐出来的就是所有可能的组合方案，没错这就是我们要的。
但这个函数怎么写呢？下面一步很关键。
主要用到了分而治之的战略思想。先考虑一个简单的例子，coin([5, 2, 1], 10)，很容易发现有10种可能，问题在于使用了怎样的解题思路。
一个保证不漏掉可能的思路是先考虑到底有取了多少个5分，显然只能是0或1或2，如果是0的话，问题被简化为求coin([2, 1], 10)，同理，如果是1的话问题简化为求coin([2, 1], 5)；最后只需要把几种情况下的可能加起来就是最终结果了。
这就是递归处理的思路，每次只处理一个候选项，并将简化了的问题通过自己调用自己的方式解决，一路下来正确答案就自己跳出来了。
唯一需要留心的是这种递归调用终结在什么地方，稍微思考一下就会发现，是整个问题最基础最简单的情形，这样解决起来也不费什么功夫了。
再看一眼
其实递归的思路和第二版的暴力破解是一样的，但得益于函数可以自我调用这一特点，代码被大大简化了。
就好比没有循环之前你想求1到100的求和只能老老实实一步一步去写，用上循环则只需要三行。
用递归的好处在于，问题被一般化了，8曾循环是这样写，100层还是这样写（只要不爆栈的话...）。代码思路变得更加清晰，可读性更好，出错的机会就小了。
但递归这种思想和人脑的工作方式有悖，所以理解也好、使用也罢并不是那么自然，需要训练。
不管如何这都是一种强大的处理问题的思路，值得好好斟酌一番。
一点补充
上面的代码其实还取了一个巧，因为最后一个选项是1，所以不管前面怎么分配，到最后一步时总能找到一个符合要求的结果，所以索性不算了。如果要处理更一般的情况，则还需要一些改动。
用pandoc-markdown，像写word一样写pdf
这篇文章要实现的效果是你在记事本或者随便其他什么编辑器里面写markdown，然后通过一个简单的指令直接生成一份优雅的pdf文档。
接下来将要涉及以下话题：
- markdown，如果你还不知道的话，可以参考我的这篇：为什么应该用markdown写作
- pandoc，这是一个近乎万能的文档格式转换软件，具体的用法下面详细介绍
- latex，是一种标记语言以及生成pdf方式，如果你没听说过，或者不知道该如何处理中文，可以参考我这篇：在ubuntu上编译中文latex文档
但是，为什么是pdf
我在为什么应该用markdown写作中提到微软的.doc不是一种理想的格式，同时，我也不太喜欢pdf，但我仍旧有足够的理由选择编译pdf：
- 是单纯且专业的文档展示标准，确保不同设备不同环境下阅读体验的一致
- 处理得当的话效果非常优雅
- 是出版业，论文圈里的绝对标准
- 数学公式，希腊字母的良好支持
- 逼格当真高
当然，因为latex本身极其繁琐恼人，很少有人真的直接手写latex源文件然后去编译pdf的，事实上如果你像我一样用latex写过一学期的场论作业，就会真切的明白为什么这样干逼格高了。
那么，能不能不干脏活又效果优雅呢
当然可以！
其实很长一段时间里我是能不碰latex-pdf就不碰的，倒是把markdown当成日常标准每天都在用。一个偶然的机会下我看到了pandoc，那一刻我明白，整个生态链的最后一环找到了，此后便是神器在手。
思路很简单，先用markdown写文档 ...
read more你为什么应该用markdown写作
什么是markdown
markdown不是什么程序或者工具，只是一种轻量级的标记语言，目的是为了让你用windows上最常见的记事本也能写出一份漂亮的文档。
不过事实是，微软的office套件如此深入人心，以至于听到我说用记事本写作大多数人会觉得我疯了。
所以我决定跳过markdown的具体语法（其实非常简单）和适用的场景（掌握了整个markdown生态链后其实完全可以抛弃微软），先来谈谈为什么要用markdown写作。
为什么要用markdown写作
彻底解决了兼容问题
正如前面所说，markdown的存在让我们用记事本写作成为可能，保存的格式自然也是纯文本的，也即windows下面的.txt，这么做有什么好处呢？
xp时代过来的同学应该都清楚office2003和2007之后的版本存在着不兼容的问题，为此吃过亏的人恐怕还不少。这还是在大家都装了盗版office的情况下才会发生的。遇到一个根本没装office的电脑再给你一个word文档你就哭去吧。当然现实没有我说的那么戏剧，但自己写了东西还非得用一个商业公司的商业软件才能打开，这么受制于人总是不好受的。
相比之下如果使用纯文本的格式保存，则可以保证这个星球上的任何计算机都能无碍打开编辑，没有盗版软件，不用预装笨重的office套件，完全自由了。
可以使用版本管理软件进行管理
没错我说的是git，配合github使用效果更佳。
git是程序员开发的一套给程序员用的管理代码的工具，上可以针对你对文件做的每次修改进行跟踪和保存，不高兴或者写废了可以轻松回到之前的版本，再不用自己手动分出版本1 2 3 4 5。
代码是纯文本格式的，你的文章也是，git能管理代码自然也能管理文章。当然我是试过用git来管理word文档的，但.doc文档直接采用二进制保存 ...
在ubuntu上编译中文latex文档
tex大名不再多说，作为需要编译的文档，外加原生不支持中文这样的设定，给人感觉难用是正常的。今天咬咬牙看了些资料，发现在前人的努力下编译中文已经是很简单的事情了，虽然原理依旧复杂，需要注意的地方依旧很多。
具体的解决方案为XeLaTeX + xeCJK + ctex。
在windows平台下还是建议使用ctex套件，该套件把引擎编辑器等等东西一起打了包，一次安装无痛使用。
linux下面则因为字体配置方案不统一的问题需要一些配置，下面是具体方法。
texlive
后端推荐使用texlive2012，可以找一个光盘镜像挂载起来，在挂载目录下直接
sudo ./install-tl
注意安装完成以后根据提示往.bashrc里面添加一下环境变量
export PATH=/usr/local/texlive/2012/bin/x86_64-linux:$PATH
export MANPATH=/usr/local/texlive/2012/texmf/doc/man:$MANPATH
export INFOPATH=/usr/local/texlive/2012 ...Linux安装gsl库
用python做计算，虽然优化花了很大功夫，但速度仍旧不够理想，所以我又开始学习c语言了。c本身并不以计算能力见长，但运行效率没问题，相关的库也很完善，平常能用到的都有涉及，这里记录一下gsl（GNU scientific lib）的安装和配置过程。
下载安装
因为是开源库，直接在官网下载就好，只有几兆，体积不大。
我选了最新的版本，得到了一个压缩包gls-1.16.tar.gz
老规矩，先解压，再进解压目录
$ tar zxvf gsl-1.16.tar.gz
$ cd gsl-1.16
接下来是安装的常规流程，值得注意的是默认安装目录为/usr/local/include和/usr/local/lib，这个先记住，随后有用。我在服务器上装了一遍 ...