独孤酒剑·重出江湖

很久了

sharang — Sat, 20 Jan 2007 02:29:00 GMT

        很久没写日志了，2个月了吧。

        11月下旬-备赛
        12月中旬-去西安
        12月20号-回长春
        12月下旬-开始数据库项目，LINUX考试
         1 月上旬-数据库项目，信息安全、邓论、软件工程考试
         1 月中旬-网络、图形学考试，答辩，项目文档和报告。

        看看上面的日程，真的很紧，不过总算挺过来了。

        西安赛给我印象最深的就是那个超大的rank了，forty-six place，听着都寒，不过居然还是铜，获奖率55.5%。就像 Dr.黄那天调侃，得了金奖就有宣传的资本了，因为别人不知道金奖其实有10个，呵呵。不过话说回来，参加ACM最大的奖励，已经在我为之奋斗的过程中颁发给我了，而赛场上的那张纸，只是为了分出1，2，3而设置的。

        前天和LiQ & LanQ吃饭，谈到写论文中的实验，我很奇怪问什么写论文的时候把实验细节忽略了，LiQ解开了疑团：因为首先要对实验过程保密，其次洋人对别人的第一印象是建立在“他说的是实话，虽然不一定是真理”的假定上的，而我们对别人的第一印象是建立在“不论他说的是否是真理，他说的都有可能是假话”。这个解释让我恍然大悟，地球太危险，我想去火星。

        说说我们的项目吧，数据库原型系统，由于时间紧迫，我们将原先的功能进行了大缩减。我们组大概做了10天，设计+编码，60个class，8500行代码(不包括visual editor生成的1500行界面代码)，实现了一些基础功能。前天把报告写了，一份是我们小组的总报告，写了10多页，还有一份是我自己的，写了21页。虽然这次的项目没完成预期的功能，也确实是由于没有预见到的时间问题，做到现在这个程度已经很不错了。

        昨晚又打了一回长春MaJiang，上次学的规则差点全忘了。幸好长春的基本规则不是太麻烦，不过还是有几次发现自己搞错规则打错牌了。昨晚依然没有迎来我的第一次胡牌 -_-

        考完了，放假了，轻松了。下学期LanQ去百度了，昨天又谈到了基金的事，谁叫我是大三的呢，欢欢都不怕，我就更不怕了，哈哈。不过LanQ提议北京和上海应该给同样多的基金，那欢欢就惨了。反正我无所谓，关注事态发展^-^。

23号早上7:30 T122，24号下午1点到长沙，一年没回家，说实话，想家了，而且是相当想家。再见了长春的朋友，永别了2006学年。

Naruto 328

sharang — Sat, 21 Oct 2006 04:00:00 GMT

        ASM大叔死了~
        AB就这么让ASM挂了，临死之前爆发的机会都没给...

        在论坛里看到这样一段话，觉得和他有那么点共鸣，不过主要还是为了娱乐啦^-^：

        火影里有些东西是非常值得我们学习的，比如，鸣人的直着，就非常让我感动。这条不多说了，大家应该都发现了，只是没把它当成火影的主要看点吧。我觉得，火影告诉我们的不仅仅是这个道理，还有团队精神、大家同心协力保家卫国的凝聚力（音和砂进攻木叶的时候，感觉跟抗日战争好像。。。），等等等等。

　　给我印象最深的，就是大蛇丸曾经对君麻吕说过的一句话：“人活着，本来就没什么意义，可是只要活下去，就一定会有快乐的事情发生。”这句，可能很少有人注意到吧。我认为这句话非常精辟。它告诉我们，生命只有一次，就算你生平取得了多么巨大的成就，到头来的归宿还是一样，表面看似生命没什么意义。但是，就是因为生命只有这么一次，我们既然来到了这个世界上，我们就是幸运的，就一定要尽自己的努力，把这一生好好地度过。所以，就算生活再怎么艰苦，也要坚强地活下去，阳光总在风雨后。

二分搜索

sharang — Tue, 10 Oct 2006 05:58:00 GMT

        二分搜索，简单?复杂?代码其实就几行，但如果不小心还真会很麻烦。

        去年暑假在翠文RP大爆发写了个二分搜索，自己都觉得经典，今天突然想贴出来。^-^

        主要还是借用了STL中左闭右开的表示方法...

// 在[l, r)范围内查找值v，返回下标
// 假设a数组已经按从小到大排序
// 失败返回-1
int bs(int a[], int l, int h, int v)
{
    int m;
    while ( l < h )
    {
        m = ( l + h ) >> 1;
        if (a[m] == v) return m;
        if (a[m] <  v) l=m+1;
        else           h=m;
    }
    return -1;
}

