存档: 2009 December

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

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

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

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

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

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

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

令2^k<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)=s₀+f((n+s₀)/2),n为奇数时,s₀=1;n为偶数时,s₀=0.

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

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

由式子A得式子C:

可以看出,式子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不支持L^AT_EX,画个公式还得转成图片,一不小心还把版式都弄得这么难看..

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

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

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

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

这其实是组合学中最最基础的入门例子,因为要求路径最短,所以我们只能向右走,或者向下走,向右需要走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种.请仔细思考,为什么组合论的方法在这里会失效呢?(答案见文末)

下面给出一种不同于组合论的方法.如下图所示,从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).

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

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

最后,给出一道题目:

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

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

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

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桌面,相形见绌.