分类: 2009 December

二进制的妙用

[题目1] 5个人参加网球单打比赛,比赛采用淘汰制,引入轮空制度,问为了决出冠军,一共需要进行几场比赛?

[分析] 这么简单的题目连分析都用不上了,画图如下,红线表示进行了一场比赛,橙色实心圆表示轮空,答案明显是4.

binary-godorz[题目2] 当题目中的5人变成79人时,需要进行几场比赛呢?

[分析] 你是否还在画图呢?其实题目1的分析有不弱的诱导性.把参赛队员想成整数,决出冠军可以看作是从79个整数中找出最大值,需要79-1=78次比较,因此答案为78.

上面的两道题目的确是很容易的,现在把题目修改如下:

[题目3] 5个人参加网球单打比赛,比赛采用淘汰制,引入轮空制度,问为了决出冠军,一共需要几次轮空?

[分析] 5不是什么大不了的数字,画图给出得到答案,但是,当将5改成n之后,你还能给出答案吗?其实,这道题在Knuth的名著The Art of Computer Programming中有专章论述.下面给出一种求解方法:

令2k<n<=2(k+1),则答案为2(k+1)-n二进制表示中1的个数.

是不是有点不相信自己的眼睛呢?下面给出证明:

记人数为n时需要的轮空数为f(n),则:

f(2)=0;
当n>2时,

  • 如果n为偶数,那么f(n)=f(n/2)
  • 如果n为奇数,那么f(n)=1+f((n+1)/2)

将上面两个式子统一为f(n)=s0+f((n+s0)/2),n为奇数时,s0=1;n为偶数时,s0=0.

subtles-of-binary-1

又因为不管n初始为多少,最终会规约到n=2的情况,即式子A:

subtles-of-binary-2

因为f(2)=0,所以有式子B:

subtles-of-binary-4

由式子A得式子C:

subtles-of-binary-3

可以看出,式子B的值为式子C 中2的0次幂到k-1次幂的所有系数和,而2的0次幂到k-1次幂之和为2(k+1)-n,因此式子B的值为2(k+1)-n二进制表示中1的个数.(请仔细思考!!!)

OK,到此我们已经看到了二进制的能耐了.其实二进制还有很多很多方面的妙用,<Aha!Insight>上有详细的介绍,如果你闲着没事干的话,可以抽出几个钟好好看看.我本想在这里介绍的,可惜这里已经有人写过了.郁闷…

Ps: 悲剧了,wordpress不支持LATEX,画个公式还得转成图片,一不小心还把版式都弄得这么难看..

Ps2: 衡量在三,还是把人家转载文章的链接给出来了,虽然这里也注明了是整理得来的,但是给出原文的真正出处总是最好的.在cn就是这么无奈,随便一篇文章都难找到原作者.

[Update 2009-12-19] 图片设置成初始大小了.

递推

我们很常遇到这么一类问题:给出地图,问从起点A到终点B的最短路径.图论里有好几种解决这类问题的算法,比如说Dijkstra算法,它是一种退化的A*算法(h永远为0),每次取g最小的结点进行扩展,为了提高算法的效率,你可以使用最小堆.

但是,有的时候,我们会遇到一类看起来简单得多的问题:地图分为m行n列,从左上角到右下角最短路径有几种走法.

perplexing-paths-1

这其实是组合学中最最基础的入门例子,因为要求路径最短,所以我们只能向右走,或者向下走,向右需要走n+1步,向下需要走m步,一共需要走m+n+1步.向右走和向下走的次序即便被打乱,我们仍旧一定能够以最少的步数走到终点,因此只要从m+n+1步中选出n+1步向右走,向下的m步就被确定了.所以,最短路径的走法一共有C(m+n+1,n)种.

当然,这是假定地图m行n列是对齐的条件下得出的结论.下图中,根据前面的结论,从A到B的最短路径一共有C(2+3+1,2)=15种走法,而实际上,走法只有13种.请仔细思考,为什么组合论的方法在这里会失效呢?(答案见文末)

perplexing-paths-2

下面给出一种不同于组合论的方法.如下图所示,从A出发到结点C和D,F的走法为1.从A到E的最少步数走法有2种:A->C->E或者A->D->E.从A到G的最少步数走法有3种:A->D->F->G,A->C->E->G,A->D->E->G,注意到2=1+1,3=2+1,你会否有种下意识的觉悟.多年的数学学习告诉我们,由数学归纳法知,记从结点A到结点t最少步数走法有f(t)种,令t的正上方结点和正左方结点分别为t1,t2,则f(t)=f(t1)+f(t2).

perplexing-paths-3当t1不存在时,f(t1)=0,t2同理;为了看得更具体一些,不妨画出示意图如下:

perplexing-paths-4

这里的递推思维看起来很简单,其实它是很巧妙的.为了求得某一状态,先求出该状态的所有前驱状态,由状态之间的转化关系求得最终结果.如果你觉得你还没有掌握其中的想法,也许你可以自己画出一些奇形怪状的地图,然后按照递推的思维进行求解.

最后,给出一道题目:

[题目] Arthur要上楼梯,楼梯一共有15阶,Arthur每次可以走1阶或者2阶,问他一共有多少种走法.

[分析] 什么都不说了,直接给答案: f(n)=f(n-1)+f(n-2)

PS: 上面为什么组合论的方法失效呢?因为组合论在故规则的地图里出现了重复状态.

