Feb 19

异或交换技巧的陷阱 不指定

felix021 @ 2009-2-19 17:31 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3812) | Via 本站原创
众所皆知,以下代码可以实现两个变量的交换:
int a, b;
a = a ^ b;
b = a ^ b;
a = a ^ b;

于是用这个写了一个随机化快速排序(防止特殊情况下的算法退化,代码很简单,如果认识快排,应该不难读懂)
void qsort(int a[], int s, int e){
    int i = s, j = e, t, p;
    if (s < e){
        p = rand() % (e - s + 1) + s;
        a[s] ^= a[p], a[p] ^= a[s], a[s] ^= a[p];
        t = a[s];
        while(i != j){
            while(i < j && a[j] > t) j--;
            if(i < j) a[i++] = a[j];
            while(i < j && a[i] < t) i++;
            if(i < j) a[j--] = a[i];
        }
        a[i] = t;
        qsort(a, s, i - 1);
        qsort(a, i + 1, e);
    }
}

看起来不错,可是运行结果不对,为什么呢?
因为
Feb 11

汇编版Hello World 不指定

felix021 @ 2009-2-11 16:28 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4190) | Via 本站原创
今天回顾汇编,顺手写了一个,居然还可以运行,挖咔咔,自恋一下

datas   segment use16
str1    db      "hello world!", 0dh, 0ah, "$"
datas   ends

stacks  segment use16
          db  256 dup(0)
stacks  ends

codes  segment use16
          assume  cs:codes, ds:datas, ss:stacks
start:  mov ax, datas
         mov ds, ax
         lea dx, str1
         mov ah, 09h
         int 21h
         mov ah, 4ch
         int 21h
codes  ends
         end start
Tags:
Feb 5

开始你的ICPC之旅 不指定

felix021 @ 2009-2-5 00:54 [IT » 程序设计] 评论(8) , 引用(0) , 阅读(5402) | Via 本站原创
这篇文章尾烂了,大家多给点意见,好充实其中的内容;也提出里面的不足。

---

我觉得这样的文章应该有人写过的,但是Google里面貌似没有(或许有英文版)
Baidu给了一个,不过不是很像样 http://baike.baidu.com/view/94274.htm
那我就写一个吧,这也是momodi大牛在上个学期初委托给我的一件事情。

这篇文章面向的对象是没有多少基础,或者是才学C语言或数据结构的同鞋们。

--

首先,什么是acm/icpc?ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM(Association for Computing Machinery,国际计算机协会)主办的,世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。
——这段定义来自 百度百科 -> ACM/ICPC,其实说简单了就几个字:想算法,写程序,解题目
Jan 11

C++ FAQ中文版 不指定

felix021 @ 2009-1-11 21:37 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4988) | Via 本站原创
sandy跟说说过好多次。
这是CPPFAQ的中文翻译版,只翻译了一部分
非常值得一看。

http://www.sunistudio.com/cppfaq/
Jan 9
这是今天算法考试的最后一题,设计一个动态规划的算法来求两个字符串的编辑距离。
以为自己做对了,很happy —— 其实错了,好笨,sigh.

--

Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离),它用来表示2个字符串的相似度,LD定义为需要最少多少步基本操作才能让2个字符串相等,基本操作包含3个:插入, 删除, 替换;比如,kiteen和sitting之间的距离可以这么计算:  
          1,kitten   --   >   sitten,   替换k为s;  
          2,sitten   --   >   sittin,   替换e为i;  
          3,sittin   --   >   sitting,   增加g;  
所以,其LD为3。

设计状态d[m][n] = d(A[1..m], B[1..n]),易知:
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
                   d[i-1][j] + 1, //插入一个字符
                   d[i][j-1] + 1  //删除一个字符

于是可以递推地填满一个 m * n 的矩阵,即得答案。
计算LD的算法表示为(C++代码):  
int d[1010][1010];
int dist(string a, string b){
    int m = a.size(), n = b.size(), i, j;
    for(i = 0; i <= m; ++i) d[i][0] = i;
    for(j = 0; j <= n; ++j) d[0][j] = j;
    for (i = 1; i <= m; ++i){
        for(j = 1; j <= n; ++j){
            //    --------------     a, b是从0开始计数的
            d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
            d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
            d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
        }
    }
    for (i = 0; i <= m; ++i){ //打印矩阵
        for(j = 0; j <= n; ++j)
            printf("%5d ", d[i][j]);
        printf("\n");
    }
    return d[m][n];
}

