【算法导论】--分治策略Strassen算法（运用下标运算）【c++】

由于偷懒不想用泛型，所以直接用了整型来写了一份

①首先你得有一个矩阵的class Matrix

②Matrix为了方便用下标进行运算，

Matrix的结构如图：(我知道我的字丑。。。)

Matrix.h代码如下：(个人并不喜欢把代码全写在一块，对于阅读者是相当巨大的负担，其实自己受不了（逃）)

 #pragma once

 #include<vector>

 using namespace std;

 class Matrix

 {

 public:

     vector<vector<int>> nums;

     int x0, y0;

     int size;

     Matrix();

     ~Matrix();

     Matrix(int size, int x0, int y0);

     Matrix(Matrix input, int x0, int y0, int size);

     Matrix(vector<vector<int>>input);

     void Display();

     static void MatrixMultiInit(Matrix &A, Matrix &B);

     static Matrix MatrixMulti(Matrix A, Matrix B);

     static Matrix MatrixAdd(Matrix A, Matrix B);

     static Matrix MatrixSub(Matrix A, Matrix B);

 };

Matrix.cpp对类的实现

一，构造，析构函数

 Matrix::Matrix()

 {

 }

 Matrix::~Matrix()

 {

 }

 Matrix::Matrix(int size, int x0, int y0)

 {

     vector<vector<int>> temp(size, *new vector<int>(size));

     for (int i = ; i < size; i++)

         for (int j = ; j < size; j++)

             temp[i][j] = ;

     this->nums = temp;

     this->x0 = x0;

     this->y0 = y0;

     this->size = size;

 }

 Matrix::Matrix(Matrix input, int x0, int y0, int size)

 {

     this->nums = input.nums;

     this->x0 = x0;

     this->y0 = y0;

     this->size = size;

 }

 Matrix::Matrix(vector<vector<int>> input)

 {

     this->nums = input;

     this->x0 = ;

     this->y0 = ;

     this->size = input.size();

 }

二，A+B，A-B实现

 Matrix Matrix::MatrixAdd(Matrix A, Matrix B)

 {

     Matrix result(A.size, , );

     for (int i = ; i < result.nums.size(); i++)

         for (int j = ; j < result.nums.size(); j++)

             result.nums[i][j] = A.nums[A.x0 + i][A.y0 + j] + B.nums[B.x0 + i][B.y0 + j];

     return result;

 }

 Matrix Matrix::MatrixSub(Matrix A, Matrix B)

 {

     Matrix result(A.size, , );

     for (int i = ; i < result.nums.size(); i++)

         for (int j = ; j < result.nums.size(); j++)

             result.nums[i][j] = A.nums[A.x0 + i][A.y0 + j] - B.nums[B.x0 + i][B.y0 + j];

     return result;

 }

