Author: David

寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王” 题目描述： Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？ 首先，我们可以假设有这样一个数据结构来表示帖子 [cpp] type struct post { char* title; char* content; int uid; }post_t; [/cpp] 题目告诉我们已知所有帖子的列表，也就是说我们知道了所有帖子的链表 post_t*　post_list，或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少，并且该uid一定超过了总和的一半。为了叙述方便，下面用数组举例。最容易就想到的方法，就是遍历整个数组，记录每一个uid出现的次数，然后再比较一下，求出最大的。 其实，这个问题就可以等价于：求数组中出现次数大于一半的那个数 解法一 对数组排序，然后遍历排好序的数组，统计各ID出现的次数，找到超过一半的那个即可。代码如下： [cpp] int Find (int* post, int len) { sort(post, post + len); int num = 1; for(int i = 0; i < len; i++) { if(post[i] == post[i + 1]) num++; else num […]

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数 题目描述：对于一个字节（8bit）的无符号整形变量，求其中的二进制表示中“1”的个数，要求算法的执行效率尽可能的高。 书中由浅入深地给出了几种解法。 解法一 也是最容易想到的，因为对于无符号整数，若采取对2取余操作，结果只有两种，奇数余1，偶数余0，而奇数的二进制最后一位为1，偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果，以二进制数1011和1100举例： 1011 对2取余，余数为1，二进制末尾为1，即含有一个1 1100 对2取余，余数为0，二进制末尾为0，即含有一个0 不管这个二进制数的高位有多少个0或者多少个1，对2取余的操作只与最低位相关。所以，如果能够把所有的位都作为最低位，对2取余一次，然后将结果相加，即可得到该题答案。而二进制数中，右移操作，就相当于除以2，所以有了以下解法。 [c] unsigned int Count (unsigned int x) { unsigned int num = 0; // the result while(x) // end of loop when x is 0 { if(x % 2 == 1) // to judge whether the last bit is ‘1’ { num++; } x = […]

读《怀才纳贿的“二皇帝”和珅》

和珅（1750～1799,清朝人，钮祜禄氏），权臣，豪商，巨贪。 读这本书并不是因为什么“读史可以明智”，还达不到那个境界。“以史为鉴”倒还是不错的。 读这本书是因为最近开始对历史有些感兴趣，恰巧在书店转的时候，又被它诙谐的语言，文学的形式所吸引，离开的时候也就带上了。从来没见过一本史书可以这样写，让人读起来毫不费力，有一些像小说。 本书从和珅出生，到求学，到考公务员（是的，原书写的就是考公务员），再到后来的官场沉浮，一直写到乾隆驾崩以后势力的迅速没落，最后上吊自杀。全方位、多角度地展示了一个真实的和珅，一个有血有肉的和珅。 此前，接触和珅最多的则是从电视上——《铁齿铜牙纪晓岚》，一部饱受争议的电视剧，最大的争议点当然还是不符合历史。其实大可不必纠结，电视剧本来就是用来消遣的，君不见广大抗日神剧中，八路军小战士手撕日寇么，难道这也要去算一算作用力与反作用力？ 再说和珅，王刚先生之所以把和珅演的惟妙惟肖、脍炙人口，不是因为多像历史的和珅，而是因为多像剧本。试问，你见过哪个电视剧的反面能演到如此让人又爱又恨看不到又想的程度么？王刚的和珅，走的是“戏饰和珅”的感觉。结合剧本的语境词境意境，将和珅一角色表达的生动活泼惟妙惟肖。 只是，和珅真不是一个大胖子啊，王刚先生。 据广大史书记载，和珅是一个美男子，而在不是以肥为美的大清，我觉得，和珅应该不会是一个胖子。 回到书中，给我印象最深的，除了和珅的干女婿刘国泰借银填仓那一段（因为最近发生的黑龙江火龙烧仓事件，实在是很难让人不起联想），就是和珅对夫妻、兄弟、朋友之前感情的珍视了，他也有他善良的一面。不过好像上天并不眷顾他们家，在各自前途最光明的时候，都相继死去，以致最后的描写的和中堂都有点让人惋惜的感觉。 如果你还没读过这本书，也碰巧想了解一下中国史上第一贪的话，可以试着读一读。走近和坤跌宕起伏、颇具戏剧色彩的人生，无疑也能让你对人性、对历史有更多的体会。 2013-7-17 于 北京

MySQL 插入错误

MySQL insert error。。。。。。。。   一条简单的SQL语句，竟然插入错误： INSERT INTO USER （id, describe） VALUES (‘David’, ‘diudiu’); 咋一看确实没错啊，瞅半天才发现，是由于table中有字段名是MySQL的保留字。这里就是‘describe’，报错也就理所当然了。 解决办法： 在关键字的地方加上反引号”`”，就是键盘1旁边的那个字符。 MySQL就是通过添加反引号来区别保留字。 上述修改为 INSERT INTO USER （id, `describe`） VALUES (‘David’, ‘diudiu’); 即可。    

Linux 下 C++ 连接 Mysql

——国外有一篇博客写得挺好，有一些小错误，改正以后翻译过来，发这里了。 C++是一个效率非常高的编程语言 Linux 是一个类Unix操作系统，它促进了开源软件社区的发展，并且用这些开源软件就几乎足以构建一个复杂精妙的企业系统。 MySQL是一个流行的多线程、多用户的数据库管理系统，全球有超过1000万的安装量。   这篇文章将演示如何在Linux下用C++连接MySQL。 首先我们需要将所需要的头文件和库全部包含进来 #include <stdio.h> #include <mysql.h> 然后我们来定义一下main函数 int main() { // code  return 0; }; 然后我们定义一下需要用到的变量，你应该将这些写到main函数里去。 MYSQL_RES *result; MYSQL_ROW row; MYSQL *connection, mysql; int state; 既然要使用MySQL数据库，我们首先就得连上它，使用下面的代码即可： mysql_init(&mysql); connection = mysql_real_connect(&mysql,host,usr,pswd,database,0,0,0); 其中 host – 数据库所在主机的名字，比如 “localhost” 或者 “192.168.250.100” usr – 连接数据库时使用的用户名 pswd – 连接数据库时使用的密码 database – 数据库的名称 如果有错误发生，如用户名/密码不匹配，我们可以通过以下代码获取到错误信息： if (connection == NULL) { printf(“%s\n”, […]

Paper things

在线考试系统功能需求以及数据库定义 由于是技术说明文档，就不再叙述背景以及国内外现状等。 在线考试系统模块需要实现的功能在这里分传统题目考试、程序题目在线判定（Online Judgement）两大部分叙述。 一：传统题目部分 对于题库： 1. 能够添加多种题型（单选、多选、判断、填空、简单等） 2. 能够添加多种题目分类（如“计算机基础“，“管理“），并支持子类父类（如”C语言” 属于 “计算机基础”） 3. 对于每一种题型，能够添加试题 4. 对于每一道试题，有正确率统计，便于出题的时候进行难度判断 5. 对于每一道试题，能够指定属于哪一分类 6. 对于每一道试题，除了设置答案以外，还需有答案解析，便于实现以后某些功能需求（如某些考生看不懂答案）。 对于试卷： 1. 能够设置试卷的名称、分类等（分类参考题库模块的分类） 2. 能够直接从题库里提取试题，组成试卷 3. 组卷选题过程中支持重复性检测，以及难度提示（根据题库中题目的正确率等作为参考） 4. 支持相同题型不同分数（即可根据难度设置分数，参考高考理综考试） 5. 能够查询某一时间段里出的试卷（如今年期末考试出题想参考1999年的试卷） 对于考卷： 1. 能够将试卷的题目乱序以后组成考卷 2. 维护考卷的基本信息 3. 记录考卷中每一道题的正误（题库中题目的正确率来源于此） 4. 支持缓冲。由于对于每一次考试，有多少考生参加就有多少张考卷，如果对每一道题都访问数据库，会由于频繁反问造成系统效率不高，所以需要提供缓冲机制。 5. 支持到时间收卷 对于考生： 1. 维护考生的基本信息 2. 考生作为与外界系统的主要接口，将其他系统的用户与在线考试系统联系起来，所以在该系统中，考生参加考试一律只使用考生编号。 总体草图 对于数据库： 1.  由于在该系统中会涉及到较多的事务处理，所以讲数据库引擎采取ENGINE = InnoDB模式 2.  数据库表如下图所示。 具体每个字段代表什么，以及具体的SQL创建语句已经在“数据库创建语句.sql”里详细列出，这里给出对于某些数据库表的解释： […]

PHP调用C/C++动态链接库

摘要 有时候，单纯依靠 PHP “本身”是不行的。尽管普通用户很少遇到这种情况，但一些专业性的应用则经常需要将 PHP 的性能发挥到极致（这里的性能是指速度或功能）。由于受到 PHP 语言本身的限制，同时还可能不得不把庞大的库文件包含到每个脚本当中。因此，某些新功能并不是总能被顺利实现，所以我们必须另外寻找一些方法来克服 PHP 的这些缺点。 了解到了这一点，我们就到了应该接触一下 PHP 的心脏并探究一下它的内核——可以编译成 PHP 并让之工作的 C 代码——的时候了。 概述： PHP调用动态链接库几个必要步骤为： 1. C/C++编写动态链接库,编译打包成.so文件 2. 初始化一个新的PHP扩展 3. 配置、编写PHP扩展内容，在扩展中使用C/C++调用.so 4. 编译并添加PHP扩展 5. 在PHP应用中直接调用PHP扩展里暴露出来的API 为了从能运行的最简单的例子开始，所以下面的叙述可能不会严格按照上面列的步骤来写，也有可能会重复穿插着写。但总体顺序是一致的。 一. C/C++编写动态链接库,编译打包成.so文件 如果还不会用C++调用自己写的.so库，请参考我的这篇文章： http://keping.me/cpp_invoke_so/ 文中从什么是Name Mangling开始，到如何用调用一个包含简单函数的so库，再到如何从so中加载类，都有详细叙述，并附有可运行示例代码。 二. 初始化PHP扩展 本文中，我们将创建一个叫“vehicle”的PHP扩展，其中包含一个“Car”类。 将要创建的扩展会涉及到以下文件需要修改，这些文件将会出现在vehicle目录下。后面会一一叙述这些文件是怎么来的，现在只是大致了解一下。 car.h —— 包含了C++写的类，即Car的定义 car.cc —— Car类的具体实现 php_vehicle.h —— 包含了PHP创建扩展所需要的一些头文件，外部变量定义等。 vehicle.cc —— 扩展的主要源码文件，这里面会调用到Car类 config.m4 —— PHP扩展的配置文件 1. […]