这个算法其实就是一个矩阵的计算:  
引用
调用dist("abcdef", "acddaf")可以得到输出为:
    0     1     2     3     4     5     6
    1     0     1     2     3     4     5
    2     1     1     2     3     4     5
    3     2     1     2     3     4     5
    4     3     2     1     2     3     4
    5     4     3     2     2     3     4
    6     5     4     3     3     3     3

最后的d[m][n]就是求得的答案。

@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组):
int diff(char *a, char *b){
    int *d[2], i, j;
    int m = strlen(a), n = strlen(b);
    d[0] = new int[n + 1];
    d[1] = new int[n + 1];
    int turn = 0, pre, t;
    for (i = 0; i <= n; ++i) d[turn][i] = i;
    for (i = 1; i <= m; ++i){
        pre = turn;
        turn = (turn + 1) % 2;
        d[turn][0] = i;
        for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
        for(j = 1; j <= n; ++j){
            t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
            t = min(t, d[pre][j] + 1);
            d[turn][j] = min(t, d[turn][j-1] + 1);
        }
    }
    for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
    t = d[turn][n];
    delete[] d[0];
    delete[] d[1];
    return t;
}
Jan 8

学习了0-1背包 不指定

felix021 @ 2009-1-8 17:11 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(4155) | Via 本站原创
其实好简单的=.= 为啥以前没去看捏。。。

已知有n个东东为u[1]~u[n], 体积和重量分别是s[1]~s[n]和w[1]~w[n]
有一个包包可以装下大小为S的东东,求这个包包最重可以装多重。
记W[n][S]为要求的东西: 从n个东东里面取出一部分填满体积为S的包包
很容易理解,W[n][S]为以下两个取值的最大值:
1. W[n-1][S] 不取第n个东东,最多可以装多重
2. (s[n] <= S的时候) w[n] + W[n-1][S-s[n]] 一定取第n个东东,重量为v[n],包包还能装S-s[n],那么前n-1个东东最多可以装多重。
另外,显然可以看出,当n或者S为0的时候,W[n][S]肯定也为0。
最简单的是写一个递归:
Jan 8
昨天看的《C++标准函数库》,看到auto_ptr这一节,说到了关于内存泄露的问题
而且有些情况以前根本没有考虑到,想想觉得好危险。
典型的情况就是如下的代码:
void foo(){
  int *p = new int[10];
  //do sth.
  delete[] p;
}

如果在//do sth.的时候退出了函数,比如一个return语句,或者是抛出了一个异常
那么最后的delete p就不会被执行,于是就造成了内存的泄露。
更极端一点的情况是,可能申请了多个内存,有多处return,如果每一个都要处理,那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决,于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
#include<memory>  //auto_ptr在头文件memory里面哦
using namespace std::auto_ptr;  //它在namespace std里面哦

void foo(){
  std::auto_ptr<classA> p(new classA);
  //do sth.
  //no need to free p;
}

在退出函数foo()的时候,p的析构函数会被调用,自动释放它指向的classA,于是再也不用费神去写delete了,真好~

不过auto_ptr不是基于引用计数的智能指针,所以有一些很特殊的属性。
如果想要用它,一定一定要都了解了才用哦!就推荐看这本书《The C++ Standard Library》C++标准函数库。
Dec 29

return语句引起的栈错误 不指定

felix021 @ 2008-12-29 20:28 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4331) | Via 本站原创
被牛逼哄哄的Snoopy雷到了。

事情是这样的,今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下,发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息,但是看不太懂~

DEBUG了一阵,定位到了错误:在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的:
......
bool Restricted_Function(){
    char f[30], ...;
    ......
    cout << "DEBUG 1" << endl;
    return false;
}

......

bool WOJ_JUDGE(){
    ......
    cout << "DEBUG 0“ << endl;
    if(Restricted_Function(){
        cout << "DEBUG 2" << endl;
        return RF;
    }
    cout << "DEBUG 2" << endl;
    ......
}

然后发现非常神奇地,程序输出的是
引用
DEBUG 0
DEBUG 1
然后跟上一堆程序出现错误的信息。
于是我就懵了,居然一个return语句也能出现错误?

然后请教snoopy大牛,经过一番七荤八素的DEBUG以后,终于找到了症结所在:
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的,所以在运行的时候,出现了少量越界写入的情况
在程序返回的时候,由于返回地址等被未预料到的字符覆盖了,于是就出现了上述问题。

一个return语句也能"出错",暴露出这样严重的内存使用问题
——可能存在于任何地方,写程序的时候务必要小心啊!

同时,通过这种方式"定位"到的错误点,未必就是错误真正发生的地方!
分页: 14/22 第一页 上页 9 10 11 12 13 14 15 16 17 18 下页 最后页 [ 显示模式: 摘要 | 列表 ]