Bài toán – Thuật toán điền số vào ma trận
Hãy lập thuật toán điền các phần tử của ma trận N´N các số 0, 1 và -1 sao cho:
a) Tổng các số của mọi hình vuông con 2×2 đều bằng 0.
b) Tổng các số của ma trận trên là lớn nhất.
Thuật toán
Để lập thuật toán điền các phần tử của ma trận N x N các số 0, 1 và -1 sao cho tổng các số của mọi hình vuông con 2×2 đều bằng 0 và tổng các số của ma trận trên là lớn nhất, chúng ta có thể sử dụng phương pháp đặt giá trị cho mỗi phần tử của ma trận bằng cách sử dụng đệ quy.
Cụ thể, để đảm bảo điều kiện a), chúng ta có thể đặt giá trị của phần tử tại hàng i, cột j của ma trận bằng 1 hoặc -1 tuỳ theo giá trị của phần tử tại hàng i-1, cột j-1. Nếu phần tử đó bằng 1 thì phần tử tại hàng i, cột j sẽ bằng -1 và ngược lại. Nếu i=1 hoặc j=1, ta có thể đặt giá trị của phần tử đó bằng 0.
Để đảm bảo điều kiện b), chúng ta có thể tính tổng của mọi phần tử của ma trận và so sánh với giá trị lớn nhất hiện tại. Nếu tổng này lớn hơn giá trị lớn nhất hiện tại thì cập nhật giá trị lớn nhất này.
Cài đặt bài toán với Python
def fillMatrix(N):
# Khởi tạo ma trận N x N với giá trị ban đầu là 0
matrix = [[0 for i in range(N)] for j in range(N)]
# Khởi tạo biến lưu giá trị lớn nhất của tổng các phần tử trong ma trận
maxSum = 0
# Hàm đệ quy fillHelper để đặt giá trị cho từng phần tử và tính tổng các phần tử
def fillHelper(i, j, currentSum):
nonlocal maxSum
# Nếu i == N thì đã đặt giá trị cho tất cả phần tử trong ma trận
if i == N:
# Nếu tổng các phần tử lớn hơn giá trị lớn nhất hiện tại thì cập nhật giá trị lớn nhất
if currentSum > maxSum:
maxSum = currentSum
return
# Thử đặt giá trị 1 tại phần tử i, j
matrix[i][j] = 1
# Kiểm tra điều kiện a) bằng cách tính tổng các phần tử trong hình vuông con 2x2
if i > 0 and j > 0:
squareSum = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i][j-1] + matrix[i][j]
# Nếu tổng khác 0 thì không đặt giá trị 1 tại phần tử i, j
if squareSum != 0:
matrix[i][j] = -1
# Đệ quy tiếp tục đặt giá trị cho phần tử tiếp theo
fillHelper(i + (j + 1) // N, (j + 1) % N, currentSum + matrix[i][j])
# Thử đặt giá trị -1 tại phần tử i, j
matrix[i][j] = -1
# Kiểm tra điều kiện a) bằng cách tính tổng các phần tử trong hình vuông con 2x2
if i > 0 and j > 0:
squareSum = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i][j-1] + matrix[i][j]
# Nếu tổng khác 0 thì không đặt giá trị -1 tại phần tử i, j
if squareSum != 0:
matrix[i][j] = 1
# Đệ quy tiếp tục đặt giá trị cho phần tử tiếp theo
fillHelper(i + (j + 1) // N, (j + 1) % N, currentSum + matrix[i][j])
# Reset giá trị của phần tử
matrix[i][j] = 0
# Gọi hàm đệ quy fillHelper với i = 0, j = 0 và currentSum = 0 để điền giá trị cho ma trận
fillHelper(0, 0, 0)
# Trả về giá trị lớn nhất của tổng các phần tử trong ma trận
return maxSum
Cài đặt bài toán bằng C++
#include <iostream>
using namespace std;
const int N = 4;
int matrix[N][N];
int maxSum = 0;
void fillHelper(int i, int j, int currentSum) {
// Nếu i == N thì đã đặt giá trị cho tất cả phần tử trong ma trận
if (i == N) {
// Nếu tổng các phần tử lớn hơn giá trị lớn nhất hiện tại thì cập nhật giá trị lớn nhất
if (currentSum > maxSum) {
maxSum = currentSum;
}
return;
}
// Thử đặt giá trị 1 tại phần tử i, j
matrix[i][j] = 1;
// Kiểm tra điều kiện a) bằng cách tính tổng các phần tử trong hình vuông con 2x2
if (i > 0 && j > 0) {
int squareSum = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i][j-1] + matrix[i][j];
// Nếu tổng khác 0 thì không đặt giá trị 1 tại phần tử i, j
if (squareSum != 0) {
matrix[i][j] = -1;
}
}
// Đệ quy tiếp tục đặt giá trị cho phần tử tiếp theo
fillHelper(i + (j + 1) / N, (j + 1) % N, currentSum + matrix[i][j]);
// Thử đặt giá trị -1 tại phần tử i, j
matrix[i][j] = -1;
// Kiểm tra điều kiện a) bằng cách tính tổng các phần tử trong hình vuông con 2x2
if (i > 0 && j > 0) {
int squareSum = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i][j-1] + matrix[i][j];
// Nếu tổng khác 0 thì không đặt giá trị -1 tại phần tử i, j
if (squareSum != 0) {
matrix[i][j] = 1;
}
}
// Đệ quy tiếp tục đặt giá trị cho phần tử tiếp theo
fillHelper(i + (j + 1) / N, (j + 1) % N, currentSum + matrix[i][j]);
// Reset giá trị của phần tử
matrix[i][j] = 0;
}
int fillMatrix() {
// Khởi tạo giá trị ban đầu cho ma trận là 0
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = 0;
}
}
fillHelper(0, 0, 0);
return maxSum;
}
int main() {
cout << fillMatrix() << endl;
return 0;
}