三，A*B的实现

 Matrix Matrix::MatrixMulti(Matrix A, Matrix B)

 {

     int n = A.size;

     int halfsize =n / ;

     Matrix result(n, , );

     if (n == )

         result.nums[][] = A.nums[A.x0][A.y0] * B.nums[B.x0][B.y0];

     else

     {

         Matrix tempS[];

         for (int i = ; i < ; i++)

         {

             tempS[i] = *new Matrix(halfsize, , );

         }

         //00--  A.x0,A.y0,halfsize

         //01-- A.x0,A.y0+halfsize,halfsize

         //10--  A.x0+halfsize,A.y0,halfsize

         //11--    A.x0+halfsize,A.y0+halfsize,halfsize

         //00-- B.x0,B.y0,halfsize

         //01-- B.x0,B.y0+halfsize,halfsize

         //10-- B.x0+halfsize,B.y0,halfsize

         //11--    B.x0+halfsize,B.y0+halfsize,halfsize

         tempS[] = tempS[].MatrixSub(*new Matrix(B, B.x0, B.y0 + halfsize, halfsize), *new Matrix(B, B.x0 + halfsize, B.y0 + halfsize, halfsize));//01-11 B

         tempS[] = tempS[].MatrixAdd(*new Matrix(A, A.x0, A.y0, halfsize), *new Matrix(A, A.x0, A.y0 + halfsize, halfsize));//00+01 A

         tempS[] = tempS[].MatrixAdd(*new Matrix(A, A.x0 + halfsize, A.y0, halfsize), *new Matrix(A, A.x0 + halfsize, A.y0 + halfsize, halfsize));//10+11 A

         tempS[] = tempS[].MatrixSub(*new Matrix(B, B.x0 + halfsize, B.y0, halfsize), *new Matrix(B, B.x0, B.y0, halfsize));//10-00 B

         tempS[] = tempS[].MatrixAdd(*new Matrix(A, A.x0, A.y0, halfsize), *new Matrix(A, A.x0 + halfsize, A.y0 + halfsize, halfsize));//00+11 A

         tempS[] = tempS[].MatrixAdd(*new Matrix(B, B.x0, B.y0, halfsize), *new Matrix(B, B.x0 + halfsize, B.y0 + halfsize, halfsize));//00+11 B

         tempS[] = tempS[].MatrixSub(*new Matrix(A, A.x0, A.y0 + halfsize, halfsize), *new Matrix(A, A.x0 + halfsize, A.y0 + halfsize, halfsize));//01-11 A

         tempS[] = tempS[].MatrixAdd(*new Matrix(B, B.x0 + halfsize, B.y0, halfsize), *new Matrix(B, B.x0 + halfsize, B.y0 + halfsize, halfsize));//10+11 B

         tempS[] = tempS[].MatrixSub(*new Matrix(A, A.x0, A.y0, halfsize), *new Matrix(A, A.x0 + halfsize, A.y0, halfsize));//00-10 A

         tempS[] = tempS[].MatrixAdd(*new Matrix(B, B.x0, B.y0, halfsize), *new Matrix(B, B.x0, B.y0 + halfsize, halfsize));//00+01 B

         Matrix tempP[];

         for (int i = ; i < ; i++)

         {

             tempP[i] = *new Matrix(n / , , );

         }

         tempP[] = tempP[].MatrixMulti(*new Matrix(A, A.x0, A.y0, halfsize), *new Matrix(tempS[], , , halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(tempS[], , ,halfsize), *new Matrix(B, B.x0 + halfsize, B.y0 + halfsize, halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(tempS[], , , halfsize), *new Matrix(B, B.x0, B.y0, halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(A, A.x0 + halfsize, A.y0 + halfsize, halfsize), *new Matrix(tempS[], , , halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(tempS[], , , halfsize), *new Matrix(tempS[], , , halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(tempS[], , , halfsize), *new Matrix(tempS[], , , halfsize));

         tempP[] = tempP[].MatrixMulti(*new Matrix(tempS[], , , halfsize), *new Matrix(tempS[], , , halfsize));

         Matrix result00 = result00.MatrixAdd(tempP[], tempP[]);

         result00 = result00.MatrixSub(result00, tempP[]);

         result00 = result00.MatrixAdd(result00, tempP[]);

         Matrix result01 = result01.MatrixAdd(tempP[], tempP[]);

         Matrix result10 = result10.MatrixAdd(tempP[], tempP[]);

         Matrix result11 = result11.MatrixAdd(tempP[], tempP[]);

         result11 = result11.MatrixSub(result11, tempP[]);

         result11 = result11.MatrixSub(result11, tempP[]);

         if (n == ) {

         for(int i=;i<n/+;i++)

             for (int j = ; j < n /  + ; j++) {

             result.nums[i][j]= result00.nums[i][j];

             result.nums[i][j+n/+] = result01.nums[i][j];

             result.nums[i+n/+][j] = result10.nums[i][j];

             result.nums[i+n/+][j+n/+] = result11.nums[i][j];

             }

         }

         for(int i=;i<n/;i++)

             for (int j = ; j < n / ; j++) {

             result.nums[i][j]= result00.nums[i][j];

             result.nums[i][j+n/] = result01.nums[i][j];

             result.nums[i+n/][j] = result10.nums[i][j];

             result.nums[i+n/][j+n/] = result11.nums[i][j];

             }

     }

     return result;

 }

四，防止size%2！=0的处理函数（即矩阵的行列数为奇数）

 void Matrix::MatrixMultiInit(Matrix &A, Matrix &B) {

     if (A.nums.size() %  != )

     {

         for (int i = ; i < A.nums.size(); i++)

             A.nums[i].push_back();

         for (int i = ; i < B.nums.size(); i++)

             B.nums[i].push_back();

         A.nums.push_back(*new vector<int>(A.nums[].size(), ));

         B.nums.push_back(*new vector<int>(B.nums[].size(), ));

         A.size++;

         B.size++;

     }

 }

五，输出函数（这个读者随意）

 void Matrix::Display()

 {

     for (int i = ; i < this->nums.size(); i++) {

         cout << "||";

         for (int j = ; j < this->nums[i].size(); j++) {

             cout << this->nums[i][j] << " ";

         }

         cout << "||" << endl;

     }

 }

六，测试函数

 #include <iostream>

 #include"Matrix.h"

 int main()

 {

     vector<vector<int>> input = {

         {,,},

         {,,},

         {,,},

     };

     Matrix test0 (input);

     Matrix test1 (input);

     Matrix test2;

     test2.MatrixMultiInit(test0, test1);

     test2= test2.MatrixMulti(test0, test1);

     test2.Display();

 }

本人比较愚笨，耗时一天半才完成，不知道是不是天气热的原因，人太燥了，沉不下心来思考bug。

A*B有一点需要注意的是分块的逻辑应该怎么表示，一开始我用了两个顶点来表示一个矩阵的分块，如图：

然后halfsize还得一个一个的算，然后自己敲错的几率还会加大，并且还不一定表示正确每个分块，然后就逼疯自己了。

感觉这两天被这一堆bug都弄自闭了。。。。

幸好还是撑过来了，这算是我啃算法导论的第一个坎吧。

幸好第二天在csdn里面看到了别人怎么分块的。看到了一个变量halfsize，于是才开始改自己Matrix的构造。

虽然一开始不愿意，但是改完之后，竟然一次过了！woc！

给我了一个教训，以后能“少”一个变量尽量“少”一个变量。

巴特西

【算法导论】--分治策略Strassen算法（运用下标运算）【c++】

最新文章

热门文章