如果想找大于等于v的第一个值，稍微修改一下就OK了。

// 传入参数必须l <= h
// 返回值l总是合理的
int bs(int a[], int l, int h, int v)
{
    int m;
    while ( l < h )
    {
        m = ( l + h ) >> 1;
        if (a[m] < v) l=m+1;
        else          h=m;
    }
    return l;
}

其实最酷的部分还是函数名，差点就是sb了...

哈希匹配

sharang — Thu, 05 Oct 2006 04:31:00 GMT

        字符串匹配有很多很好的算法，其中有一个Karp-Rabin，期望复杂度很好。

        设匹配串char T[N];        模式串char P[M];

        KR算法的特点：
        将模式串哈希，如果匹配串中的某一段与模式串的哈希值相等，再进行内容的比较；
        预处理阶段用0(N)的复杂度算出匹配串中(N-M+1)个长为M的子串的哈希值；
        比较阶段，最坏复杂度0((N-M+1)*M)，期望复杂度O(N+M)。

        这里有两个问题需要解决：
        1.如何选择hash函数。
        2.如何在线性时间内算出匹配串的所有哈希值。

        第一个问题，通常用以下看似有点复杂的hash函数，它既描述了串的内容，也记录了串的顺序：
        hash( P ) = ( P₀ * d^m-1 + P₁ * d^m-2 + ... + P_m-1 * d⁰ ) % q
                      = (...( P₀ * d + P₁ ) * d + P₂ ) * ... ) * d + P_m-1) % q
        虽然这个哈希函数的表达式比较复杂，不过计算还是相当简单的，O(M)的一个循环就可以搞定。

        第二个问题，怎样在O(1)的时间内算出T[i...i+m-1]的哈希值呢?注意到这个hash函数是有继承性的，也就是后一个hash值可以由前一个算出：
        hash( T[i...i+m-1] ) = ( hash( T[i-1...i+m] ) - T_i-1 * d^m-1 ) * d + T_i+m-1
        d和q的选择：
        上面哈希函数中d，有选2的，这样可以用二进制移位操作，简化了计算；也可以选其他数。q可以选大素数，但计算机中%的计算是很耗时的，所以一个不错的注意是让q = 2³²，这样取模运算就可以让硬件来办了。但这个时候d就不能选2了，因为m>32时，d=2，q=2³²，串的高位信息将丢失。可以用11或者27代替。

        COLLISION
        伴随hash而来的就是冲突判定问题了，就是当两个串的hash值相等时的判断。KR算法中，如果hash( P ) = hash( T[i...i+m-1] )，要继续用O(M)的循环判断两个串是否相等。但有时候也可以省略这个步骤(在ACM中)。如果WA，可以换一个q或者d，换几次应该就AC了，只是有点无赖了 ^ - ^

amusing lucky number

sharang — Fri, 29 Sep 2006 06:14:00 GMT

Lucky numbers are defined by a variation of the well-known sieve of Eratosthenes. Beginning with the natural numbers strike out all even ones, leaving the odd numbers 1, 3, 5, 7, 9, 11, 13, ... The second number is 3, next strike out every third number, leaving 1, 3, 7, 9, 13, ... The third number is 7, next strike out every seventh number a.s.o. The numbers surviving are called lucky numbers. The first lucky numbers are:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303, 307, 319, 321, 327, 331, 339, 349, 357, 361, 367, 385, 391, 393, 399, ...

What’s remarkable is that the "luckies," though generated by a sieve based entirely on a number’s position in an ordered list, share many properties with primes. For example, there are 25 primes less than 100 and 23 luckies less than 100. Indeed, it turns out that primes and luckies come up about equally often within given ranges of integers. The distances between successive primes and the distances between successive luckies also keep increasing as the numbers increase. In addition, the number of twin primes -- primes that differ by 2 -- is close to the number of twin luckies.

        Perhaps the most famous unsolved problem involving primes is the Goldbach conjecture, which states that every even number greater than 2 is the sum of two primes. Luckies are featured in a similar conjecture, also unsolved: Every even number is the sum of two luckies. Computer searches have reached at least 100,000 without finding an exception.

        SEE ALSO

        http://online-judge.uva.es/p/v109/10909.html

        http://www.wschnei.de/number-theory/lucky-numbers.html

        http://www.sciencenews.org/pages/sn_arc97/9_6_97/mathland.htm

独孤酒剑·重出江湖

很久了

Naruto 328

二分搜索

哈希 匹配

amusing lucky number

哈希匹配