duanple

两年前的日志了———————————————
 现在的生活…
2006-12-05 09:34:57

这周就要考网络安全了，于是去图书馆，看相关的网络安全书籍，还要做网络安全的实验。很多的时间也放在了网上，有时候去bmy的几个技术版面，java， c&c++,算法，计算机程序设计逛逛。在se，mood灌灌水，今天又拿到了新斑竹的棒棒糖。生活就是这样度过的，晚上去学院被那机子搞郁闷了 之后，便去图书馆了，然后是康三的书店，或许可以在周末去西安的书城看书，也是一种不错的消遣。 read more

历史上，Knuth在其<<Sorting and Searching>>一书的第6.2.1节指出：尽管第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现。

而不经仔细斟酌而写出的一个二分查找经常遭遇off by one或者无限循环的错误。下面将讨论二分查找的理论基础，实现应用，及如何采用何种技术保证写出一个正确的二分程序，让我们免于思考麻烦的边界及结束判断问题。 read more

作为思维的一种方法，类比大概是其中最重要的一种。

陈胜说"王侯将相，宁有种乎"，必然是经过一番比较的。仿生学的产生，比如潜艇，飞机，军装的颜色便是一种生物的模仿。了解下蜂房的构造，有助于人类建筑的改进。王阳明格物致知，格竹，这也是一番类比。类比一番，你会发现宏观世界与微观世界的惊人相似，天体力学与原子力学是统一的，光就是一种电磁波。大多数的不幸都是类似的，大多数的幸福也是类似的。时间空间本身就是人类的一种空想，梦境与真实实际上是如此模糊不清。 read more

走进2009的第一天，我才发现我的生日已然在几天前过去了，不过我向来对生日之类的节日不感冒，自己也很少会为了生日做些特殊的事情。

还是想想2008吧，日子如水一般，平静的流淌过。这样久违的日子终于又回来了，上半年在校园里悠哉悠哉的晃着。在图书馆里自由自在的翻着书，享受着大学的生活。可是到现在我能记起来的这一年里发生的事情，果真是太有限了。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081131113145832/

虽然网上有很多介绍了，我还是要写一下吧，尽量从它的起源，如何被发现，以及为什么应该是这样的来写，单纯的使用很简单，也不是学习的目的，理解有助于记忆吧，当然可能还有理解不到的地方。 read more

爱因斯坦总共在乌尔姆呆了１５个月。至今也无证据表明他此后探访过自己的出生地。乌尔姆市长曾给他写信，通知已将他故居门前的胡同命名为爱因斯坦大街。爱因斯坦致信答谢说：“我知道有条街以我命名了。令我稍感安慰的是，我本人不用为这条街上出了什么事儿负责。” read more

祖师度我出红尘，铁树开花始见春。化化轮回重化化，生生转变再生生。
欲知有色还无色，须识无形却有形。色即是空空即色，空空色色要分明。

我把袈裟扯破，埋了藏经，弃了木鱼，丢了铙钹。学不得罗刹女去降魔，学不得南海水月观音座。夜深沉独自卧，起来时独自坐，有谁人孤凄我？似这等削发缘何？恨只恨说谎的僧和俗，哪里有天下园林树木佛，哪里有枝枝叶叶光明佛，哪里有江湖两岸流沙佛，哪里有八万四千弥陀佛。从今后把钟楼佛殿远离却，下山去寻找一个年少哥哥。凭他打我、骂我、说我、笑我，一心不愿成佛，不念弥陀般若波罗。 read more

很有意思的文章。

有一天，柏拉图问苏格拉底：什麽是爱情？
　　苏格拉底说：我请你穿越这片稻田，去摘一株最大最金黄的麦穗回来，但是有个规则：你不能走回头路，而且你只能摘一次。
　　於是柏拉图去做了。许久之后，他却空著双手回来了。
　　苏格拉底问他怎麽空手回来了？
　　柏拉图说道：当我走在田间的时候，曾看到过几株特别大特别灿烂的麦穗，可是，我总想著前面也许会有更大更好的，於是就没有摘；但是，我继续走的时候，看到的麦穗，总觉得还不如先前看到的好，所以我最后什麽都没有摘到。。。
　　苏格拉底意味深长地说：这，就是爱情。
　　又一天，柏拉图问苏格拉底：什麽是婚姻？
　　苏格拉底说：我请你穿越这片树林，去砍一棵最粗最结实的树回来好放在屋子裏做圣诞树，但是有个规则：你不能走回头路，而且你只能砍一次。
　　於是柏拉图去做了。许久之后，他带了一棵并不算最高大粗壮却也不算赖的树回来了。
　　苏格拉底问他怎麽只砍了这样一棵树回来？
　　柏拉图说道：当我穿越树林的时候，看到过几棵非常好的树，这次，我吸取了上次摘麦穗的教训，看到这棵树还不错，就选它了，我怕我不选它，就又会错过了砍树的机会而空手而归，尽管它并不是我碰见的最棒的一棵。
　　这时，苏格拉底意味深长地说：这，就是婚姻。
　　还有一次，柏拉图问苏格拉底：什麽是幸福？
　　苏格拉底说：我请你穿越这片田野，去摘一朵最美丽的花，但是有个规则：你不能走回头路，而且你只能摘一次。
　　於是柏拉图去做了。许久之后，他捧著一朵比较美丽的花回来了。
　　苏格拉底问他：这就是最美丽的花了？
　　柏拉图说道：当我穿越田野的时候，我看到了这朵美丽的花，我就摘下了它，并认定了它是最美丽的，而且，当我后来又看见很多很美丽的花的时候，我依然坚持著我这朵最美的信念而不再动摇。所以我把最美丽的花摘来了。
　　这时，苏格拉底意味深长地说：这，就是幸福。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/709717672008112243754300/

