数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中计算和能被'k'整除的子矩阵数量
给定一个行x列的矩阵作为输入。目标是在矩阵[行][列]中找到所有子矩阵，使得该子矩阵元素的总和能被整数k整除。
如果矩阵是mat[3][3]且k是4，则子矩阵将如下所示：
让我们通过例子来理解。
例如
输入 - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} } k=4
输出 - 和能被'k'整除的子矩阵数量为：4
解释 - 子矩阵将如上所示。
输入 - matrix[3][3] = { {1,1,1}, {2,2,2 }, {3,3,3} } k=12
输出 - 和能被'k'整除的子矩阵数量为：4
解释 - 子矩阵将如下所示：
下面程序中使用的方法如下
在这种方法中，我们将从左到右遍历矩阵，对于每一对左列和右列，将子矩阵的元素添加到数组arr[]中，并分别计算其元素的总和以及和能被k整除的子数组。
函数check_val()接受一个包含子矩阵元素的一维数组arr[]。现在计算累积和，并检查其与k的余数，并将余数的频率存储在数组arr_2[]中。
- 将矩阵[行][列]和整数k作为输入。
- 函数check_val(int arr[], int size, int k)接受子矩阵元素的数组arr[]，并返回arr中所有和能被k整除的子数组的数量。
- 将变量count和temp设置为0。
- 使用数组arr_2[]存储累积和与k的余数的频率。
- 使用for循环从i=0到i<size计算累积和。将每个arr[i]添加到temp中，并使用arr_2[((temp % k) + k) % k]++递增余数的频率（对于负数和，取两次模）。
- 再次使用for循环遍历频率数组arr_2[]，对于每个值>1，将arr_2[i] * (arr_2[i] - 1)) / 2添加到count中，作为所有可能的子数组的数量。
- 最后，将arr_2[0]添加到count中。
- 函数matrix_divisible(int matrix[row][col], int size, int k)接受一个输入子矩阵，并返回所有和能被k整除的子矩阵的数量。
- 将初始计数设置为0。
- 使用一个临时数组arr[size]。
- 使用两个for循环设置左列索引i和右列索引j。
- 将元素的总和计算为arr[temp]+= matrix[temp][j]。
- 对于arr[]中的子数组数量，将check_val(arr, size, k)添加到count中。
- 在所有for循环结束时，返回count作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
#define row 10
#define col 10
int check_val(int arr[], int size, int k) {
int count = 0;
int temp = 0;
int arr_2[k];
memset(arr_2, 0, sizeof(arr_2));
for (int i = 0; i < size; i++) {
temp = temp + arr[i];
arr_2[((temp % k) + k) % k]++;
}
for (int i = 0; i < k; i++) {
if (arr_2[i] > 1) {
count += (arr_2[i] * (arr_2[i] - 1)) / 2;
}
}
count = count + arr_2[0];
return count;
}
int matrix_divisible(int matrix[row][col], int size, int k) {
int count = 0;
int arr[size];
for (int i = 0; i < size; i++) {
memset(arr, 0, sizeof(arr));
for (int j = i; j < size; j++) {
for (int temp = 0; temp < size; ++temp) {
arr[temp] += matrix[temp][j];
}
count = count + check_val(arr, size, k);
}
}
return count;
}
int main() {
int matrix[row][col] = {{2,4,-1},{6,1,-9},{2,2, 1}};
int size = 3, k = 4;
cout << "Count of sub-matrices having sum divisible ‘k’ are: " << matrix_divisible(matrix, size, k);
return 0;
}如果我们运行上面的代码，它将生成以下输出
输出
Count of sub-matrices having sum divisible 'k' are: 7
更新于: 2021年1月29日
173 次查看
广告