資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告