简单卷积

[编程题]简单卷积

热度指数：173 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小森最近在工作上遇到了一些麻烦，他需要在许多矩阵上计算卷积的结果，希望你能够帮助他写一个程序简化计算。

小森已经将他要计算的卷积处理成了如下的简化形式，以便即使不了解卷积的人也可以进行计算：

给出一个n*m的矩阵A和一个3*3的矩阵B，A和B的计算结果是一个(n-2)*(m-2)的矩阵C，满足：

$C_{x, y} = \sum_{i=0..2}\sum_{j=0..2}A_{x+i, y+j}*B_{i,j}$

请按照以上公式，根据给出的矩阵A和B计算出矩阵C。

输入描述:

输入的第一行为两个正整数n和m，其中3 <= n, m <= 500。
接下来的n行，每行包含m个用空格分隔的整数，其中第x行第y列的整数为，且。
接下来的3行，每行包含3个用空格分隔的整数，其中第x行第y列的整数为，且。

输出描述:

输出包含n-2行，每行包含m-2个用空格分隔的整数，其中第x行第y列的整数为。

示例1

输入

4 4
1 2 3 4
5 4 3 2
-1 -2 -3 -4
-5 -4 -3 -2
1 0 -1
0 -1 1
-1 0 1

输出

-5 -5
3 3

说明

以输出样例中左上角的-5为例：

(1 * 1) + (2 * 0) + (3 * (-1)) + (5 * 0) + (4 * (-1)) + (3 * 1) + ((-1) * (-1)) + ((-2) * 0) + ((-3) * 1) = 1 + 0 + (-3) + 0 + (-4) + 3 + 1 + 0 + (-3) = -5

算法知识视频讲解

C/C++

ت20181024193444

#include <stdio.h>
#include <stdlib.h>

#define N 500

int n, m;
int feat[N][N];
int kernel[3][3];

int main() {
    scanf("%d %d",&n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &feat[i][j]);
        }
    }
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            scanf("%d", &kernel[i][j]);
        }
    }
    int res[N][N];

    int sum;
    
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-2; j++){
            // int sum = 0; 运行时间 83ms 占用内存 4848KB
            // 循环外int sum;  这里sum=0; 运行时间 82ms 占用内存 4904KB， 避免了重复定义的时间，但是每次都需要开辟一块内存，且在并行计算时，如果多个线程同时访问同一个变量，可能会导致数据竞争的问题，需要使用同步机制来保证数据的正确性
            int sum = 0;
            for(int k=0; k<3; k++){
                for(int l=0; l<3; l++){
                    sum += feat[i+k][j+l] * kernel[k][l];
                }
            }
            res[i][j] = sum;
        }
    }
    // 在循环中输出会导致程序频繁地调用输出函数，增加了 I/O 操作的次数，从而影响程序的效率。因此，在循环外面先计算好结果，再一次性输出，可以减少 I/O 操作的次数，提高程序的效率。
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-2; j++){
            printf("%d ",res[i][j]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2023-04-06 17:36:51 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[][] a = new int[n][m];
        int[][] b = new int[3][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                b[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n-2; i++) {
            for (int j = 0; j < m-2; j++) {
                int sum = 0;
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        sum += a[i + k][j + l] * b[k][l];
                    }
                }
                if (j == m-3) System.out.println(sum);
                else System.out.print(sum + " ");
            }
        }
    }
}

发表于 2022-06-27 13:19:03 回复(0)

是梦扰了她

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int matrix[n][m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>matrix[i][j];
        }
    }
    int kernl[3][3];
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>kernl[i][j];
        }
    }
    for(int i=0;i<n-2;i++)
    {
        for(int j=0;j<m-2;j++)
        {
            int res=0;
            for(int k=0;k<=2;k++)
            {
                for(int l=0;l<=2;l++)
                {
                    res+=matrix[i+k][j+l]*kernl[k][l];
                }
            }
        cout<<res<<" ";
        }
        cout<<endl;
    }
    return 0;
 }

发表于 2020-03-18 11:00:39 回复(0)