矩阵扩展-算卷积算法介绍及C语言代码实现

目录

矩阵扩展算法——简单的算卷积

杂谈

矩阵

矩阵的幂

矩阵转置 

---

矩阵扩展算法——简单的算卷积

接着上文，矩阵进行更深入的学习就需要学习更多的处理了，矩阵被运用在很多的领域，这里简单以计算机图形处理的重要概念——卷积，为例进行说明：

卷积。用一个模板去和另一个图片对比，进行卷积运算。目的是使目标与目标之间的差距变得更大。卷积在数字图像处理中最常见的应用为锐化和边缘提取，此外，在人工智能中的图像处理也极为常见，这里的运算介绍不提供繁杂的公式（相信短时间内也看不懂）使用Zero padding，unit strides（零填充，单位滑动）的计算方式进行举例。

（图片来自外国的学术论坛datascience）

对于此类计算，有两个矩阵a和b，矩阵a是原矩阵，b是卷积核，他们的运算过程是，首先对b矩阵进行倒置，如：

 接着，再将待处理矩阵的部分与卷积核进行逐个进行相对应的运算，本例子由于按照边缘’零’处理的方式，因此边缘全部按照0进行运算，如图运算的过程为：0*1+0*2+0*3+0*2+1*1+2*2+0*1+1*2+2*1=9，这样的一个值计算完成后，对每一个值再度进行运算即可。

以卷积核为3*3为例，代码样例为： 

#include <stdio.h>#define MAXN 105int n, m;
int org[MAXN][MAXN] = {0};
int ker[3][3] = {0};
int ans[MAXN][MAXN] = {0};int main() {scanf("%d %d", &n, &m);// 输入待处理的矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &org[i][j]);}}// 以倒置的方式输入卷积核for (int i = 2; i >= 0; i--) {scanf("%d %d %d", &ker[i][2], &ker[i][1], &ker[i][0]);}// 卷积运算    for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int tmp = 0;for (int a = 0; a < 3; a++) {for (int b = 0; b < 3; b++) {tmp += (ker[a][b] * org[i - 1 + a][j - 1 + b]);}}ans[i][j] = tmp;}}// 结果输出for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {printf("%d ", ans[i][j]);}printf("\n");}return 0;
}

杂谈

从前文的代码实现可以看出，矩阵在整个计算机中使用非常广泛，而其实现方式又无不与二维数组这个概念相对应，二维数组是最简单的矩阵表示方式，其便利性可以让我们设计出相当多的矩阵相关的算法，与一维的运算不同，二维的运算无论从理解出发还是计算乃至代码设计出发，都复杂了许多，这就需要充分的数学知识做铺垫，也希望读者能够细细理解代数这一门学科的奥妙。

矩阵

 

代码示例:

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
// 对于该题也可以把数组设为arr[7][7],count[7],设为全局变量更好，方便函数传参
int SumMax(int** arr, int n)// 计算矩阵中列的最大值
{int max = -1000;for (int i = 0; i < n; i++){int sum = 0;for (int j = 0; j < n; j++){sum += arr[j][i];}max = sum > max ? sum : max;}return max;
}
void RightRotate(int** arr, int n, int i)// 实现右移一次
{int temp = arr[i][n - 1];for (int k = n - 2; k >= 0; k--){arr[i][k + 1] = arr[i][k];}arr[i][0] = temp;
}
int main()
{int n;while (scanf("%d", &n) != EOF && n != -1)// -1结束{// 定义一个二维数组，为n*n的矩阵int** arr = (int**)malloc(n * sizeof(int*));for (int i = 0; i < n; i++){arr[i] = (int*)malloc(n * sizeof(int));}// 定义一个一维数组，用来储存每一行需移动的次数int* count = (int*)malloc(n * sizeof(int));    // 初始化数据for (int i = 0; i < n; i++){count[i] = 0;for (int j = 0; j < n; j++){scanf("%d", &arr[i][j]);}}int min = 100000;if (n == 1){min = arr[0][0];}else{bool flag = true;while (flag){flag = false;// 用于终止循环，当第二行右移完之后for (int i = n - 1; i >= 1; i--)// 实现第i行的右移，一直到第二行即可{RightRotate(arr, n, i);if (count[i] < n)// 每一行最多移动n次{count[i]++;min = SumMax(arr, n) < min ? SumMax(arr, n) : min;for (int j = i + 1; j < n; j++)count[j] = 0;// 将i行后面移动的次数重置为0，再重新进行每行的右移flag = true;break;}}}}// 或者像下面这样一次循环，注意一下不同之处while (flag){flag = false;// 用于终止循环，当第一行右移完之后for (int i = n - 1; i >= 0; i--)// 实现第i行的右移，一直到第一行即可{RightRotate(arr, n, i);if (count[i] < n)// 每一行最多移动n次{count[i]++;min = SumMax(arr, n) < min ? SumMax(arr, n) : min;for (int j = i + 1; j < n; j++)count[j] = 0;// 将i行后面移动的次数重置为0，再重新进行每行的右移flag = true;break;}}}printf("%d\n", min);// 动态申请内存后释放，养成一个好习惯free(arr);free(count);arr = NULL;count = NULL;}return 0;
}

矩阵的幂

 代码示例:

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
class M
{public:LL data[101][101];M(){memset(data,0,sizeof(data));}
};
M *Mul(M *m1,M *m2)
{M *ans=new M();for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)ans->data[i][j]+=m1->data[i][k]*m2->data[k][j];return ans;
}
M *mPow(M *m,int p)
{M *E=new M();for(int i=0;i<2;i++)for(int j=0;j<2;j++)if(i==j)E->data[i][j]=1;while(p!=0){if((p&1))E=Mul(E,m);m=Mul(m,m);p>>=1;}return E;
}
int main()
{int n;M *res=new M(),*a=new M();a->data[0][0]=0;a->data[0][1]=1;a->data[1][0]=2;a->data[1][1]=3;while(cin>>n){res=mPow(a,n);for(int i=0;i<2;i++)for(int j=0;j<2;j++)cout<<res->data[i][j]<<" ";cout<<endl;memset(res,0,sizeof(res));}return 0;
}

矩阵转置 

代码示例:

#include<stdio.h>int main(){int a[100][100];int n,i,j;scanf("%d",&n);for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&a[i][j]);}}for(i=0;i<n;i++){for(j=0;j<n;j++){printf("%d ",a[j][i]);}printf("\n");}return 0;}