宏，是一个比较容易出错的地方，同时也是容易产生技巧的地方。比如用宏可以使c++的访问控制失效，比如

#define private public

可以用于生成函数，可以替换一些函数，可以定义一些程序模式。。。 read more

先看一下匈牙利算法的dfs实现，很简洁

//二分匹配模板
bool g_map[MAX_N][MAX_N];
int r[MAX_N];
int l[MAX_N];
bool used[MAX_N];
int n;
bool path(int u,int n){
    for(int v = 0 ; v < n ; v++){
        if(g_map[u][v] && !used[v]){
            used[v] = true;   
            if(r[v] == -1 || path(r[v],n)){
                l[u] = v;
                r[v] = u;   
                return true;
           }           
        }
    }
    return false;
}
int bin_match(int n){
    int res = 0;
    memset(r,-1,sizeof(r));
    memset(l,-1,sizeof(l));
    for(int i = 0 ; i < n ; i++){
        memset(used,false,sizeof(used));
        if(l[i] == -1){
           if(path(i,n)) res++;   
        }
    }
    return res;
} read more

http://www.royans.net/arch/
http://www.guao.hk
http://horicky.blogspot.com/2010/10/scalable-system-design-patterns.html
http://www.theregister.co.uk/2009/10/23/google_spanner/
 

我自己申请的共享空间，可以用来放文件

大牛的链接：

http://www.matrix67.com/blog/ 竟然是中文系的。。。 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/709717672008111064351431/

很明显，对于算法的证明过程的理解有助于算法本身的理解。

关于二分图，算法的流程在这篇blog里讲的很清楚，很多算法都结合了图形，所以讲讲得很易懂，推荐一下 read more

转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081198472074/

二分图，是图论中的一个经典模型，关于二分图，涉及了很多问题，比如最大匹配，最优匹配，完美匹配，最小覆盖。网络流也是这样，再求最大匹配的时候，实际上可以利用转化的思路，就像利用最短路算法求解差分约束系统，利用单源最短路求单目标最短路，利用单源最大流求多源最大流，都是利用了转换的思想，将一个不熟悉的问题转换或者规约为一个熟知的问题。 read more

大卫.希尔伯特说过，we must konw，we will know.

1.
一对夫妇邀请N-1对夫妇参加聚会（因此聚会上总共有2N人）。每个人都和所有自己不认识的人握了一次手。然后，男主人问其余所有人（共2N-1个人）各自都握了几次手，得到的答案全部都不一样。假设每个人都认识自己的配偶，那么女主人握了几次手？ read more

想起来了，以前计划写的一些还没完成

一个是逻辑的引擎，一个是搜索引擎专题。

1.

将数组{32,74,25,53,28,43,86,47}按从小到大排列，每次可以交换任意两个元素，最少

需要交换_______次

答案是5次,置换的分解。

2.

给你一个已经排好序的数组a，里面可能有重复元素，比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整

a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1}，要求里面的每个子序列都是有序的，并且其中的元素唯一。

另外，要求这样的子序列数最小，并且只能使用O(1)的辅助空间。 read more

1.设置环境变量，我省略了设置LD_ASSUME_KERNEL=2.4.1这步，因为引发了错误，有动态库找不到
./home/duanple/intel/ict/3.0.1/itac/7.0.1/bin/itacvars.sh
2.添加必须的头文件
#include <VT.h>
3.编译，链接，-t是对于-L -lVT的一个简化调用
mpiicc -g -t test.c
4.设置产生得trace数据的保存文件夹
export VT_LOGFILE_PREFIX=~/mpitest
export VT_PCTRACE=5
mpiexec -n 2 ./a.out read more

转载请注明作者：phylips@bmy

出处：http://duanple.blog.163.com/blog/static/70971767200811344425606/

引言：
现实中的很多问题都可以看成搜索问题
众里寻她千百度，蓦然回首那人却在灯火阑珊中。
就算是人类的思维，很多时刻也是在进行着搜索，搜索存储在脑中的记忆元素
就算身在社会中，我们也还是在不同的时间搜索着不同的东西。 read more

做这种事情比较没成就感，就是碰到一堆问题，然后上网搜索，要么多尝试几次，花费的时间比较多，但是比较无趣
接前话
1.安装完毕intel集群工具包之后，接下来要记得运行几个**var.sh,主要是设置环境变量的脚本，一般在各个包的/bin目录下面，比如mpi的mpivars.sh,icc的iccvars.sh,如果单纯执行脚本的话，只对当前shell有效
最好直接修改/etc/profile,如何修改，可以打开这两个脚本做的事情。
其实主要是设置了PATH LD_LIBRARY_PATH这两个变量 read more

经典问题,如果只要求额外空间O(1)，实际下面这篇文章就是这种，但是我怀疑它的时间不是O(n)

利用了手摇算法进行swap.

http://www.cppblog.com/converse/archive/2008/09/28/63008.aspx?opt=admin

原文作为附录贴在本文后面了。

实际上该题出现在taocp。

taocp:5.2.4 18. read more