技术手记

Coding in Java

Posted on by snoopy

For the course, and for learning a useful skill, start coding in Java. Java is the third programming language I learned strictly, before it are Pascal and C. There is more easy that when you have used a programming language skilled to study another, because the ideas are the same, only the method to get the result are different. The last words may be wrong, because Java is an OO(Object Oriented) language, which is different to the Process-Oriented language likes Pascal/C, and I said I learned C only as I didn’t know the ideas of OO in C++.

In Java, everything is long, the name of class, function, variable, too long to type… I love C, I love VIM, which can do anything use keyboard only. Our Java text book used the Hungarian notation ordinary, so it’s a good way to make my coding habit standardization.

最优匹配(Kuhn_Munkras算法)

Posted on by snoopy 
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1

int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    fx[u]=1;
    for(v=1;v<=ny;v++)
        if((lx[u]+ly[v]==w[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret=0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i=1;i<=nx;i++) {
        lx[i]=-INF;
        for(j=1;j<=ny;j++)
            if(w[i][j]>lx[i])
                lx[i]=w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k=1;k<=nx;k++)
                if(fx[k]>0)
                    for(j=1;j<=ny;j++)
                        if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
                            p=lx[k]+ly[j]-w[k][j];
            for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
            for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************

最大匹配(匈牙利算法)

Posted on by snoopy 
// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1

int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];

int path(int u)
{
    int v;
    for(v=1;v<=ny;v++)
        if((mat[u][v])&&(fy[v]<0)) {
            fy[v]=1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u]=v;
                maty[v]=u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((mat[u][v]...
    return(0);
} // end of int path()

int MaximumMatch()
{
    int i,ret=0;
    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i=1;i<=nx;i++)
        if(matx[i]<0) {
            memset(fy,-1,sizeof(fy));
            ret+=path(i);
        } // end of if(matx[i]...
    return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************

KMP

Posted on by snoopy

直接抄的武大李春葆老师的数据结构上的改进KMP

// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000

typedef struct
{
    char ch[MaxSize];
    int len;
} SqString;

void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.len)
    {
        if((k==-1)||(t.ch[j]==t.ch[k]))
        {
            j++;
            k++;
            if(t.ch[j]!=t.ch[k]) nextval[j]=k;
            else nextval[j]=nextval[k];
        }
        else k=nextval[k];
    }
}

int KMP(SqString s,SqString t)
{
    int nextval[MaxSize],i=0,j=0,v;
    GetNextval(t,nextval);
    while((i<s.len)&&(j<t.len))
    {
        if((j==-1)||(s.ch[i]==t.ch[j]))
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>=t.len) v=i-t.len;
    else v=-1;
    return(v);
}

int main()
{
//    freopen("kmp.in","r",stdin);
//    freopen("kmp.out","w",stdout);

    SqString str1,str2;
    gets(str1.ch);
    str1.len=strlen(str1.ch);
    gets(str2.ch);
    str2.len=strlen(str2.ch);
    printf("%dn",KMP(str1,str2));
    return(0);
}

RMQ

Posted on by snoopy

从whummd的blog上copy来的,加了点自己的修改,正在看,集训加油

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%dn",RMQ(start,end));
    return 0;
}

在尝试IE7beta2和WindowsMediaPlayer11

Posted on by snoopy

RT.好奇啊…本来不是这么喜欢尝鲜的人的,但是挂在山水上做Software斑竹,好歹也要在其位谋其政吧.最近试用的东西不是太多了,但是比较敏感的东西还是在试,比较有代表性的就是IE7beta2和WindowsMediaPlayer11了吧.
自己已经发的关于这两个东西的意见都在武大珞珈山水BBS的Software上,也上了一些图.有图的Link写一下吧:
http://202.114.68.70/bbscon.php?bid=46&id=13141
http://202.114.68.70/bbscon.php?bid=46&id=13139
http://202.114.68.70/bbscon.php?bid=46&id=13000
http://202.114.68.70/bbscon.php?bid=46&id=12999

下面开始介绍,IE7beta2是微软官方发布的,所有WindowsXP用户均可使用,当然,现在要通过正版验证.我下了后传了一个到C.S.的ftp上,有兴趣的可以去看看.
ftp://cs:cs2006@cs.whu.edu.cn/incoming/IE7B2P-WindowsXP-x86-enu.exe

现在只有英文版的,还好一般软件的英文还是挺简单的,特别是这种常用软件,菜单也都能背下来了.IE7变PP了很多,很有Vista的风格,传统的菜单栏默认是不显示的,从而腾出了更多空间来浏览页面.

