技术乐土

编程珠矶学习笔记（5）--两分搜索算法（折半查找算法）

ljqy — 2009-10-19 22:22:00

个人原创，转载请注明出处，谢谢！一、目的 input: 有序序列 output: 查找结果，如果为-1则未找到目标 constrain: 使用两分法进行查找，使查找时间复杂度为O(logn) 二、算法原理两分搜索算法是一种理解比较简单，但执行效率却十分高的算法。可以用循环的方式来实现，也可以用递归的方式来实现。算法原理如图: 通过不断的改变l和u的值来接近要查找的目标值（40） m = ( 0 + 13 ) / 2 = 6 result: l = 0, u = m – 1 = 5 m = ( 0 + 5 ) / 2 = 2 result: l = m + 1 = 3, u = 5 m = ( 3 + 5 ) / 2 = 4 result: l = 3 , u = m – 1 = 3 三、代码 #include #include #include #define MAXN 1000000 typedef int DataType; DataType x[MAXN]; int n = 0; int binarysearch (DataType t) { int l, u, m; l = 0; u = n-1; while (l <= u) { m = (l + u) / 2;

编程珠矶学习笔记（4）--挤压法查找变位词

ljqy — 2009-10-19 22:20:00

个人原创，转载请注明出处，谢谢！一、目的如示例： input: 单词文件 output: 同位词归类文件 constrain: 归类所有为同位词的单词何为同位词：单词字母相同，但字母的顺序不同: pans 和snap是同位词 pots 、stop和tops是同位词，还有这些：二、算法原理如果我们输入如下单词序列，并期望对该序列进行同位词归类：第一步：对每个单词进行签名。如这些单词：我们使用每个单词的字母序列（按字母顺序进行排列）作为它的个人签名，如pans的签名是 anps，这样我们可以得到上图右侧的签名序列。第二步：对签名序列进行排序。如下图：通过对签名序列进行排序后，大家可以发现同位词聚在了一起，我们只需要将具有相同签名的单词合并在一起即可。第三步：对排序后的签名序列进行挤压：这样我们通过三步即完成了同位词的查找过程，实现代码其实很简单，但其算法思想给人眼前一亮的感觉。三、代码 Sign.c: #include #include #include #define WORDMAX 100 int charcomp (char *x, char *y) { return *x - *y; } int main() { char word[WORDMAX], sig[WORDMAX]; while (scanf("%s", word) != EOF) { strcpy

编程珠矶学习笔记（3）--反转旋转（手摇法实现旋转）

ljqy — 2009-10-19 22:19:00

个人原创，转载请注明出处，谢谢！一、目的如示例： input: n = 10, rotdist = 5 (移动前5个元素到数组尾), x[] = {1,2,3,4,5,6,7,8,9,10} output: x[6,7,8,9,10,1,2,3,4,5] constrain: 使用尽可能少的额外内存可通过手揺法来实现旋转，其原理如下图：准备：两手上下平放，左手在上，右手在下，手面圴冲自己，此时规定十个手指从上到下分别代表1,2,3,4,5,6,7,8,9,10 第一步：将左手反转，手背冲自己，拇指此时冲地面：第二步：将右手也反转，手背冲自己，拇指此时冲地面：第三步：将两个手同是反转，手面冲自己，与准备动作的区别是，现在右手在上左在下，观察手指上的数字会发现，此时已经达到了移位的目的(6,7,8,9,10,1,2,3,4,5)：这就是本算法的原理，通过三次反转(手摇三次)来实现旋转的目的。为了易于说明原理，本例采用了10个元素，移动5个的要求（必竟人就10个手指嘛），但对于其它任何要求，本算法也适用。二、代码#include #include #include #define MAXN 10000000 int x[MAXN]; int rotdist, n; void reverse(int i, int j) { int t; while (i < j) { t = x[i]; x[i] = x[j]; x[j] = t; i++; &nbs

编程珠矶学习笔记（2）--移位旋转

ljqy — 2009-10-19 22:13:00

个人原创，转载请注明出处，谢谢！一、代码#include #include #include #define MAXN 10000000 int x[MAXN]; int rotdist, n; int gcd(int i, int j) { int t; while (i != 0) { if (j >= i) j -= i; else { t = i; i = j; j = t; } } return j; } void jugglerot(int rotdist, int n) {

编程珠矶学习笔记（10）--查找最大和（扫描算法O(n)）

ljqy — 2009-10-19 12:12:00