Linux下配置C/C++连接Mysql

Mysql是数据库中的主流,因此我一直以为在Linux下配置会很很容易,结果Google了大半天,大部分网页只说了如何安装Mysql之类的废话,对如何使用C/C++连接Mysql却只字不提,或者提的方法也根本不可用.下面列出一种可行的方法,我用的是Ubuntu,其他发行版应该也大同小异.参考文章在这里.

安装Mysql

1.首先安装Mysql服务器

sudo apt-get install mysql-server

2.然后安装客户程序

sudo apt-get install mysql-client

3.启动服务器

sudo /etc/init.d/mysql restart

4.当服务器启动之后,你可以使用netstat命令来查看服务器的运行情况

sudo netstat -tap | grep mysql

5.既然服务器已经启动了,我们登录进去看看吧

mysql -u root -p

其中,root为默认的Mysql数据库管理员账户,回车之后应该输入密码,相信密码在安装时你已经设置过了,如果你没设置的话,默认密码为空,因此直接敲回车就可以了,或者还有一个默认密码是db_user_password.

6.下面的命令是用来修改密码的

sudo mysqladmin -u root password newpassword

进了Mysql之后,你可以拿本诸如Mysql宝典之类的书练练手了.

在Linux下使用C/C++链接Mysql

1.安装必需的开发包

sudo apt-get install gcc g++ libgcc1 libg++ make gdb

2.安装Mysql的C语言开发包(放心,C++一样用的)

sudo apt-get install libmysql++2c2a libmysqlclient15-dev libmysqlclient15off libmysql++-dev

3.把lib文件复制到库里

sudo cp /usr/lib/mysql/* /usr/lib/

现在,你已经可以使用C/C++链接Mysql了,但是,接下来你必须接受一个残酷的事实,以后编写C/C++程序时,你必须包含mysql.h文件

#include “/usr/include/mysql/mysql.h”

4.而且,要编译文件,你只能在命令行下敲下如下代码

g++ src.cc -o src.out -L/usr/lib/mysql -lmysqlclient -lz

如果习惯性地用IDE编译,估计你的console窗口会被出错信息淹没.网上传言说,可以在Makefile的LIBS尾部加入-L/usr/lib/mysql -lmysqlclient -lz,我试过了,但没成功.或者你可以试试.

5.运行C/C++程序

sudo ./src.out

测试

1.这里是我的 一个数据库,下载并且解压缩

wget http://godorz.info/wp-content/uploads/2009/12/mysql.tar.gz && tar -zvxf mysql.tar.gz

2.导入数据库

mysql -u root -p newdatabase < back.sql

3.编译C++源文件(记得将源文件里的user和password修改为你的数据库用户名和密码)

g++ main.cpp -o src.out -L/usr/lib/mysql -lmysqlclient -lz

4.运行C/C++程序

sudo ./src.out

如果终端输出一串人名清单,恭喜你,你已经成功使用C/C++连接Mysql了.如果不成功,点我可以帮你,MM优先.

最后,送上某神牛制作的vim图一份,对这它码了这篇文章,暴爽..这是我以前做的vim桌面,相形见绌.

因为编写搜索引擎的需要,必须将下载得到网页之后写入数据库,目前主流的数据库是Mqsql,本以为在Linux很容易就可以配置完了,结果Google了大半天.下面列出我的配置方法,我用的是Ubuntu,其他发行版应该也大同小异.
1.首先安装mysql服务器
sudo apt-get install mysql-server
2.然后安装客户程序
sudo apt-get install mysql-client
OK.该安装的目前为止已经够了.
3.启动服务器
sudo /etc/init.d/mysql restart
4.当服务器启动之后,你可以使用netstat命令来查看服务器的运行情况
sudo netstat -tap | grep mysql
5.既然服务器已经启动了,我们登录进去看看吧
mysql -u root -p
其中,root为默认的mysql数据库管理员账户,回车之后应该输入密码,相信密码在安装时你已经设置过了,如果你没设置的话,默认密码为空,因此直接敲回车就可以了,或者还有一个默认密码是db_user_password.
6.下面的命令是用来修改密码的
sudo mysqladmin -u root password newpassword
进了mysql之后,你可以拿本诸如mysql宝典之类的书练练手了.
如果你有空的话,不烦按照这篇文章把代码敲了(后面会用到)
1.接下来谈谈如何在Linux下使用c/c++链接mysql,首先安装必需的开发包
sudo apt-get install gcc g++ libgcc1 libg++ make gdb
2.然后安装Mysql的C语言开发包(放心,C++一样用的)
sudo apt-get install libmysql++2c2a libmysqlclient15-dev libmysqlclient15off libmysql++-dev
3.然后把lib文件复制到库里
sudo cp /usr/lib/mysql/* /usr/lib/
现在,你已经可以使用C/C++链接Mysql了,但是,接下来你必须接受一个残酷的事实,以后编写C/C++程序时,你必须包含mysql.h文件
#include “/usr/include/mysql/mysql.h”
4.而且,要编译文件,你只能在命令行下敲下如下代码
gcc -g test.c -o test -I/usr/include/mysql -L/usr/lib/mysql -lmysqlclient
如果习惯性地用IDE编译,估计你的console窗口会被出错信息淹没.网上传言说,可以在makefile的LIBS尾部加入-L/usr/lib/mysql -lmysqlclient -lz,我试过了,但没成功.或者你可以试试.
Ok
:wq