一 01
转眼又过了一年，现在已经工作了。博客好久不更新了，刚开始是因为找工作比较忙，后来就慢慢忘记了。现在工作大概有半年了，工作不是很辛苦，自己也会抽时间学习点东西，也会记录一些学习的笔记，但是和博客的内容相比还是差了好多，很多都缺乏整理。很多知识都在于整理，整理的过程也是重新学习，更新认识的过程。
在新的一年里，我将会努力学习新知识，充实自己，坚持写博客，记录自己的学习历程（呵呵，希望能坚持吧~~~）。另外也祝大家在新的一年里，生活多姿多彩，工作一帆风顺 ^_^
九 01
长久以来一直对递归一知半解。最近看面试方面的书，在数据结构中有很多算法是和递归有关的，另外一些经典问题：打靶问题、8皇后问题、0-1背包问题也和递归有关，在有些算法中递归甚至是必不可少的，因此很有必要把递归算法再重新学一下。
首先说一下递归和迭代的区别。迭代是反复的意思，有时候也指重复执行和反复执行。迭代一般是通过循环执行一组指令，并且在每次执行后都会从变量的原值推出它的新值。迭代往往需要一个迭代表达式，如f(n+1)=f(n)+f(n-1)。大家可以看出递归中的经典案例N！也可以通过迭代来做，而且更高效（因为迭代相比递归一般要高效很多）。
下面就来谈递归。递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。文[1]中对于递归讲解比较细致，大家可以参考。下面展示两段代码[1]：
返回一个二叉树的深度：
int depth(Tree t){
if(!t) return 0;
else {
int a=depth(t.right);
int b=depth(t.left);
return (a>b)?(a+1):(b+1);
}
}
判断一个二叉树是否平衡：
int isB(Tree t){
if(!t) return 0;
int left=isB(t.left);
int right=isB(t.right);
if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)
return (left<right)? (right +1) : (left + 1);
else return -1;
}
第一个算法还是比较好理解的，但第二个就不那么好理解了。第一个算法的思想是：如果这个树是空，则返回0；否则先求左边树的深度，再求右边数的深度，然后对这两个值进行比较哪个大就取哪个值+1。而第二个算法，首先应该明白isB函数的功能，它对于空树返回0，对于平衡树返回树的深度，对于不平衡树返回-1。明白了函数的功能再看代码就明白多了，只要有一个函数返回了-1，则整个函数就会返回-1。（具体过程只要认真看下就明白了）
对于递归，最好的理解方式便是从函数的功能意义的层面来理解。了解一个问题如何被分解为它的子问题，这样对于递归函数代码也就理解了。这里有一个误区（我也曾深陷其中），就是通过分析堆栈，分析一个一个函数的调用过程、输出结果来分析递归的算法。这是十分要不得的，这样只会把自己弄晕，其实递归本质上也是函数的调用，调用的函数是自己或者不是自己其实没什么区别。在函数调用时总会把一些临时信息保存到堆栈，堆栈只是为了函数能正确的返回，仅此而已。我们只要知道递归会导致大量的函数调用，大量的堆栈操作就可以了。
下面介绍和递归密切相关的算法：回溯算法。回溯算法是一种搜索算法，它可以通过对问题从一个状态出发，搜索从该状态出发的所有状态，当一条路走到尽头时，再后退一步继续搜索，直到所有路径都试探过。回溯算法通常由递归来实现，因为递归结束时会返回调用处（上一步），回溯结束时也是返回上一步，两者可以很好的契合。文[2]中对于回溯的讲解挺详细的，大家可以参考下。这里引用文中的一段话，我觉得写的挺好的：“通过把递归结束的条件设置到搜索的最后一步，就可以借用递归的特性来回溯了。因为合法的递归调用总是要回到它的上一层调用的，那么在回溯搜索中，回到上一层调用就是回到了前一个步骤。当在当前步骤找不到一种符合条件情况时，那么后续情况也就不用考虑了，所以就让递归调用返回上一层（也就是回到前一个步骤）找一个以前没有尝试过的情况继续进行。当然有时候为了能够正常的进行继续搜索，需要恢复以前的调用环境。”。下面通过一个例子来介绍递归回溯的实现
楼梯问题：假设一个楼梯共有10级台阶，一个人可以选择一次走1级或2级台阶，请问总共有多少种不同走法？
这个问题是之前一个师兄跟我说的，当时考虑了好久也不得其解，现在通过递归回溯算法来解决它。具体代码如下：
#include <iostream>
using namespace std;
const int STAIRS=10;
const int MAX_STEP=2;
int result_number=1;
int steps[STAIRS];
void print_result(){
cout<<"This is the "<<result_number++<<" result: "<<endl;
for(int i=0;i<STAIRS;i++){
if(steps[i]==0){
break;
}
cout<<steps[i]<<" ";
}
cout<<endl;
}
void do_step(int stairs,int step_number){
if(stairs==1){
steps[step_number]=1;
print_result();
steps[step_number]=0;
steps[step_number-1]=0;
return;
}
else if(stairs==0){
print_result();
steps[step_number-1]=0;
return;
}
else{
for(int i=1;i<=MAX_STEP;i++){
if(stairs-i<0){
break;
}
steps[step_number]=i;
do_step(stairs-i,step_number+1);
}
}
}
int main(){
cout<<"the program started..."<<endl;
do_step(STAIRS,0);
cout<<"there are "<<result_number-1<<" results."<<endl;
}
do_step函数的功能是：当执行时如果参数stairs为1，或0，则直接输出结果，并且把steps[]恢复到上一步的状态，退出函数。如果stairs大于1，则尝试分别走1步和2步，此后问题转化为原问题的子问题。明白了函数的功能就很容易看懂代码了。该函数中出现了for循环嵌套 递归的情况，大家只要认为是多次执行其中的代码就可以了（那个我们不理解的复杂的函数堆栈调用关系可以正确无误的实现我们要求的函数调用，呵呵）。程序会列出每个结果，总的可行走法共89种。
大家了解了回溯算法后就可以解决一大类问题了，包括上面说的打靶问题、8皇后问题等。大家也可以尝试通过回溯算法来解决“数独”问题，通过搜索来查找可行的数独解（也算是个小小的挑战吧，^_^）。
参考资料：
[1] 漫谈递归思想 http://www.cnblogs.com/BLoodMaster/archive/2010/03/23/1692641.html
[2] 递归回溯总结 http://hi.baidu.com/sulipol/blog/item/32411851bb9724551138c2eb.html
[3] 《程序员面试宝典》第8章 循环、递归与概率
八 09
最近一段时间一直在准备着找工作，学各种东西。期间还是感觉很有收获的，等有时间整理一下然后发布出来。实验室的项目也还在进行，不过我的工作相对少了很多（因为快要毕业了嘛，还是很感激老师能体谅我们的，^_^）。
目前我在项目中的任务是做一个系统的图形界面。当初也不知道怎么想的，竟然想用web形式来实现，也许是为了不让自己之前学的ruby和rails不要白费吧，呵呵。现在想想Web GUI的想法的确挺好的，由于ruby的类库丰富，开发相对还是比较轻松的，不过为了让C++系统和rails的能正常交互消息还是需要学一下http类库libcurl方面的知识（这些知识它的官网上有很多，也很详细）。
由于项目的需要，我们的图形界面上需要显示一些数据的分析图表，使用ruby的gruff工具包可以绘制很好的数据分析图表。下面说下linux环境下gruff的安装和使用，安装过程如下：
1、首先安装ruby-1.8.6环境以及ruby gems，大家可以在网上找相关的教程。
2、安装ImageMagick的库，gruff的运行依赖于这些库
yum install ImageMagick yum install ImageMagick-devel
3、安装TrueType字体。ImageMagick在画图时需要用到这个库。有些linux版本会默认安装，那样的话大家就可以跳过这步了
wget http://www.osresources.com/files/centos-windows-fonts/msfonts.tbz mkdir /usr/share/fonts/default/TrueType tar xvjpf msfonts.tbz -C /usr/share/fonts/default/TrueType/
4、安装 rmagick 的gem包
gem install rmagick
5、安装gruff所需的gem包。gruff包会依赖以下包：json_pure、rubyforge、hoe、rake
gem install gruff
至此gruff就安装完成了。下面介绍一个gruff的代码实例，实例中会绘制一个柱状图，其他类型的图的画法请参考gruff的rdoc文档。
示例代码如下：
require 'rubygems'
require 'gruff'
g = Gruff::Bar.new(600) # The graph will be 600 pixels wide.
g.bar_spacing = 0.5 # the bars' space
g.title = 'The Nodes\'s Load'
g.theme_37signals # The best-looking theme, in my options.
load_info_1=[21,3,6,14,7,11,19] #the data information, you can use you own data here.
load_info_2=[8,27,13,4,9,14,10]
range = (1..7)
g.data('Node 1', range.collect { |x| load_info_1[x-1] })
g.data('Node 2', range.collect { |x| load_info_2[x-1]})
g.labels = {2 => 'n=2', 4 => 'n=4', 6 =>'n=6' }
g.write('load_info_bar.png')
输出结果图片如下：
可以看出，gruff生成的图片还是挺漂亮的。我这里的数据是自己任意写的，没什么实际的意义。
PS：我个人还是很喜欢Ruby语言的，它的语法优美，代码看起来很像伪代码，很易读；它有丰富的类库，对文本处理的功能很强。大家如果想学一门脚本语言的话建议学习Ruby，可以很好的提高你的工作效率，呵呵
参考资料：
[1]http://hi.baidu.com/rainchen/blog/item/089ef7364497de320a55a9a3.html
[2] Ruby Cookbook: Recipe 12.4. Graphing Data
七 01
鼓捣了好久wordpress主题，发现还是最开始的主题比较好。之前换其他主题主要是因为文章栏太窄了，当显示前面的游戏的时候显示不完整。之后在网上下了很多别人推荐的主题，包括Stripey、BlackGelly、Manly、pyrmont等，这些主题初看起来的确不错，漂亮的外观和字体，但当真正使用时才发现各种问题。因为我的blog现在装了很多插件，如代码显示还有评论表情，嵌套评论等，当采用新主题时，要么插件不能使用，要么显示错误。而且这些主题也有不同的缺点，页面的边栏中的内容要么太少，要么太多。
现在才明白，真正好用的主题还得自己动手改。自己花了段时间对页面的布局进行调整，主要是修改背景图片和css样式。幸运的是在网上找到了这个主题的头部的图像的psd文件，可以方便的对图像进行缩放等简单的修改而不损失图像质量。我现在的主题是glossyblue，最初在yo2的时候也是用的这个主题。目前安装的插件如下：
- Akismet :用来抵制垃圾评论的。装上这个插件后垃圾评论少了好多，我的邮箱也清净好多。
- Custom Smiles：用来评论中使用表情的，挺好用的
- Add From Server：用来往wordpress中上传文件的，比wordpress自带的上传工具要好用得多
- Syntax Highlighter and Code Prettifier Plugin for WordPress :用来显示代码的插件，这个插件的功能还是比较强大的，可以支持各种语言，c/cpp, bash、java、ruby等
- Wordpress Thread Comment ：由于我的主题自身不支持嵌套评论，所以用了这个插件
- WP SlimStat ：wordpress的统计工具，可以统计博客的访问量，有哪些页面比较流行，访问者所用的浏览器，最近的关键词等，信息很多，很好用
另外推荐一个网址 一些不错的WordPress主题下载站 ，上面有好多很好的主题，大家可以根据自己的需要修改。大家如果有什么关于WP主题的问题或意见欢迎交流。
PS：最近在试用Windows Live Writer，一个wordpress的离线编辑器，目前感觉还是挺好用的，大家也可以试试。。。
四 07
现在终于有自己的网站了，以后会一直用这个网址了，呵呵。之前的yo2的网站后来被GFW了，虽说数据现在恢复过来了，但弄的也挺郁闷的，现在再也不用担心这个问题了。再此要感谢我的小学弟，要不是他的帮忙不知道要花多久网站才能运作。
下面简单记录一下建站的过程，方便有兴趣建站的朋友。建立个人网站需要有自己的域名和空间。
1、域名的申请在国外申请比较方便，我是在www.godaddy.com上申请的，而且可以马上开通。当然了，申请之前你要保证这个域名没有被用过，可以通过www.whois.com来查询该域名是否已经有人注册了。（如何起域名就看个人的水平了，我的水平也不是很高，呵呵）
2、申请个人的空间，我个人是购买的布置在国外的个人主机，网上有很多提供合租主机服务的站点，大家可以在网上搜一下，我是用的www.gegehost.com的主机，据说挺好用的。
3、获得空间后可以看到远程主机的ip地址，然后进入www.godaddy.com 的网站，然后进入个人域名的管理，然后把域名绑定到这个ip就可以了。
4、最后就需要在远程的主机上建立相应的数据库，上传wordpress安装程序，然后安装好wordPress就可以了（wordpress的安装可以参考网上的教程，注意一点就是编辑config文件时请用高级点的文本编辑器，不要用记事本）。
远程主机的功能很强大，基本可以和在本地操作文件一样方便，可以实现文件的移动、复制、删除、压缩、解压等。数据库的操作也比较简单，也有phpMyAdmin等工具可以使用。
建站容易维护难啊，呵呵，希望自己能认真做好维护工作吧。。。
十一 24
最近项目的程序完成部分代码，需要进行测试，由于测试需要好几台主机才能进行，由于设备限制，我就先把程序在Elastix Linux（我们实验室服务器的linux版本）和我自己的fedora7下进行测试。在Elastix下可以编译通过，但是在程序运行时一旦收到消息开始处理，程序就会崩溃，并且反馈为 glibc detected *** : free(): invalid pointer 错误。但是因为我在fedora7下该程序可以正常接收和处理消息，当时只是认为是操作系统的问题，也没有太在意。
今天好不容易装好了几台测试电脑，都是fedora系统的，本来打算晚上把测试的程序装上，然后就OK了，应该不会有什么错的。没想到当在多个fedora下运行该程序进行测试时，对于前面几条消息程序还是可以正常处理的，但是当处理到3，4条消息的时候程序开始提示上面的同样的错误。当时自己花了很长时间来找原因，程序的配置改了又改，但还是没有解决，整的也很郁闷。晚上回去后又继续调试，用gdb加载程序，当程序退出后，查看程序的堆栈信息（输入bt）命令，经过几次尝试后终于发现错误的所在，原来是自己当时初始化一个字符串时分配的空间太小。有点像下面这样：char tempString[MAX_LENGTH]; tempString[length]=0;但是在程序中没有检查length的大小，如果length>=MAX_LENGTH时就会出现上面的错误。然后修改程序后就一切正常了。
看来在程序的世界里没有偶然，只有必然，当程序出错时很可能就是你程序错了，不要报有侥幸的心理，专心的找出错误的根源才是王道 :D
Recent Comments