个人原创，转载请注明出处，谢谢！一、目的input: n个元素的数组； output: 在数组中查找相邻数的最大和； constrain: 如最大和为负数，则最大和为0，即一个也不选。二、算法原理算法从数组的最左端x[0]开始，一直扫描到最右端x[n-1]，记下所碰到过的最大和，初始最大和为0。实际通过一个一个的增加元素来判断哪个子数组的和最大，抛弃小的和，留下大的和，最终得到最大和。就像我们看一排队伍中哪个人最高，我们从队伍的开头走起，发现一个比前面个子高的，就记下他来，然后往后走，又发现一个个子更高的，那就记下这个，忘掉之前的，再继续向后走，最终走到头，即可知道这个队伍中谁个子最高。和本算法唯一区别是，本算法不是求某个数最大，而是求哪几个连续数的和最大。如下图：三、代码#include #include #include #define MAXN 10000000 int n; float x[MAXN]; void sprinkle() { int i; for (i = 0; i < n; i++) { x[i] = 1 - 2*( (float) rand()/RAND_MAX); } } float get_max_sum () { int i; float maxsofar = 0, maxendinghere = 0; for (i = 0; i < n; i++) { maxendinghere += x[i]; if (maxendinghere < 0)

编程珠矶学习笔记（1）--位排序

ljqy — 2009-10-12 22:55:00

个人原创，转载请注明出处，谢谢！一、代码#include #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; inline void set_bit(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } inline void clear_bit(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } inline int test_bit(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); } int main() { int i; for (i = 0; i < N; i++) { clear_bit(i); } while (scanf("%d", &i) != EOF) &nbs

白皮书、蓝皮书、红皮书都是啥？[zt]

ljqy — 2009-07-22 10:07:00

原文:http://cykctadcl.blog.163.com/blog/static/4229299620092510123812/ 白皮书白皮书最初是因为书的封皮和正文所用的纸皆为白色而得名。英语中“WHITE PAPER”和“WHITE BOOK”，汉语均译作白皮书，但两者是有区别的。在英国，“WHITE PAPER”主要指政府发表的短篇幅报告。任何题材、任何组织机构均可使用，亦可用于包含背景材料的政治性官方声明。蓝皮书蓝皮书用于官方文件时，主要指英国议会的一种出版物。因封皮是蓝色，故名。开始发行于1681年，自1836年才公开出售。其名称是《英国议会文书》，是英国政府提交议会两院的一种外交资料和文件。有一类外文称为蓝皮书的，并不属于什么官方文件。从内容看，乃系名人录、指南、手册之类的工具书，甚至包括纪念画册。如美国政府官员名录、社会名人录、国务院每月发行的驻美外交人员衔名录，以及美国一些大学作试题答案用的小册子也称蓝皮书（汉语可译为蓝皮簿）。红皮书使用红皮书的国家主要有西班牙、奥地利、英国、美国、土耳其、前苏联等。有的用于官方文件，有的用于非官方文件。西班牙于1965年、1968年先后发表《关于直布罗陀问题的红皮书》（英文版）。英国早在13世纪就有用于财政方面的红皮书。此外，有的国际组织亦使用红皮书，如《国际电信联盟红皮书》。当然最有名、发行量最大的“红皮书”莫过于六、七十年代的《毛主席语录》——“红宝书”。

code complete 代码大全

ljqy — 2009-03-09 12:18:00

花了近四个月读完，但读的是英文版的，读的比较细，由于内容比较多所以基本是体会很多，但看了后面的忘了前面的，所以准备读第二遍，并适当的做笔记，并撰写一些博客心得，目前有以下个人心得; (1)对于软件构建说的系统详细。以前在大些公司做过，也用过CMM，但真正体会其价值及其应该如何去用，是在这里才明白；（2）由于做过一些项目，走过很多弯路所以对一些内容、方法和建议有一些体会，但对于项目工作经验不是很多的人理解估计会费些力，但我想坚持下来，以后做项目时会少走弯路；（3）由于内容庞大，细节很多，同时它也像本，项目过程参考手册，所以我想有个总体学习后，主要是在后期项目具体阶段再回到书里来，具体问题具体解决；我曾尝试着用其方法，新写了一个子模块，在系统，结构和可读性上确实有很大提高，使自己很欣慰,同时看着这些代码感觉很踏实；（4）书里提供了很多参考书，估计有上百本，但大家如何去选择阅读？作者在网站上提供了开发人员进阶的读书列表，大家可以依照进行，使自己知识能快速的全面系统起来，也避免淹没在书海中；（5）读完它后感觉自己真是沧海一粟，要学的还有很多，但有作者的阅读计划作为参考，心里比较有底，大胆的往前走即可。最后，我感觉她就像一个点，她能帮你引出一个点和面来，如果能真正拥有她们，最终你的知识将形成一个牢不可破的网！在开发上如果找不到自信或不知何去何从的话，我向您推荐这本书！个人观点，仅供参考！ http://ljqy.programfan.com

爱的宣言

ljqy — 2008-12-14 17:09:00

