博文
编程珠矶学习笔记（5）--两分搜索算法（折半查找算法）(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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#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）--挤压法查找变位词(2009-10-19 22:20:00)
摘要：个人原创，转载请注明出处，谢谢！
一、 目的
如示例：
input: 单词文件
output: 同位词归类文件
constrain: 归类所有为同位词的单词
何为同位词：单词字母相同，但字母的顺序不同:
pans 和snap是同位词
pots 、stop和tops是同位词，还有这些：
二、算法原理
如果我们输入如下单词序列，并期望对该序列进行同位词归类：
第一步：对每个单词进行签名。如这些单词：
我们使用每个单词的字母序列（按字母顺序进行排列）作为它的个人签名，如pans的签名是 anps，这样我们可以得到上图右侧的签名序列。
第二步：对签名序列进行排序。如下图：
通过对签名序列进行排序后，大家可以发现同位词聚在了一起，我们只需要将具有相同签名的单词合并在一起即可。
第三步：对排序后的签名序列进行挤压：
这样我们通过三步即完成了同位词的查找过程，实现代码其实很简单，但其算法思想给人眼前一亮的感觉。
三、代码
Sign.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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）--反转旋转（手摇法实现旋转）(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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#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++;
&n......
编程珠矶学习笔记（2）--移位旋转(2009-10-19 22:13:00)
摘要：个人原创，转载请注明出处，谢谢！
一、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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)
{ &nb......
编程珠矶学习笔记（10）--查找最大和（扫描算法O(n)）(2009-10-19 12:12:00)
摘要：
个人原创，转载请注明出处，谢谢！
一、目的
input: n个元素的数组；
output: 在数组中查找相邻数的最大和；
constrain: 如最大和为负数，则最大和为0，即一个也不选。
二、算法原理
算法从数组的最左端x[0]开始，一直扫描到最右端x[n-1]，记下所碰到过的最大和，初始最大和为0。实际通过一个一个的增加元素来判断哪个子数组的和最大，抛弃小的和，留下大的和，最终得到最大和。就像我们看一排队伍中哪个人最高，我们从队伍的开头走起，发现一个比前面个子高的，就记下他来，然后往后走，又发现一个个子更高的，那就记下这个，忘掉之前的，再继续向后走，最终走到头，即可知道这个队伍中谁个子最高。和本算法唯一区别是，本算法不是求某个数最大，而是求哪几个连续数的和最大。如下图：
三、代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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 &l......
编程珠矶学习笔记（1）--位排序(2009-10-12 22:55:00)
摘要：个人原创，转载请注明出处，谢谢！
一、代码
#include <stdio.h>
#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)
......
白皮书、蓝皮书、红皮书都是啥？[zt](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 代码大全(2009-03-09 12:18:00)
摘要：花了近四个月读完，但读的是英文版的，读的比较细，由于内容比较多所以基本是体会很多，但看了后面的忘了前面的，所以准备读第二遍，并适当的做笔记，并撰写一些博客心得，目前有以下个人心得;
(1)对于软件构建说的系统详细。以前在大些公司做过，也用过CMM，但真正体会其价值及其应该如何去用，是在这里才明白；
（2）由于做过一些项目，走过很多弯路所以对一些内容、方法和建议有一些体会，但对于项目工作经验不是很多的人理解估计会费些力，但我想坚持下来，以后做项目时会少走弯路；
（3）由于内容庞大，细节很多，同时它也像本，项目过程参考手册，所以我想有个总体学习后，主要是在后期项目具体阶段再回到书里来，具体问题具体解决；我曾尝试着用其方法，新写了一个子模块，在系统，结构和可读性上确实有很大提高，使自己很欣慰,同时看着这些代码感觉很踏实；
（4）书里提供了很多参考书，估计有上百本，但大家如何去选择阅读？作者在网站上提供了开发人员进阶的读书列表，大家可以依照进行，使自己知识能快速的全面系统起来，也避免淹没在书海中；
（5）读完它后感觉自己真是沧海一粟，要学的还有很多，但有作者的阅读计划作为参考，心里比较有底，大胆的往前走即可。
最后，我感觉她就像一个点，她能帮你引出一个点和面来，如果能真正拥有她们，最终你的知识将形成一个牢不可破的网！在开发上如果找不到自信或不知何去何从的话，我向您推荐这本书！
个人观点，仅供参考！
http://ljqy.programfan.com ......
爱的宣言(2008-12-14 17:09:00)
摘要：我有一个小小的窝
如果饥饿将带走我们
我希望第一个是我
如果寒冷将带走我们
我也希望第一个是我
我将把仅有的食物留给我的爱人
我也将把单薄的衣服披上我的爱人
因为我知道
我的孩子将在她母亲的哺育下茁壮成长
因为我也知道
我的孩子将在她母亲的怀里温暖入睡
在我倒下的地方
我希望化为一棵参天的大树
守护着我的小窝
我将枝繁叶茂
以为她们挡风遮雨
我也将硕果累累
以为她们驱除饥饿
这时我将变得幸福无比
因为我们的爱情已经永生
这就是我爱的宣言
http://blog.programfan.com/article.asp?id=12266
新的一年即将来临，谨以此献给跟随我漂泊将满九年，但却仍要和我为生活继续苦拼的妻子。同时也将它献给为生活奔波，没房、没车、没钱、没有太多东西，但却拥有爱情并视其为生命的朋友们！
同时希望新的一年经济危机能够过去！......
乒乓球拍品牌介绍[zt](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好一些，价......