Đặt N^2 số vào ma trận sao cho mỗi hàng có tổng bằng nhau trong C++

Trong bài toán này, chúng ta được cho một giá trị nguyên N. Nhiệm vụ là in các số trong khoảng (1, N²) vào ma trận 2D kích thước NxN sao cho tổng các phần tử của mỗi hàng đều bằng nhau.

Ví dụ minh họa:

Đầu vào - N = 4

Kết quả -

1 6 11 16 
2 7 12 13 
3 8 9 14 
4 5 10 15

Tổng các phần tử mỗi hàng là 34

Để giải bài toán, cần đặt từng phần tử vào ma trận sao cho tổng mỗi hàng bằng nhau. Sử dụng phương pháp tham lam (greedy) và đặt hàng bởi hàng các phần tử đúng để tổng bằng nhau.

Đầu tiên, điền tất cả các phần tử vào ma trận, sau đó tạo ma trận mới lấy phần tử từ ma trận trước theo công thức:

resultMat[i][j] = prevMat[j][(i+j)%n]

Chương trình minh họa

Code dưới đây triển khai giải pháp:

#include <iostream> 
using namespace std; 

int main() { 
    int n = 4, i, j; 
    cout << "Ma trận kích thước: " << n << " mà tổng các phần tử mọi hàng bằng nhau là:\n"; 
    int prevMat[n][n], resultMat[n][n]; 
    int c = 1; 
    for (i = 0; i < n; i++) { 
        for (j = 0; j < n; j++) 
            prevMat[i][j] = c++; 
    } 
    for (i = 0; i < n; i++) { 
        for (j = 0; j < n; j++) { 
            resultMat[i][j] = prevMat[j][((i + j) % n)]; 
        } 
    } 
    for (i = 0; i < n; i++) { 
        for (j = 0; j < n; j++) { 
            cout << resultMat[i][j] << "\t"; 
        } 
        cout << endl; 
    } 
    return 0; 
}

Kết quả

Ma trận kích thước: 4 mà tổng các phần tử mọi hàng bằng nhau là: 
1 6 11 16 
2 7 12 13 
3 8 9 14 
4 5 10 15