我有一个小小的窝如果饥饿将带走我们我希望第一个是我如果寒冷将带走我们我也希望第一个是我我将把仅有的食物留给我的爱人我也将把单薄的衣服披上我的爱人因为我知道我的孩子将在她母亲的哺育下茁壮成长因为我也知道我的孩子将在她母亲的怀里温暖入睡在我倒下的地方我希望化为一棵参天的大树守护着我的小窝我将枝繁叶茂以为她们挡风遮雨我也将硕果累累以为她们驱除饥饿这时我将变得幸福无比因为我们的爱情已经永生这就是我爱的宣言 http://blog.programfan.com/article.asp?id=12266 新的一年即将来临，谨以此献给跟随我漂泊将满九年，但却仍要和我为生活继续苦拼的妻子。同时也将它献给为生活奔波，没房、没车、没钱、没有太多东西，但却拥有爱情并视其为生命的朋友们！同时希望新的一年经济危机能够过去！

乒乓球拍品牌介绍[zt]

ljqy — 2008-11-17 18:03:00

http://july19721114.blog.hexun.com/8293426_d.html 一、成品球拍：所谓成品球拍，就是把底板胶皮海绵粘贴好然后成套出售的球拍，一般为初学者选用较多。推荐品牌为天津友谊公司的729系列成品拍，其性价比在成品拍中算是相当高的，价格一般为几十元，性能对于初学者来说是足够使用了。初学者因为技术风格还没有成型，可以先购买一块729的成品球拍，专心练技术。等到达到一定水平之后，再根据自己的需要DIY一块专业底板，这是比较经济实惠的器材路线。 729成品拍比较有特色的是国粹系列，使用京剧脸谱作为拍柄的拼花，整体看上去很漂亮，性能也不错。此外还有专门为儿童设计的儿童球拍等等。此外，一些进口品牌，比如日本蝴蝶和瑞典STIGA等等也都制作了一些成品球拍，这些球拍的价格一般也是几十元，但是性价比较729系列还是差了一些。红双喜曾经推出狂飙系列高档成品拍，用狂飙系列专业底板配上狂飙系列套胶成套出售，价格一般在三四百元，性价比很低，而且整体的搭配也并不算合理，不推荐购买。　二、底板篇： 1、进口品牌： STIGA (斯蒂卡)——瑞典品牌。STIGA具有世界上一流的粘合技术，所制造出来的底板以底劲充足著称，在国家队占有相当大的使用比例。STIGA还首创了拍柄中空的WRB技术和CR技术等，是研发能力最强的厂家之一。代表作品主要有：Clipper Wood系列(刘国梁曾用)、OC系列(王励勤曾用)、Tube系列、白钻、红黑碳王等，新近上市的“水晶”等新材质底板呼声也异常响亮。 YASAKA(亚萨卡)——瑞典品牌，以制作弧圈板著称。代表作如YASAKA EXTRA(盖亭、马琳、王皓等先后使用)、YASAKA OFFENSIVE(李静曾用)等。近来以YCA为代表的软碳作品也相当热卖，掀起了一股碳素软板的热潮。 AVOLOX(阿瓦拉)——瑞典品牌。在上一代专业队员中占有绝对市场，传闻为中国国家队设计，请瑞典STIGA代工制作，以手感柔和著称，比较符合中国运动员的习惯。代表作品如P500(王楠曾用)、P700(王涛曾用)。近年AVOLOX品牌渐有凋零之势，其产品质量很不稳定。经日本乒协检测过的AVOLOX底板同时被烙上NITTAKU烙印，成为Nittaku-Avolox，据说其品质比一般的AVOLOX好一些，价格也贵一

延庆--龙庆峡--豆腐宴

ljqy — 2008-10-30 13:35:00

十一和朋友去了次延庆，一些体会和大家分享：（1）龙庆峡门票40元，只能去水库一侧爬山，越爬越郁闷，即没有可看的也没有可玩的。为了不白来一趟（毕竟难得的长假），狠了一下心去坐船（60元），船速到不慢，带着大家在水库里转了一圈，冷的不行（要不冷可以租棉衣），然后停靠在中心的小岛下来转了一圈，十分钟就能走到头，然后又坐船回来了。虽然是青山绿水，但从进门到出门总有不断被骗的感觉，不过景点有的是有钱的韩国和日本人，不缺也不需回头客。（2）豆腐宴柳沟的豆腐宴比较有特色，在农家院里面，无论人多人少，都给上满一大桌子，尤其是火盆锅最有味道，而且价钱也不贵，19元/每人，没吃过的可以尝一下，唯一的不足是，有些饭菜吃不完，他们是回收的，想一下不是太卫生，再去吃的念头也就没有了。

看清--北京林捷货运有限公司

ljqy — 2008-10-28 15:16:00

