• Thứ Ba, 16/12/2003 14:18 (GMT+7)

    Thuật toán xây dựng ma trận kỳ ảo

    Định nghĩa

        Ma trận vuông kích thước NxN được gọi là kỳ ảo nếu nó được điền đầy các số 1, 2, 3 ... N2 sao cho tổng số của các số hàng, cột và đường chéo đều bằng nhau.

        Chúng ta có thể dùng thuật toán thử-sai (thuật toán quay lui) để dò hết các trườ̀ng hợp. Nhưng cách này sẽ làm bùng nổ tổ hợp: với n = 2 ta có 4! cách chọn, n=k ta có (k2)! cách chọn, ngoài ra thời lượng tính toán kiểm tra trên các hàng, cột và đường chéo cũng rất lớn.

        Dưới đây là thuật toán cho phép bạn giải nhanh bài toán này.

    Thuật toán

        a) Trường hợp 1: N lẻ

    N=2m+1.

        Ma trận A được đánh chỉ số [0..N-1,0..N-1]. Thuật toán điền các số 1,2,3,..,N2 vào ma trận A như sau:

        • Số 1 điền vào ô A[m,2m]

        • Giả sử k đã được điền vào ô A[x,y] thì k+1 sẽ được điền vào A[x+1 mod N, y+1 mod N] nếu ô này trống, ngược lại điền vào A[x,y-1].

        b) Trường hợp 2: N chẵn

        N=2m (m>0)

        Thuật toán:

        Các số 1,2,..,N2 lần lượt điền vào ma trận A theo thứ tự từ trái qua phải và trên xuống dưới.

        Chia ma trận vuông A thành 4 ma trận vuông con kích thước mxm.

        Chọn ra hình vuông đầu tiên ở góc trái trên. Trong ma trận này đánh dấu một số kí hiệu *,-,| như sau:

        • Đánh dấu mx[m/2] dấu “*” sao cho trên mỗi hàng và mỗi cột có đúng [m/2] (lấy số nguyên) dấu “*”.

        • Nếu m lẻ, đánh dấu bổ sung thêm đúng m dấu “–” và m dấu “|” sao cho thoả mãn các điều kiện sau:

            1. Các dấu này không trùng với “*” và trên mỗi hàng, mỗi cột có đúng 1 dấu “–” và 1 dấu “|”.

            2. Các dấu này không nằm trên đường chéo chính.

        • Tiếp theo, các dấu *,-,| được phát triển ra toàn bộ ma trận NxN theo qui tắc sau:

            1. Dấu “*” lấy đối xứng qua trục ngang, trục dọc và qua tâm.

            2. Dấu “-” lấy đối xứng qua trục ngang.

            3. Dấu “|” lấy đối xứng qua trục dọc.

        • Bây giờ ta thực hiện phép biến đổi ma trận như sau:

            1. Đổi chỗ các ô có dấu “*” đối xứng qua tâm.

            2. Đổi chỗ các ô có dấu “-” đối xứng qua trục ngang.

            3. Đổi chỗ các ô có dấu “|” đối xứng qua trục dọc.

            4. Các vị trí còn lọai giữ nguyên.ÿ

    Trịnh Quang Đào –PTNK
    hackerdarkrose@yahoo.com

    ID: A0305_97