Cho một ma trận col hàng làm đầu vào. Mục tiêu là tìm tất cả các ma trận con trong ma trận [row] [col] sao cho tổng các phần tử của ma trận con đó chia hết cho số nguyên k.
Nếu ma trận là ma trận [3] [3] và k là 4 thì ma trận con sẽ như hình dưới đây:-
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - ma trận [3] [3] ={{1,1,1}, {2,2,2}, {3,3,3}} k =4
Đầu ra - Số ma trận con có tổng 'k' chia hết là:4
Giải thích - Các ma trận con sẽ như được hiển thị ở trên.
Đầu vào - ma trận [3] [3] ={{1,1,1}, {2,2,2}, {3,3,3}} k =12
Đầu ra - Số ma trận con có tổng 'k' chia hết là:4
Giải thích - Các ma trận con sẽ như hình dưới đây:-
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ duyệt ma trận từ trái sang phải và đối với từng cặp cột trái và phải, thêm các phần tử của ma trận con vào mảng arr [] và tính riêng tổng các phần tử và mảng con của nó có tổng chia hết cho k.
Hàm check_val () nhận một mảng có các phần tử của submatrix là mảng 1D. Bây giờ hãy tính tổng tích lũy và kiểm tra phần dư với k và lưu trữ tần suất của phần dư trong mảng arr_2 [].
- Lấy ma trận [row] [col] và số nguyên k làm đầu vào.
- Hàm check_val (int arr [], int size, int k) nhận arr [] của các phần tử của ma trận con và trả về tổng số của tất cả các mảng con trong arr có tổng chia hết cho k
- Lấy các biến đếm và tạm thời là 0.
- Lấy mảng arr_2 [] để lưu trữ tần số của phần còn lại của tổng tích lũy với k.
- Tính tổng tích lũy bằng vòng lặp for từ i =0 đến i
- Một lần nữa, sử dụng mảng tần số chạy ngang vòng lặp arr_2 [] và đối với mỗi giá trị> 1, hãy thêm arr_2 [i] * (arr_2 [i] - 1)) / 2 để đếm tất cả các mảng con có thể.
- Ở cuối, hãy thêm arr_2 [0] để đếm.
- Hàm ma trận_có thể phân chia (int matrix [row] [col], int size, int k) nhận một ma trận con đầu vào và trả về tổng số của tất cả các ma trận con có tổng chia hết cho k.
- Lấy số lượng ban đầu là 0.
- Lấy một mảng tạm thời arr [size].
- Sử dụng hai vòng lặp for đặt chỉ số cột bên trái i và chỉ số cột bên phải j.
- Tính tổng các phần tử dưới dạng arr [temp] + =matrix [temp] [j].
- Đối với số lượng mảng con trong arr [], hãy thêm check_val (arr, size, k) để đếm.
- Ở cuối tất cả các vòng lặp for, kết quả là trả về số lượng.
Ví dụ
#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;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau
Đầu ra
Count of sub-matrices having sum divisible 'k' are: 7