这周，在这家（北京林捷货运有限公司）公司运了个包裹，感觉： http://www.laiwan.com/shop/966/22578/index.html （1）服务态度比较差，员工比较牛；（2）费用比较高，比六郎庄托运要贵20元左右；（3）有欺骗性，电话咨询时说保费千分之四，但当你交费时，又告诉你保一万以上才是这个比例，一万一下均是10元保费；（4）手续不规范，给客户的凭据连个公司章都没有。（5）拿走包裹连在上面贴个条都没有，真不知会不会给我寄错了！让人寄完后就郁闷，更别说担心我的包裹了。

dao 和 ado 冲突怎么解决[zt]

ljqy — 2008-03-27 00:29:00

http://topic.csdn.net/t/20020327/21/604906.html

Linux下的FTP服务器配置[zt]

ljqy — 2008-03-08 11:43:00

http://www.pconline.com.cn/pcedu/soft/st/linux/10209/90930_1.html

linux top命令详解[zt]

ljqy — 2008-03-03 11:21:00

(1) http://hi.baidu.com/hill_ming/blog/item/2a3e2151460f358c8d5430fe.html (2) http://www.pcicp.com/tech/os/LinuxStudy/2004-02-06/1076049804d2390.html (3) http://www.linuxdiyf.com/viewarticle.php?id=68828

什么是initrd[zt]

ljqy — 2008-02-28 15:03:00

http://hi.baidu.com/schuang333/blog/item/3b562c236203c6569922ed8f.html http://blog.csdn.net/pilipili/archive/2007/03/18/1532659.aspx

开放源码平台革命：Embedded Linux 技术与概念解析[zt]

ljqy — 2008-02-28 14:59:00

开放源码平台革命：Embedded Linux 技术与概念解析 http://www.mcuol.com/Tech/116/23879.htm

Linux系统启动过程分析[zt]

ljqy — 2008-02-28 14:58:00

http://blog.chinaunix.net/u1/48373/showart_418407.html

initrd-x.x.x.img文件分析-制作安装程序不支持的根文件系统[zt]

ljqy — 2008-02-28 14:57:00

http://bbs.chinaunix.net/viewthread.php?tid=147511

《观察与思考》:相信中国,寻找下一个比尔·盖茨[zt]

ljqy — 2008-02-12 15:01:00

原文:http://news.csdn.net/n/20080206/113435.html 你为什么成不了比尔·盖茨? 不必沮丧,不必恼怒,毕竟,这个世界上只有一个比尔·盖茨,准确地说应该是:我们为什么成不了比尔·盖茨?“开什么国际玩笑,我一个连住房按揭都还不过来的'月光族',还比尔·盖茨呢!”如果你真的这么想,那只能说明你在思维上与比尔·盖茨相差一光年,比财富上的距离还远—是的,正如巴拉昂秘诀所揭示的,你缺乏野心! 比尔·盖茨的偶像、世界上第一个亿万富翁洛克菲勒曾豪言:“如果把我剥得一文不名丢在沙漠的中央,只要一行驼队经过—我就可以重建整个王朝.”世界旅馆业大王康拉德·希尔顿则表示,当他潦倒困顿到必须睡在公园的长板凳上时,他已经知道自己以后将会成功.这就是野心的力量! 比尔·盖茨自然是幸运的:他自己亦坦承,如果王安能完成他的第二次战略转折,世界上可能就没有今日的微软,“我可能就在某个地方成了一位数学家,或一位律师”,此乃天时;微软公司创办25周年之际,《今日美国报》记者问他对美国政府决定分割微软的看法,他回答说:“撇开这宗诉讼不谈,这仍是一个利于创业的伟大国度.我对这个国家的感激,远胜于这宗针对我们的官司.”比尔·盖茨本人无疑是“美国梦”的最佳诠释.此乃地利;更关键的是,他在选择学校、专业乃至选择退学上最终都得到了父母的理解和支持,他担任IBM董事的母亲“以自己的成就和人格为我的爱子作最好的担保”帮助初创的微软获得了至关重要的第一份商业合约,而其身为知名律师的父亲亦在商务处理方面颇多助力,此乃人和. 除了天时、地利、人和,最重要的,当然仍是天才企业家的个人禀赋.《影响历史的商业七巨头》一书的作者、哈佛商学院教授理查德 ·泰德罗就认为:“这本书里的主人公是天生的,而不是后天教育的”.甲骨文CEO拉里·埃里森甚至声称:“一顶帽子一套学位服必然要让你沦落……”伟大的企业家没有一个是读出来的,他们总是创造或改写商学院案例,而非学习案例.“有能力把自己写进艺术史的人,不会做一个评论家”,尽管这是两种不同的价值. 这一论断在某种意义上同样适用于企业家.德鲁克就说过:“管理是一种实践,其本质不在于'知'而在于'行';其验证不在于逻辑,在于成果.”