博文
数独计算器(2006-12-06 23:02:00)
摘要：前一段时间写的数独计算器,由于代码太长,这里只贴出算法思路和用到的功能函数,以及主函数.有感兴趣的可以向我索要完整的源代码.
/*
Name: 数独
Copyright: 自由软件
Author: goal00001111
Date: 02-12-06 17:00
Description: 版本号3.0 对2.0版本进行了优化，使输出更合理，并能输出多个解
算法思想：1。利用不重复原理（即每个数字在每行，列，小九宫中只能出现一次），根据已确定位置，
排除与其同行，同列和同小九宫位置不能取的值。
2。根据完备性原理（即每个数字在每行，列，小九宫中必须出现一次），
若某个数字只能在某行，列，小九宫中的一个位置出现，则该位置的确定值就为该数字。
3。根据双隐数对方法，即同一行，列，小九宫中，若有两个位置都有且仅有两个相同的可能值，
则同一行，列，小九宫中的其他位置不能取该两个值。或在同一行，列，小九宫中，若某两个数字
存且仅存在于两个位置中，则这两个位置只可能取这两个值。
4。经过上面三个步骤以后，一般的数独题目都可以解决了。
若通过前面三种方法还不能确定全部位置，则调用杀手锏---穷举法。
因为经过前面三个步骤以后，未知位置已经不多了，而且未知位置的可能值也不多了，这时候只要
猜中某一个位置，则可能得到答案。
因此可以遍历所有未知位置，穷举某一个（注意不是每一个）位置的可能值，再由它得到其他位置的值，
如果出错或不能得到最终结果（确定全部位置），则分析下一个位置。
注意：这里不是采用回溯的方法----因为回溯所需空间太大，而是利用只要猜中某一个位置，
则可得到答案的原理，遍历所有未知位置。这样只需要一个辅助空间，花费很小。......
修剪花卉---一道竞赛题的解答(2006-12-06 22:59:00)
摘要：/*
Name: 修剪花卉
Copyright:
Author:
Date: 26-11-06 22:29
Description:
修剪花卉
内存限制：32M
问题背景：
ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。
一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。
于是当日课后，ZZ就向老师提出了这个问题：
一株奇怪的花卉，上面共连有N朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。
每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，
说明这朵花看着都让人恶心。
所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。
经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。
老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），
使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，
相当不爽，于是又拿来问你。
输入说明：
第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N朵花。
第二行有N个整数，第I个整数表示第I朵花的美丽指数。
接下来N-1行每行两个整数a,b，表示存在一条连接第a朵花和第b朵花的枝条。
输出说明：
一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。
样例输入：
7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7
样例输出：
3
数据范围：
对于60%的数据， 保证N≤1,000
对于100%的数据，保证N≤16,000
*/
/*
算法：先把所有的花进行分组，把连在一起的花合并到一组，那么问题就转化为求每一组中数据之和的最大值。
合并花的算法借鉴了连通问题。
*/
#include <iostream>
using namespace ......
折半算法示例集锦之一(2006-12-06 22:56:00)
摘要：折半算法示例集锦
例1：计算x的N次方(N>=0)。
常规算法，复杂度为O(N):
double Power(double x, unsigned int N)
{
double result = 1.0;
for (unsigned int i=0; i<N; i++)
result *= x;
return result;
}
折半算法，复杂度为O(logN):
double Power(double x, unsigned int N)
{
if (N == 0)
return 1.0;
double t = Power(x, N/2);
if (N % 2 == 0)
return t * t;
else
return t * t * x;
}
例2：静态查找问题，给定一个整数x和一个数组a，返回x在a中的下标，或者返回x不存在的标志。
如果x不止出现一次，则返回其中任意一个。
若数组a未经过排序，则我们只能对数组进行线性顺序查找，复杂度为O(N):
template <typename T>
int OrderSearch(const vector<T> & a, const T & x)
{
for (int i=a.size()-1; i>=0; i++)
{
if (a[i] == x)
return i;
}
return NOT_FOUND; //NOT_FOUND = -1;
}
若数组a已经经过排序，则我们可以使用折半查找，复杂度为O(logN):
template <typename T>
int Ord......
如何阅读源代码之四(转帖)(2006-12-06 22:51:00)
摘要：在parse_record分析完数据之后，做日期的分析，把日志中的月份等数据转换成机器可读（可理解)的数据，并存入到log_rec中去。
if ((i>=12)||(rec_min>59)||(rec_sec>59)||(rec_year<1990))
{
total_bad++; /* if a bad date, bump counter */
if (verbose)
{
fprintf(stderr,"%s: %s [%lu]",
msg_bad_date,log_rec.datetime,total_rec);
......
如果日期，时间错误，则把total_bad计数器增加1，并且打印错误信息到标准错误输出。
good_rec = 1;
/* get current records timestamp (seconds since epoch) */
req_tstamp=cur_tstamp;
rec_tstamp=((jdate(rec_day,rec_month,rec_year)-epoch)*86400)+
(rec_hour*3600)+(rec_min*60)+rec_sec;
/* Do we need to check for duplicate records? (incremental mode) */
if (check_dup)
{
/* check if less than/equal to last record processed */
if ( rec_tstamp <= cur_tstamp&nbs......
如何阅读源代码之三(转帖)(2006-12-06 22:51:00)
摘要：在上面曾经提到过，这是DNS解析的代码部分，可以略过不看，不会影响对整个程序的理解。
/* prep hostname */
if (!hname)
{
if (uname(&system_info)) hname="localhost";
else hname=system_info.nodename;
}
这一段继续处理参数做准备工作。如果在命令行中指定了hostname(机器名）则采用指定的名称，否则调用uname查找机器名，如果没有，则用localhost来作为机器名。(同样在README中说得很详细）
/* get past history */
if (ignore_hist) {if (verbose>1) printf("%s ",msg_ign_hist); }
else get_history();
如果在命令行中指定了忽略历史文件，则不读取历史文件，否则调用get_history()来读取历史数据。在这里，我们可以回想在README文件中同样说过这一细节，在命令行或者配置文件中都能指定这一开关。需要说明的是，我们在这里并不一定需要去看get_history这一函数，因为从函数的名称，README文件和程序注释都能很清楚的得知这一函数的功能，不一定要去看代码。而如果要猜想的话，也可以想到，history是webalizer在上次运行的时候记录下来的一个文件，而这个文件则是去读取它，并将它的数据包括到这次的分析中去。不信，我们可以来看看。
void get_history()
{
int i,numfields;
FILE *hist_fp;
char buffer[BUFSIZE];
/* first initalize internal array */
for (i=0;i<12;i++)
{
hist_month[i]=......
如何阅读源代码之二(转帖)(2006-12-06 22:50:00)
摘要：作为一个C程序，在头文件里面，和C文件里面定义的extern变量，结构等等肯定不会少，但是，单独看这些东西我们不可能对这个程序有什么认识。所以，从main函数入手，逐步分析，在需要的时候再回头来看这些数据结构定义才是好的方法。（顺便说一句，Visual C++, 等windows下的IDE工具提供了很方便的方法来获取函数列表，C++的类列表以及资源文件，对于阅读源代码很有帮助。Unix/Linux也有这些工具，但是，我们在这里暂时不说，而只是通过最简单的文本编辑器vi来讲)。跳过webalizer.c开头的版权说明部分（GPL的），和数据结构定义，全局变量声明部分，直接进入main()函数。在函数开头，我们看到：
/* initalize epoch */
epoch=jdate(1,1,1970); /* used for timestamp adj. */
/* add default index. alias */
add_nlist("index.",&index_alias);
这两个函数暂时不用仔细看，后面会提到，略过。
sprintf(tmp_buf,"%s/webalizer.conf",ETCDIR);
/* check for default config file */
if (!access("webalizer.conf",F_OK))
get_config("webalizer.conf");
else if (!access(tmp_buf,F_OK))
get_config(tmp_buf);
从注释和程序本身可以看出，这是查找是否存在一个叫做webalizer.conf的配置文件，如果当前目录下有，则用get_config来读入其中内容，如果没有，则查找ETCDIR/webalizer.conf是否存在。如果都没有，则进入下一部分。(注意：ETCDIR = @ETCDIR@在mak......
如何阅读源代码之一(转帖)(2006-12-06 22:47:00)
摘要：作者：ariesram 来源：不详
写在前面的话：
自从我在linuxaid.com.cn上发表一些文章开始，就不断的有网友发来电子邮件，或者是就其中某些问题进行探讨，或者是查询其他文章的地址（往往这些网友看的是其他网站转载的我的文章），我很高兴自己写出的文章有这么多人回应，因为这是对我最好的赞赏，也很高兴有这么多人对我的文章感兴趣。但是常常因为工作关系。有很多邮件是询问我的其他文章在哪里能够找到，我不一定能够及时回复，也觉得回复同样的问题比较麻烦，所以在这里重复一下，我为linuxaid.com.cn写的文章都能在www.linuxaid.com.cn的应用开发栏目中找到，我的一部分文章收集在bambi.may10.ca/~ariesram/articles下面（这是一个很简陋的网页，只有文本格式的文章，也欢迎有兴趣的网友帮我设计一下网页），我的邮件地址：ariesram@linuxaid.com.cn, 或者ariesram@may10.ca。请转载文章的网站保留这一说明，欢迎网友写email给我探讨问题，虽然我不能保证能及时回复。
正文：
由于工作的关系，我常常需要读一些源代码，并在上面做一些修改并且拿来使用，或者是借鉴其中的某些部分。可以说，open source对于程序员来说，是很有意义的事情。根据我的经验，读源代码，至少有3个好处。第一个好处是可以学习到很多编程的方法，看好的源代码，对于提高自己的编程水平，比自己写源代码的帮助更大。当然不是说不用自己写，而是说，自己写代码的同时，可以从别人写的好的源代码中间学习到更多的编程方法和技巧。第二个好处是，可以提高自己把握大规模源代码的能力。一个比较大型的程序，往往都是经过了很多个版本很长的时间，有很多人参与开发，修正错误，添加功能而发展起来的。所以往往源代码的规模都比较大，少则10-100多k, 多的有好几十个MB. 在阅读大量源代码的时候，能够提高自己对大的软件的把握能力，快速了解脉络，熟悉细节，不仅仅是编程技巧，还能在程序的架构，设计方面提高自己的能力。（这里说一句题外话，<<设计模式>>这本书相信很多人都看过，而且很多人对它推崇备至，奉为经典。现在也出了不少书，都是冠以"设计模式"这一名称......
爱因斯坦的思考题(2006-12-06 22:40:00)
摘要：/*爱因斯坦的思考题
在网上看到了个有趣的逻辑推理题，爱因斯坦声称世界上只有2%的人能解出：
有五个具有五种不同颜色的房间排成一排；
每个房间里分别住着一个不同国籍的人；
每个人都在喝一种特定品牌的饮料，抽一特定品牌的烟，养一特定的宠物；
没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。
问题：谁在养鱼作为宠物？
爱因斯坦给出如下线索：
英国人住在红色的房子里；
瑞典人养狗作为宠物；
丹麦人喝茶；
绿房子紧挨着白房子，在白房子的左边；
绿房子的主人喝咖啡；
抽Pall Mall牌香烟的人养鸟；
黄色房子里的人抽Dunhill牌香烟；
住在中间那个房子里的人喝牛奶；
挪威人住在第一个房子里面；
抽Blends牌香烟的人和养猫的人相邻；
养马的人和抽Dunhill牌香烟的人相邻；
抽BlueMaster牌香烟的人喝啤酒；
德国人抽Prince牌香烟；
挪威人和住在蓝房子的人相邻；
抽Blends牌香烟的人和喝矿泉水的人相邻。
国籍 颜色 宠物 饮料 香烟
挪威 黄色 猫 矿泉水 Dunhill
丹麦 蓝色 鱼 茶 Blends
英国 红色 猫 牛奶 Pall Mall
德国 绿色 鱼 咖啡 Prince
瑞典 白色 狗 啤酒 BlueMaster
*/
/*
算法思路：
以房子的位置为主序，把国籍，颜色，宠物，饮料，香烟都作为该房子的一个成员，每一个成员都有可能
处在任何位置，为所有成员穷举每一个位置，再根据已知条件进行适当剪枝，找到唯一的解
*/
#include <iostream>
#include <string>
#include <......
连通问题(2006-11-26 15:31:00)
摘要：这是我在阅读<<算法1-4（C++实现）——基础，数据结构，排序和搜索（第三版）>>
([美]Robert Sedgewick 著， 张铭泽 赵剑云 梁勇等 译 中国电力出版社)
时整理的读书笔记,现在贴出来,希望能给初学者一些启发.
/*
Name: 连通问题
Copyright:
Author:
Date: 25-11-06 21:59
Description: 连通问题
假设有一个整数对的序列，每个整数代表某个类型的一个对象，p-q对表示"p连接到q"，
即p和q之间连通。假设连通关系具有传递性--如果p与q连通，q与r连通，那么p与r连通。
我们的目标是写一个过滤出那些不在集合中的对的程序：输入p-q对时，
如果已输入的对的集合中没有隐含这样的对（通过连通关系的传递性），那么程序将输出该对。
如果前面输入的对隐含了p与q的连通，那么程序将忽略p-q，准备输入下一对。
输入输出示例如下：
输入 输出 隐含
3-4 3-4
4-9 4-9
8-0 8-0
2-3 2-3
5-6 ......
我所理解的动态内存分配(2006-11-23 16:34:00)
摘要：本文的内容大部分来自《C++Primer第三版中文版》，是我学习C++的一个笔记，写出来主要是作为初学者的一个参考，希望对大家有所帮助。
全局对象和局部对象的生命期是严格定义的，程序员不能够以任何方式改变它们的生命期。但是，有时候需要创建一些生命期能被程序员控制的对象，它们的分配和释放可以根据程序运行中的操作来决定。这种对象被称为动态分配的对象(dynamicaily allocated object)。动态分配的对象被分配在内存的堆中（有些资料称为自由空间(free store)，其实就是堆）。关于堆的具体含义大家可以参考《数据结构》教程和文章《明晰C++内存分配的五种方法的区别》。
程序员用new表达式创建动态分配的对象，用delete表达式结束此类对象的生命期。动态分配的对象可以是单个对象，也可以是对象的数组，动态分配的数组的长度可以在运行时计算。
在本文中，我将向大家介绍我所理解的两种形式的new的表达式：一种支持单个对象的动态分配，另一种支持数组的动态分配。并详细分析一种智能指针auto_ptr。
一 单个对象的动态分配与释放
new表达式由关键字new及其后面的类型指示符构成。该类型指示符可以是内置类型或class类型。例如：
new int ;
从堆中分配了一个int型的对象。类似地
......