IE7默认就是分页浏览(Tabs),对Tab的配置可以进入Option里面调整(就是Internet选项啦),IE7还是加入了不少的新内容需要去适应.我的习惯都是在新的Tab里面打开网页,所以调了一下.不过好像在很多地方反应还是没Maxthon好,还是会去打开一个新的窗口就是一个新的IE而不是一个新的Tab.还有一个不是很爽的地方就是默认都是激活新的Tab页,没找到类似Maxthon那个选项,即打开新Tab后当前激活Tab是目前的还是新的.IE7里面对Tab的控制个人感觉还是不够人性化,经常出现点开一个新的Link然后覆盖了当前查看的内容.Tabs这个新的功能对那些习惯了Maxthon的人很不错,并且在打开非常多的Tab的时候上面不会成为一排密密麻麻的小标签,而是保持了一个最小宽度,左右加入了<>这样的滑动按钮.关闭Tab方面,IE7在有多个Tab的时候会在当前激活Tab的标签右边出现一个X号来关闭,要关闭非激活Tab需要先点激活然后关闭,无法跟Maxthon一样通过双击来实现.在只有一个Tab的情况下,无法关闭此Tab,就是说,没办法保持只有一个空的页面,当然,也可以通过新开一个新空白Tab然后关闭有内容的.存在多个Tab的情况下,IE7加入了一个缩略页的功能,可以同时显示多个小页面,能比较方便找到自己要的页面然后直接点开.

IE7里面加入的Feed是我非常喜欢的功能,虽然RSS这个Web2.0的一个前端概念早就知道也通过其他一些乱七八糟的RSS阅读器了解了一下,不过一直没太去刻意用这个.最近去看了看很多好朋友的Blog,发现如果只是用浏览器一个一个打开太慢了,刚好有Feed这个功能,就整合进去算了.现在没事刷新看看有没更新.然后打开Feed看,风格都比较统一,比较顺眼 :P

关于MS历来是一个诟病的资源占用问题,beta2的IE7解决的还是不好.我一般使用下都是75-90M内存,今天中午居然都截到了占有240M+内存,90%+CPU的图,当然,那个是我在开多个包含Flash,图片并且正在打开过程中截的,平时用Maxthon遇见这种情况也是比较卡.不过现在还好,我的Sempron2400+(1.833G)和512M内存跑起来没卡的感觉.

说完了IE7,我们来讨论WMP11,WMP11发布的消息我是在几天前知道的,然后就有人说5.17正式发布XP版,不过在昨天5Q上开始有泄漏出来的下载,开始没敢下,怕病毒,后来有人用了没问题就用吧.同样的,我也传了一个到C.S.的ftp服务器上:
ftp://cs:cs2006@cs.whu.edu.cn/incoming/mpsetup.exe

中午才下到的,没仔细测试乱七八糟的功能.第一反应是:PP了好多,为了Vista啊…然后是:真PP.

系统资源占有方面,没仔细注意,反正不卡,我上面那个IE截图240+M内存的时候就开了WMP.没去MS的主页看WMP11到底改变了什么,对我有影响的就是界面好看了很多,然后Library也好看了很多,没细看Library的功能变化.在对文件格式的支持上,我一般听的mp3和wma都没问题,不过还是不支持ape/cue,不能不说是一个遗憾.

WMP11还是没有加入官方的新皮肤,就是skin mode里面的,现在大家貌似还都是在用的9里面的那个,其他的个人都觉得不是很PP…

用了半天WMP11,唯一的感觉就是PP了好多,其他,没有了.呵呵,以后有了可以再发吧.

机器今天晚上准备重装,习惯…机器一直都还在裸奔,中毒不浅,QQ还连续被盗了两次,第一次是我去重庆了,结果天天在发垃圾消息,回来后被好友名单里半数拉黑名单了.55~第二次就在昨天吧,不过更多的是怀疑是系统的问题,好友丢失了近50个,奇怪.

西方俗语说:好奇会使猫丧命.希望不要太好奇真的让偶家猫猫挂了.乌鸦嘴:P

读书计划

Posted on by snoopy

不能一直只沉迷于同一件事情上,开始好好学点实用的东西.给自己一个计划,让自己好好进步.

HTML语言入门.五一前看完书,做基本的应用,开始接手维护OJ的首页.
离散数学及其应用.花一个学期好好看看吧,计算机科学的灵魂所在.
DreamWeaver.考四级前看完,能基本应用,以后可以考虑自己做东西玩.
Windows编程.用2个星期看完,串讲式的看一遍,了解一下.

有能力去看看asp和jsp吧,以后还想去维护OJ玩呢.

最后,四级.过掉,最好能漂亮的过掉.