Aug
16
@ 2009-05-25 其实早就发现了这个代码有严重的内存泄露问题，不过懒得改了。。。
------
实现重载了等于= 加法+ 减法- 矩阵乘法* 矩阵幂^(使用快速幂算法) 输出<< 输入>>，用起来会比较方便了，不过就是有点长。
查了好久快速幂算法，网上居然没有现成的，于是只好自己再推一遍，先贴出是整数的快速幂算法：
下面是矩阵类的代码:
------
实现重载了等于= 加法+ 减法- 矩阵乘法* 矩阵幂^(使用快速幂算法) 输出<< 输入>>，用起来会比较方便了，不过就是有点长。
查了好久快速幂算法，网上居然没有现成的，于是只好自己再推一遍，先贴出是整数的快速幂算法：
int Pow(int x, int y){
int ans, b, i;
if(y == 0)return 1;
if(y < 0) return -1;
for(i = y, b = 0; i > 0; i >>= 1) b++;
for(ans = 1, i = b - 1; i >= 0; i--){
if(y & (1 << i)){
ans = ans * ans * x;
}else{
ans = ans * ans;
}
}
return ans;
}
int ans, b, i;
if(y == 0)return 1;
if(y < 0) return -1;
for(i = y, b = 0; i > 0; i >>= 1) b++;
for(ans = 1, i = b - 1; i >= 0; i--){
if(y & (1 << i)){
ans = ans * ans * x;
}else{
ans = ans * ans;
}
}
return ans;
}
下面是矩阵类的代码:
#include<iostream>
#include<math.h>
using namespace std;
template <typename T>
class Matrix{
//class Matrix by felix021
//usage: Matrix<typename> varname(row, col[, mod]);
//如果typename不是short/int/long/long long
//那么取模运算需要包含math.h头文件(使用fmod函数)
//取模运算的代码仅在 + - * 三个函数内.
public:
T **data;
Matrix *temp;
int row, col, modnum;
//无参构造函数，没有给定矩阵的大小时，输出错误提示
Matrix(){
printf("Size parameter invalid!\n");
}
//构造函数， r是行数，c是列数，若给定m>0, 则在求和/差/积时对m取模
Matrix(int r, int c, int m = 0){
int i;
temp = NULL;
row = r, col = c;
data = new T *[r]; //分配一个 T *[r]类型的数组给data
for(i = 0; i < r; i++){
data[i] = new T [c]; //给data下的每个指针分配内存, 类型为 T [c]
}
if(m > 0) modnum = m;
else modnum = 0;
}
//析构函数，用于释放分配的内存
~Matrix(){
int i;
if(temp != NULL){delete temp; }
for(i = 0; i < row; i++) delete data[i];
delete data;
}
//赋值，给第i行第j列的元素赋值为 a
void assign(int i, int j, const T a){
if(i < 0 || i >= row || j < 0 || j >= col) {
printf("Invalid row/column number.\n");
return;
}else{
data[i][j] = a;
}
}
//取出元素，给第i行第j列的元素的值
T at(int i, int j){
if(i < 0 || i >= row || j < 0 || j >= col) {
printf("Invalid row/column number.\n");
return;
}else{
return data[i][j];
}
}
//重载<<运算符，可用cout输出
friend inline ostream & operator<<(ostream &os, const Matrix &a){
int i, j;
for(i = 0; i < a.row; i++){
for(j = 0; j < a.col - 1; j++){
os << a.data[i][j] << " ";
}
os << a.data[i][j];
os << endl;
}
return os;
}
//重载>>运算符，可用cin输入
friend inline istream & operator>>(istream &is, const Matrix &a){
int i, j;
for(i = 0; i < a.row; i++){
for(j = 0; j < a.col; j++){
is >> a.data[i][j];
}
}
return is;
}
//重载=运算符，要求两个矩阵的大小相同
Matrix & operator = (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
data[i][j] = a.data[i][j];
if(modnum > 0){
data[i][j] = mod(data[i][j]);
}
}
}
return *this;
}
//重载+运算符，要求两个矩阵的大小相同
Matrix & operator + (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
temp->data[i][j] = data[i][j] + a.data[i][j];
if(modnum > 0){
temp->data[i][j] = mod(temp->data[i][j]);
}
}
}
return *temp;
}
//重载-运算符，要求两个矩阵的大小相同
Matrix & operator - (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
temp->data[i][j] = data[i][j] - a.data[i][j];
if(modnum > 0){
temp->data[i][j] = mod(temp->data[i][j] + modnum);
}
}
}
return *temp;
}
//重载*运算符，要求矩阵a的列数等于b的行数
Matrix & operator * (const Matrix &a){
int i, j, k;
T tmp;
if(col != a.row){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, a.col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < a.col; j++){
tmp = 0;
for(k = 0; k < a.row; k++){
tmp += data[i][k] * a.data[k][j];
if(modnum > 0){
tmp = mod(tmp);
}
}
temp->data[i][j] = tmp;
}
}
return *temp;
}
//重载^运算符，要求矩阵的列数等于行数
Matrix & operator ^ (const int a){
int i, j;
if(row != col){
printf("No n*n matrix!\n");
return *this;
}
if(a < 0){
printf("Invalid a(%d)!\n", a);
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){ //单位方阵
for(j = 0; j < col; j++){
if(i == j )temp->data[i][j] = 1;
else temp->data[i][j] = 0;
}
}
for(i = a, j = 0; i > 0; i >>= 1) j++;
for(i = j - 1; i >= 0; i--){
if(a & (1 << i)){
*temp = *temp * *temp * (*this);
}else{
*temp = *temp * *temp;
}
}
return *temp;
}
//重载求模函数，对int, long, long long, float, double都有效
int mod(int i){
return i % modnum;
}
long mod(long i){
return i % modnum;
}
long long mod(long long i){
return i % modnum;
}
float mod(float i){
return fmod(i, modnum);
}
double mod(double i){
return fmod(i, modnum);
}
};
int main(){
int i, j;
Matrix <int> t(2, 2), t1(2, 2), t2(2, 2), a(5, 10, 7), b(10, 5), c(5, 5);
cout << "(cin/cout test)\nPlease input 2 (2*2) Matrix: \n";
cin >> t;
cout << t << endl;
t1 = t * t * t * t * t;
t2 = t ^ 5;
cout << "t^5 = \n" << t1 << endl << t2 << endl;
getchar();
for(i = 0; i < 5; i++){
for(j = 0; j < 10; j++){
a.assign(i, j, 1);
b.assign(j, i, 2);
}
}
c = a * b;
cout << "Matrix a:" << endl << a << endl;
cout << "Matrix b:" << endl << b << endl;
cout << "Matrix a * b:" << endl << c << endl;
getchar();
return 0;
}
#include<math.h>
using namespace std;
template <typename T>
class Matrix{
//class Matrix by felix021
//usage: Matrix<typename> varname(row, col[, mod]);
//如果typename不是short/int/long/long long
//那么取模运算需要包含math.h头文件(使用fmod函数)
//取模运算的代码仅在 + - * 三个函数内.
public:
T **data;
Matrix *temp;
int row, col, modnum;
//无参构造函数，没有给定矩阵的大小时，输出错误提示
Matrix(){
printf("Size parameter invalid!\n");
}
//构造函数， r是行数，c是列数，若给定m>0, 则在求和/差/积时对m取模
Matrix(int r, int c, int m = 0){
int i;
temp = NULL;
row = r, col = c;
data = new T *[r]; //分配一个 T *[r]类型的数组给data
for(i = 0; i < r; i++){
data[i] = new T [c]; //给data下的每个指针分配内存, 类型为 T [c]
}
if(m > 0) modnum = m;
else modnum = 0;
}
//析构函数，用于释放分配的内存
~Matrix(){
int i;
if(temp != NULL){delete temp; }
for(i = 0; i < row; i++) delete data[i];
delete data;
}
//赋值，给第i行第j列的元素赋值为 a
void assign(int i, int j, const T a){
if(i < 0 || i >= row || j < 0 || j >= col) {
printf("Invalid row/column number.\n");
return;
}else{
data[i][j] = a;
}
}
//取出元素，给第i行第j列的元素的值
T at(int i, int j){
if(i < 0 || i >= row || j < 0 || j >= col) {
printf("Invalid row/column number.\n");
return;
}else{
return data[i][j];
}
}
//重载<<运算符，可用cout输出
friend inline ostream & operator<<(ostream &os, const Matrix &a){
int i, j;
for(i = 0; i < a.row; i++){
for(j = 0; j < a.col - 1; j++){
os << a.data[i][j] << " ";
}
os << a.data[i][j];
os << endl;
}
return os;
}
//重载>>运算符，可用cin输入
friend inline istream & operator>>(istream &is, const Matrix &a){
int i, j;
for(i = 0; i < a.row; i++){
for(j = 0; j < a.col; j++){
is >> a.data[i][j];
}
}
return is;
}
//重载=运算符，要求两个矩阵的大小相同
Matrix & operator = (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
data[i][j] = a.data[i][j];
if(modnum > 0){
data[i][j] = mod(data[i][j]);
}
}
}
return *this;
}
//重载+运算符，要求两个矩阵的大小相同
Matrix & operator + (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
temp->data[i][j] = data[i][j] + a.data[i][j];
if(modnum > 0){
temp->data[i][j] = mod(temp->data[i][j]);
}
}
}
return *temp;
}
//重载-运算符，要求两个矩阵的大小相同
Matrix & operator - (const Matrix &a){
int i, j;
if(row != a.row || col != a.col){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
temp->data[i][j] = data[i][j] - a.data[i][j];
if(modnum > 0){
temp->data[i][j] = mod(temp->data[i][j] + modnum);
}
}
}
return *temp;
}
//重载*运算符，要求矩阵a的列数等于b的行数
Matrix & operator * (const Matrix &a){
int i, j, k;
T tmp;
if(col != a.row){
printf("Unmatch Matrix!\n");
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, a.col, modnum);
for(i = 0; i < row; i++){
for(j = 0; j < a.col; j++){
tmp = 0;
for(k = 0; k < a.row; k++){
tmp += data[i][k] * a.data[k][j];
if(modnum > 0){
tmp = mod(tmp);
}
}
temp->data[i][j] = tmp;
}
}
return *temp;
}
//重载^运算符，要求矩阵的列数等于行数
Matrix & operator ^ (const int a){
int i, j;
if(row != col){
printf("No n*n matrix!\n");
return *this;
}
if(a < 0){
printf("Invalid a(%d)!\n", a);
return *this;
}
if(temp != NULL) delete temp;
temp = new Matrix(row, col, modnum);
for(i = 0; i < row; i++){ //单位方阵
for(j = 0; j < col; j++){
if(i == j )temp->data[i][j] = 1;
else temp->data[i][j] = 0;
}
}
for(i = a, j = 0; i > 0; i >>= 1) j++;
for(i = j - 1; i >= 0; i--){
if(a & (1 << i)){
*temp = *temp * *temp * (*this);
}else{
*temp = *temp * *temp;
}
}
return *temp;
}
//重载求模函数，对int, long, long long, float, double都有效
int mod(int i){
return i % modnum;
}
long mod(long i){
return i % modnum;
}
long long mod(long long i){
return i % modnum;
}
float mod(float i){
return fmod(i, modnum);
}
double mod(double i){
return fmod(i, modnum);
}
};
int main(){
int i, j;
Matrix <int> t(2, 2), t1(2, 2), t2(2, 2), a(5, 10, 7), b(10, 5), c(5, 5);
cout << "(cin/cout test)\nPlease input 2 (2*2) Matrix: \n";
cin >> t;
cout << t << endl;
t1 = t * t * t * t * t;
t2 = t ^ 5;
cout << "t^5 = \n" << t1 << endl << t2 << endl;
getchar();
for(i = 0; i < 5; i++){
for(j = 0; j < 10; j++){
a.assign(i, j, 1);
b.assign(j, i, 2);
}
}
c = a * b;
cout << "Matrix a:" << endl << a << endl;
cout << "Matrix b:" << endl << b << endl;
cout << "Matrix a * b:" << endl << c << endl;
getchar();
return 0;
}
Aug
14
from http://hi.baidu.com/buddhist_byr/blog/item/214bf995f4a30a48d0135e38.html
GDB使用教程
忘了从哪里找到这篇文章的,看了之后对于像我这样的初学者有很大帮助.为了今后参考,在这里把这篇文章贴出来.也希望更多初学者
能够从中受益.这篇文章所有版权归原作者所有.
GDB概述
————
GDB 是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许，各位比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，
但如果你是在 UNIX平台下做软件，你会发现GDB这个调试工具有比VC、BCB的图形化调试器更强大的功能。所谓“寸有所长，尺有所
短”就是这个道理。
一般来说，GDB主要帮忙你完成下面四个方面的功能：
GDB使用教程
忘了从哪里找到这篇文章的,看了之后对于像我这样的初学者有很大帮助.为了今后参考,在这里把这篇文章贴出来.也希望更多初学者
能够从中受益.这篇文章所有版权归原作者所有.
GDB概述
————
GDB 是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许，各位比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，
但如果你是在 UNIX平台下做软件，你会发现GDB这个调试工具有比VC、BCB的图形化调试器更强大的功能。所谓“寸有所长，尺有所
短”就是这个道理。
一般来说，GDB主要帮忙你完成下面四个方面的功能：
Aug
14
from http://www.programfan.com/blog/article.asp?id=20319
没什么好写的，都在《Introduction to Algorithms》里面，老外的教材就是厉害，不像我们国内，计算机类书籍不少，优点是：一、贵，二、内容不全，有时候要学个什么东西查一本书还不行，唉，写书都是为了赚钱，哪有什么好书。
前些天我借了本《算法设计与分析》的书，读着读着发觉怎么好像读过，一想，哦，是这本书里看过，那时候觉得看英文累，印象深刻，原来写中文书还有这么一招，直接翻译来就OK。老外不喜欢东搞西搞，一本书，比砖头还厚，把想说的全说完，全部搞定，简单，容易查阅，买一本一辈子带身边。哈哈，我刚好有一本，影印版的。
这个Priority Queue原来学《数据结构》的时候老师没讲，自己也没重视，现在翻出来学，发现很有用的。
没什么好写的，都在《Introduction to Algorithms》里面，老外的教材就是厉害，不像我们国内，计算机类书籍不少，优点是：一、贵，二、内容不全，有时候要学个什么东西查一本书还不行，唉，写书都是为了赚钱，哪有什么好书。
前些天我借了本《算法设计与分析》的书，读着读着发觉怎么好像读过，一想，哦，是这本书里看过，那时候觉得看英文累，印象深刻，原来写中文书还有这么一招，直接翻译来就OK。老外不喜欢东搞西搞，一本书，比砖头还厚，把想说的全说完，全部搞定，简单，容易查阅，买一本一辈子带身边。哈哈，我刚好有一本，影印版的。
这个Priority Queue原来学《数据结构》的时候老师没讲，自己也没重视，现在翻出来学，发现很有用的。
Aug
13
下载文件 (已下载 1177 次)
Aug
3
此版本的代码可能有问题，查看新版本。
以为会很难，看了一下，居然很容易就看懂了，也自己把代码写出来了（但愿没有错。。）。
RMQ(Range Minimum/Maximum Query)问题：
RMQ问题是求给定区间中的最值问题。当然，最简单的算法是O(n)的，但是对于查询次数很多（设置多大100万次），O(n)的算法效率不够。可以用线段树将算法优化到O（logn)（在线段树中保存线段的最值）。不过，Sparse_Table算法才是最好的：它可以在O(nlogn)的预处理以后实现O(1)的查询效率。下面把Sparse Table算法分成预处理和查询两部分来说明(以求最小值为例)。
以为会很难，看了一下，居然很容易就看懂了，也自己把代码写出来了（但愿没有错。。）。
RMQ(Range Minimum/Maximum Query)问题：
RMQ问题是求给定区间中的最值问题。当然，最简单的算法是O(n)的，但是对于查询次数很多（设置多大100万次），O(n)的算法效率不够。可以用线段树将算法优化到O（logn)（在线段树中保存线段的最值）。不过，Sparse_Table算法才是最好的：它可以在O(nlogn)的预处理以后实现O(1)的查询效率。下面把Sparse Table算法分成预处理和查询两部分来说明(以求最小值为例)。
Aug
1
from http://hi.baidu.com/trooper/blog/item/ad377fd9ee6d072d10df9bc2.html
p.s. Felix终于看懂了, 建议先看看RMQ的实现算法之sparse table
一、最近公共祖先(Least Common Ancestors)
对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。
这里给出一个LCA的例子：
p.s. Felix终于看懂了, 建议先看看RMQ的实现算法之sparse table
一、最近公共祖先(Least Common Ancestors)
对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。
这里给出一个LCA的例子：
