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++代码)：
这个算法其实就是一个矩阵的计算：
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
以为自己做对了，很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];
}
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
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;
}
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
其实好简单的=.= 为啥以前没去看捏。。。
已知有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。
最简单的是写一个递归：
已知有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这一节，说到了关于内存泄露的问题
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
如果在//do sth.的时候退出了函数，比如一个return语句，或者是抛出了一个异常
那么最后的delete p就不会被执行，于是就造成了内存的泄露。
更极端一点的情况是，可能申请了多个内存，有多处return，如果每一个都要处理，那程序就太恶心了。
但是不处理又是不行的——于是需要有一种方式来解决，于是标准库就引进了auto_ptr 智能指针。
这个东西保证它自己被销毁的时候能够释放其指向的对象(使用delete)。
一个简单的例子是:
在退出函数foo()的时候，p的析构函数会被调用，自动释放它指向的classA，于是再也不用费神去写delete了，真好～
不过auto_ptr不是基于引用计数的智能指针，所以有一些很特殊的属性。
如果想要用它，一定一定要都了解了才用哦！就推荐看这本书《The C++ Standard Library》C++标准函数库。
而且有些情况以前根本没有考虑到，想想觉得好危险。
典型的情况就是如下的代码：
void foo(){
int *p = new int[10];
//do sth.
delete[] p;
}
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;
}
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
被牛逼哄哄的Snoopy雷到了。
事情是这样的，今天打开 http://acm.whu.edu.cn/woj 检查oak的运行情况
发现在status的第二页有好多个submit都处于Running状态
ssh到服务器上去看了一下，发现Judge在Compile OK以后就挂掉了。
有一堆Stack的信息，但是看不太懂~
DEBUG了一阵，定位到了错误：在判断Restricted_Function的那个函数里面。
加入了调试代码以后的大概结构是这样的：
然后发现非常神奇地，程序输出的是
然后跟上一堆程序出现错误的信息。
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
事情是这样的，今天打开 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;
......
}
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
DEBUG 1
于是我就懵了，居然一个return语句也能出现错误？
然后请教snoopy大牛，经过一番七荤八素的DEBUG以后，终于找到了症结所在：
原来在Restricted_Function里面定义的那个char f[30]空间太小了
由于是分配在栈空间里面的，所以在运行的时候，出现了少量越界写入的情况
在程序返回的时候，由于返回地址等被未预料到的字符覆盖了，于是就出现了上述问题。
一个return语句也能"出错"，暴露出这样严重的内存使用问题
——可能存在于任何地方，写程序的时候务必要小心啊！
同时，通过这种方式"定位"到的错误点，未必就是错误真正发生的地方！
Dec
29
#include<iostream>
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
using namespace std;
char l[] = "Felix021";
void print(char a){
for(int i = 7; i >= 0; --i){
cout << ((a >> i ) & 1);
}
}
int main(){
for(int i = 0; l[i]; ++i){
print(l[i]);
}
cout << endl;
return 0;
}
Dec
7
momodi同学說得很对，嗯。
--
貌似新人们总会遇到几个问题，提一下吧。
1. 64Bit整型的问题
这个东西比较纠结阿。一般来说
在VC下面，定义的时候要用__int64
用g++/gcc的时候，则应该用long long定义
在Windows下面，输入输出的时候要用%I64d这个格式
在类Unix(包括Solaris/Linux等)下面，输入输出的时候要用%lld这个格式
对于各类OJ，不妨自己在A+B这道题上试试
参加比赛的时候，务必向工作人员或者judge问清楚编译环境
——包括操作系统和编译器。
2. 大数组RE的问题
emingCup的时候就有队伍遇到这个问题
自己运行的时候都RE还交过来。
这个涉及到编译器对不同类型变量的内存分配规则。
在C/C++中
--
貌似新人们总会遇到几个问题，提一下吧。
1. 64Bit整型的问题
这个东西比较纠结阿。一般来说
在VC下面，定义的时候要用__int64
用g++/gcc的时候，则应该用long long定义
在Windows下面，输入输出的时候要用%I64d这个格式
在类Unix(包括Solaris/Linux等)下面，输入输出的时候要用%lld这个格式
对于各类OJ，不妨自己在A+B这道题上试试
参加比赛的时候，务必向工作人员或者judge问清楚编译环境
——包括操作系统和编译器。
2. 大数组RE的问题
emingCup的时候就有队伍遇到这个问题
自己运行的时候都RE还交过来。
这个涉及到编译器对不同类型变量的内存分配规则。
在C/C++中
Nov
15
#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
int main(){
vector<int>a;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(a));
sort(a.begin(), a.end());
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
return 0;
}
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
int main(){
vector<int>a;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(a));
sort(a.begin(), a.end());
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
return 0;
}
Nov
4
这两天在看密码学的大作业，写一个DES加密程序，里面有很多涉及位运算的东西。
虽然直接用bitset写，但是非常非常地不顺手，于是自己写了一个类，里头有DES需要的运算，恩。
如果谁发现有错的话，麻烦告诉我一声。
好久没有写这样的代码了，一个简单的类居然花了这么久。囧。
虽然直接用bitset写，但是非常非常地不顺手，于是自己写了一个类，里头有DES需要的运算，恩。
如果谁发现有错的话，麻烦告诉我一声。
好久没有写这样的代码了，一个简单的类居然花了这么久。囧。
