Ma phương



Ma phương
Ma phương là những bảng số hình vuông trong đó mỗi dòng, mỗi cột và mỗi đường chéo đều cùng thoả một số tính chất nào đó. Các nhà thiên văn cổ Trung Hoa cho rằng mỗi tinh tú trên bầu trời đều ứng với một ma phương. Nhiều nhà toán học cổ Ai Cập, Ấn Độ và sau này các nhà toán học phương Tây đã phát hiện những tính chất khá lí thú của các loại ma phương. Trong bài này ta giới hạn khái niệm ma phương theo nghĩa sau.
Ma phương bậc n là một bảng số hình vuông, mỗi cạnh n ô chứa các số từ 1 đến n2 sao cho tổng các số trên mỗi dòng, trên mỗi cột và trên mỗi đường chéo đều bằng nhau. Tổng này được gọi là đặc số của ma phương.
4
9
2



16
2
3
13
3
5
7



5
11
10
8
8
1
6



9
7
6
12






4
14
15
1

(a)




           (b)
   (a) – ma phương bậc 3, đặc số S3 = 15
   (b) – ma phương bậc 4, đặc số S4 = 34

Yêu cầu: Với mỗi trị N = 1..20 xây dựng ma phương bậc n.
Bài giải
Ta dễ dàng tính được đặc số của ma phương bậc n qua nhận xét: tổng của một cột (dòng) chính là tổng của toàn bộ các số nằm trong bảng chia cho số cột (số dòng):
Sn = (1 + 2 + ... + n2)/n = n(n2 + 1)/2.
Theo các thí dụ trên ta có:
Đặc số của ma phương bậc 3: S3 = 3(9 + 1)/2 = 15.
Đặc số của ma phương bậc 4: S4 = 4(16 + 1)/2 = 34.
Như vậy, trong ma phương bậc 3, tổng của các số nằm trên cùng hàng, cùng cột hoặc cùng đường chéo đều là 15. Trong ma phương bậc 4, tổng này là 34.
Tính chất trên không thay đổi nếu ta điền lần lượt các số hạng của một cấp số cộng vào ma phương.
Ngoài bậc n = 2, với mọi số tự nhiên n ³ 1 đều tồn tại ma phương với nhiều cách bố trí khác nhau. Chúng ta sẽ tìm hiểu hai thuật toán dễ cài đặt.
Với mỗi ncho trước ta xét tính chẵn lẻ của nó. Nếu nlẻ ta gọi thủ tục MPL (ma phương bậc lẻ), ngược lại ta gọi thủ tục MPC (ma phương bậc chẵn).

(*-------------------------------
             Ma phuong
--------------------------------*)
procedure MP(bac: word);
begin
n :=  bac;
if n = 2 then exit;
if Odd(n) then MPL else MPC;
Test;
end;
Trong đó n là biến tổng thể chứa bậc của ma phương cần xây dựng.
Hàm Odd(n) cho giá trị đúng (true) khi nlà một số lẻ, ngược lại hàm nhận giá trị sai (false).
Thủ tục MPL(n): Ma phương bậc lẻ





k





k + 1





Điền ô theo hướng Đông - Nam cho ma phương bậc lẻ.
Ta dùng một mảng hai chiều M để chứa ma phương cần xây dựng theo các bước sau đây. Để cho tiện ta đặt tên cho ma phương cần xây dựng là hình vuông ABCD.
Bước 1. Khởi trị: Điền các số 0 vào bảng M[1..n, 1..n].
Bước 2. Xác định ô xuất phát: Đó là ô giữa của dòng cuối, tức là ô
M[i, j] với i = n, j = (ndiv 2) +1.
Bước 3. Điền số:Với mỗi k biến thiên từ 1 đến n2 ta thực hiện các thao tác sau:
3.1. Điền ô (i, j): M[i, j]:= k;
3.2. Xác định vị trí ii, jj mới để điền số tiếp theo (k + 1).
Vị trí ii, jj mới được xác định theo nguyên tắc Đông-Nam với ý nghĩa là sau khi đã điền giá trị k, giá trị k + 1 sẽ được viết vào ô nằm ở vị trí Đông-Nam so với ô chứa k. Như vậy, nếu M[i, j] = k thì vị trí ô chứa k + 1 sẽ là ii:= i + 1, jj:= j + 1. Có thể sẽ xảy ra các tình huống sau đây:
3.2.1. (i = n) và (j = n): Số k đã viết ở góc Đông-Nam (góc C) của ma phương. Khi đó, nếu đi tiếp theo hướng Đông-Nam thì sẽ rơi vào ô nằm ngoài bảng. Ta gọi tình huống này là tình huống Đông-Nam và xử lí như sau: viết số k + 1 vào ô sát trên ô chứa k, tức là chọn
ii :=  n-1; jj :=  n;
Ta gọi phương thức xử lí này là đền trên: Đền vào ô trên ô vừa viết (xem các số 6 ® 7 trong ma phương bậc 3).
3.2.2. (i = n) và (j < n): Số k đã viết nằm ở cạnh DC và khác ô C. Ta gọi tình huống này là tình huống Nam và xử lí theo phương thức "nổi bọt" như sau: Viết k + 1 vào vị trí Đông-Nam tức là ô
i+1 = n+1,j+1.
Dĩ nhiên ô này nằm ở ngoài bảng, dưới cạnh DC. Bây giờ ta cho nó nổi lên tới cạnh AB. Như vậy ta sẽ chọn
ii :=  (i mod n) + 1;
jj :=  (j mod n) + 1;
(xem các số 1 ® 2 và 8 ® 9 trong ma phương bậc 3).
3.2.3. (i < n) và (j = n): Số k đã viết nằm ở cạnh BC và khác ô C. Ta gọi tình huống này là tình huống Đông và xử lí theo theo phương thức đẩy trái như sau: Viết k + 1 vào vị trí Đông-Nam tức là ô
i+1, j+1 = n+1
Ô này nằm ngoài bảng, bên phải cạnh BC. Bây giờ ta đẩy trái nó sang tới cạnh AD. Giống như trên, ta chọn:
ii :=  (i mod n) + 1;
jj :=  (j mod n) + 1;
(xem các số 2 ® 3 và 7 ® 8 trong ma phương bậc 3).
3.2.4. Đụng độ: Cuối cùng có thể ô (ii, jj) rơi vào trong bảng nhưng ở đó đã có số được viết trước. Ta gọi tình huống này là tình huống đụng độ và xử lí theo phương thức đền trên như tình huống Đông-Nam (xem bước đi 3 và 4 trong ma phương bậc 3). Trường hợp này ta chọn:
ii := i- 1; jj := j;
Sử dụng phép toán đồng dư ta có thể giải quyết tự động các tình huống Nam và Đông theo công thức
ii := (i mod n)+1 ; jj := (j mod n)+1;

A


B




A


B













k+1





k



k



k+1



D                                C
Đông-Nam



D                             C
Đông


A


B




A


B



k+1



k+1









k




k





  *


D                              C
Nam



D                               C
Đụng độ
Các tình huống khi điền ma phương bậc lẻ
Dưới đây là thủ tục ma phương bậc lẻ.
(*---------------------------------
          Ma phuong bac le
----------------------------------*)
procedure MPL;
var k,i,ii,j,jj: word;
begin
{Buoc 1: Khoi tri}
fillchar(M, sizeof(M),0);
{Buoc 2: Xac dinh o xuat phat}
i  :=  n;
j  :=  n div 2 + 1;
{Buoc 3: Dien so}
for k  :=  1 to n*n do
begin
{3.1. Dien o (i,j)}
M[i,j]  :=  k;
{3.2 Xac dinh vi tri ii,jj
 cho so tiep theo (k+1)}
if (i=n) and (j=n) then
{3.2.1.Tinh huong Dong-Nam:Den tren}
begin
ii  :=  n-1; jj  :=  n;
end
else
begin {3.2.2 va 3.2.3.}
ii  :=  i mod n + 1;
jj  :=  j mod n + 1;
end;
if M[ii,jj]<>0 {o da dien} then
begin
{3.2.4. Dung do: Den tren}
ii  :=  i-1; jj  :=  j;
end;
   i  :=  ii; j  :=  jj;
end;
end;
Thủ tục MPC(n): Ma phương bậc chẵn
Bước 1. Khởi trị: Điền các số từ 1 đến n2 vào bảng theo trật tự từ trên xuống dưới, từ trái sang phải. Thí dụ, với n = 4, M được khởi trị như sau:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Khởi trị cho ma phương bậc 4
Bước 2. Tạo xâu mẫu: Ta tạo xâu mẫu s phục vụ cho việc đổi chỗ các số trong M. Xâu mẫu s có chiều dài k = n div 2 và bao gồm các kí tự 'T', 'D', 'N' và 'B' với các ý nghĩa sau:
-          'T' - thực hiện phép đối xứng tâm: Đổi chỗ các cặp phần tử:
M[i,j] « M[n-i+1,n-j+1]
M[i,n-j+1] « M[n-i+1,j]
-          'D' - thực hiện phép đối xứng theo trục dọc:Đổi chỗ cặp phần tử:
M[i,j] « M[i,n-j+1]
-          'N' - thực hiện phép đối xứng theo trục ngang:Đổi chỗ cặp phần tử:
M[i,j] « M[n-i+1,j]
-          'B' - không làm gì.
Xâu mẫu s được tạo như sau:
2.1. Khởi trị xâu rỗng   s[0] :=  #0;
2.2. Tính  k  :=  n div 2;
2.3. Nạp (k div 2) kí tự 'T' cho s.
for i  := 1 to (k div 2) do
s  :=  s+TT;
2.4. Nếu k lẻ nạp thêm hai kí tự 'DN' cho s:
if Odd(k) then s :=  s+DD+NN;
2.5. Điền thêm các kí tự 'B' cho đủ k kí tự trong s.
for i  :=  length(s)+1 to k do s  :=  s+BB;
trong đó các hằng TT, DD, NN và BB được khai báo như sau
                           const
TT = 'T'; {doi xung Tam}
DD = 'D'; {doi xung Doc}
NN = 'N'; {doi xung Ngang}
BB = 'B'; {Bo qua}
Các thí dụ tạo xâu mẫu s:
- Với n = 4 ta có k = n div 2 = 2 (chẵn), k div 2 = 1, do đó  s='TB'
- Với n = 6 ta có k = n div 2 = 3 (lẻ), k div 2 = 1, do đó s='TDN'
- Với n = 18 ta có k = n div 2 = 9 (lẻ), k div 2 = 4, do đó s='TTTTDNBBB'
Thủ tục khởi trị cho ma phương bậc chẵn sẽ như sau:
(*-----------------------------------------
     Khoi tri cho ma phuong bac chan
------------------------------------------*)
procedure InitMPC;
var i,j: word;
begin
{Buoc 1. Khoi tri}
for i := 1 to n do
  for j := 1 to n do
     M[i,j] :=  Num(i,j);
{Buoc 2: Tao xau mau}
s[0] := #0; {Khoi tri xau rong}
k :=  n div 2;
{Nap (k div 2) ki tu T}
for i := 1 to (k div 2) do s  :=  s+TT;
{Nap them 2 ki tu D va N neu k le}
if Odd(k) then s  :=  s+DD+NN;
{Bu cac ki tu B cho du k ki tu}
for i :=  length(s)+1 to k do s  :=  s+BB;
end;
Chú ý rằng để khởi trị giá trị rỗng cho xâu s ta có hai cách:
Cách 1. Viết hai dấu nháy đơn sát nhau:
s :=  '';
Cách 2. Gán cho phần tử s[0] là nơi chứa chiều dài xâu s giá trị #0 ứng với kí tự có mã ASCII là 0:
s[0] :=  #0;
Cách thứ nhất khiến bạn đọc dễ nhầm với dấu cách, nên dùng cách thứ hai.
Bước 3. Điền số theo xâu mẫu
for i := 1 to k do
begin
XuLyDong(i);
QuayXauMau;
end;
Để xử lí dòng i ta lần lượt xét các kí tự s[j] trong xâu mẫu và xử lí từng phần tử M[i, j],  j = 1..length(s).
-          Nếu s[j] = 'T' ta gọi thủ tục Tam(i,j,n) để thực hiện đối xứng tâm cho các ô (i, j) và (i, nj + 1).
-          Nếu s[j] = 'D' ta gọi thủ tục Doc(i,j,n) để thực hiện đối xứng theo trục dọc cho ô (i, j).
-          Nếu s[j] = 'N' ta gọi thủ tục Ngang(i, j, n) để thực hiện đối xứng theo trục ngang cho ô (i, j).
-          Nếu s[j] = 'B' ta bỏ qua.
procedure XuLyDong(i: word);
var j: word;
begin
for j  :=  1 to k do
case s[j] of
TT: Tam(i,j);
DD: Doc(i,j);
NN: Ngang(i,j);
end;
end;
Để ý rằng tại bước khởi trị số nằm trên ô (i, j) sẽ có giá trị (i – 1)*n + j. Ta sẽ sử dụng hàm Num(i,j,n) để tính giá trị này.
(*------------------------------------
     So nam tren hang i, cot j.
-------------------------------------*)
function Num(i,j: word):word;
begin
Num := (i-1)*n+j;
end;
Các thủ tục lấy đối xứng qua tâm, dọc và ngang là khá đơn giản.
(*-------------------------------------
     Lay doi xung qua tam (2 cap so)
--------------------------------------*)
procedure Tam(i,j: word);
begin
M[i,j] :=  Num(n-i+1,n-j+1);
M[n-i+1,n-j+1] :=  Num(i,j);
M[n-i+1,j] :=  Num(i,n-j+1);
M[i,n-j+1] :=  Num(n-i+1,j);
end;
(*--------------------------------------
               Doi xung doc
--------------------------------------*)
procedure Doc(i,j: word);
begin
M[i,j] :=  Num(i,n-j+1);
M[i,n-j+1] :=  Num(i,j);
end;
(*-----------------------
      Doi xung ngang
------------------------*)
procedure Ngang(i,j: word);
begin
M[i,j] :=  Num(n-i+1,j);
M[n-i+1,j] :=  Num(i,j);
end;
Mỗi lần xử lí xong một dòng ta cần quay xâu mẫu s thêm một vị trí theo chiều kim đồng hồ, kí tự cuối xâu được đưa về đầu xâu, các kí tự khác được dịch qua phải một vị trí.
Thí dụ về quay xâu mẫu s: Với n = 18 ta có:
s = 'TTTTDNBBB'
sau lần quay thứ nhất ta thu được
s = 'BTTTTDNBB'
sau lần quay thứ hai ta thu được
s = 'BBTTTTDNB'
Để quay xâu s[1..k] ta lấy kí tự cuối cùng s[k] ghép lên khúc đầu s[1..k-1], tức là đặt
s  :=  s[k]+s[1..k-1]
Để lấy đoạn s[1..k-1] ta gọi hàm copy:
copy(s,1,len-1)
trong đó lenchính là chiều dài xâu s.
Lệnh
copy(s,i,m)
sẽ tạo ra một xâu con của xâu svới m kí tự kể từ kí tự thứ i:
copy(s,i,m) = s[i..(i+m-1)]
(*--------------------------
   Quay xau mau s 1 vi tri
---------------------------*)
procedure QuayXauMau;
var len: byte;
begin
len  :=  length(s);
s  :=  s[len] + copy(s,1,len-1);
end;
Sau đây là thủ tục tạo ma phương bậc chẵn.
(*---------------------------
      Ma phuong bac chan
----------------------------*)
procedure MPC;
var i,j: word;
begin
if n=2 then exit;
InitMPC;
{Dien so theo xau mau}
for i := 1 to k do
begin
XuLyDong(i);
QuayXauMau;
end;
end;
Sau khi đã tạo xong ma phương ta cần kiểm tra lại xem ma trận M có thoả các tính chất cơ bản của ma phương bậc ncho trước hay không.
Thủ tục Testsẽ hiển thị ma phương trên màn hình và đồng thời kiểm tra xem các tổng các phần tử trên mỗi dòng, tổng các phần tử trên mỗi cột, tổng các phần tử trên đường chéo chính c1 và tổng các phần tử trên đường chéo phụ c2 có bằng đặc số của ma phương hay không.
Ta sử dụng hai mảng dong[1..n], cot[1..n] và hai biến đơn c1, c2 để tính các tổng này bằng một lần duyệt mảng hai chiều M.
Để tính đặc số ta lưu ý kiểu của biến chứa đặc số d longint trong khi đó các trị của mảng M là word. Trong Turbo Pascal có nguyên tắc sau:
Nguyên tắc định kiểu cho biểu thức
Kiểu của trị của biểu thức số sẽ là kiểu rộng nhất trong số các kiểu của các đại lượng (hằng và biến) có mặt trong biểu thức.
Theo quy định này, với khai báo nlà biến kiểu wordthì kiểu của trị của biểu thức tính đặc số của ma phương bậc n
((n*n+1)*n) div 2
cũng sẽ là word.
Điều này có thể dẫn đến tràn số.
Ta khắc phục bằng thao tác hai bước như sau:
d  :=  0;
d  :=  d+((n*n+1)*n) div 2;
Khi đó, do biểu thức vế phải của phép gán có chứa biến d thuộc kiểu longint nên kết quả sẽ có kiểu longint.
Bạn cũng có thể dùng toán tử chuyển sang kiểu longint một trong các đại lượng trong biểu thức vế phải, chẳng hạn:
d :=  ((n*n+longint(1))*n) div 2
(*--------------------------------
    Hien thi va kiem tra ket qua
----------------------------------*)
procedure Test;
var i,j: word;
dong, cot: ML1;
d,c1,c2: longint;
begin {Tinh Dac so}
d := 0;
d := d+((n*n+1)*n) div 2;
writeln(NL,' Ma phuong bac ',n,', Dac so: ',d);
fillchar(dong,sizeof(dong),0);
fillchar(cot,sizeof(cot),0);
c1 :=  0;
c2 :=  0;
for i := 1 to n do
begin
  writeln;
  c1  :=  c1 + M[i,i];
  c2  :=  c2 + M[i,n-i+1];
  for j :=  1 to n do
begin
  write(M[i,j]:4);
  dong[i] :=  dong[i] + M[i,j];
  cot[j] :=  cot[j] + M[i,j];
end;
end;
writeln;
for i :=  1 to n do
begin
if dong[i] <> d then
  writeln(' Sai dong ',i,BL,dong[i]);
if cot[i] <> d then
  writeln(' Sai cot ',i,BL, cot[i]);
end;
if c1 <> d then writeln(' Sai cheo chinh ',c1);
if c2 <> d then writeln(' Sai cheo phu ',c2);
end;
(* Pascal  *)
Chương trình MAPHUONG.PAS dưới đây tạo bộ dữ liệu kiểm thử với các ma phương từ bậc 1 đến bậc 20.
(* MAPHUONG.PAS *)
uses crt;
const
MN = 50;
TT = 'T'; {doi xung Tam}
DD = 'D'; {doi xung Doc}
NN = 'N'; {doi xung Ngang}
BB = 'B'; {Bo qua}
BL = #32; {dau cach}
NL = #13#10; {qua dong moi}
type
MW1 = array[0..MN] of word;
MW2 = array[0..MN] of MW1;
ML1 = array[0..MN] of longint;
var M: MW2;
n,k: word;
s: string;
(*--------------------------------
  Hien thi va kiem tra ket qua
----------------------------------*)
procedure Test; tự viết
(*------------------------------------
      So nam tren hang i, cot j
-------------------------------------*)
function Num(i,j: word):word;
begin
Num  :=  (i-1)*n+j;
end;
(*-------------------------------------
     Lay doi xung qua tam (2 so)
--------------------------------------*)
procedure Tam(i,j: word); tự viết
(*--------------------------------------
              Doi xung doc
--------------------------------------*)
procedure Doc(i,j: word); tự viết
begin
M[i,j] :=  Num(i,n-j+1);
M[i,n-j+1] :=  Num(i,j);
end;
(*--------------------------------------
              Doi xung ngang
---------------------------------------*)
procedure Ngang(i,j: word); tự viết
(*--------------------------
   Quay xau mau s 1 vi tri
---------------------------*)
procedure QuayXauMau; tự viết
(*-----------------------------------------
      Khoi tri cho ma phuong bac chan
------------------------------------------*)
procedure InitMPC; tự viết
procedure XuLyDong(i: word); tự viết
(*---------------------------
     Ma phuong bac chan
----------------------------*)
procedure MPC; tự viết
(*---------------------------------
         Ma phuong bac le
----------------------------------*)
procedure MPL; tự viết
(*-------------------------------
            Ma phuong
--------------------------------*)
procedure MP(bac: word); tự viết
(*--------------------------------
  Test cac ma phuong bac 1..20
----------------------------------*)
procedure Run;
var i: word;
begin
clrscr;
for i := 1 to 20 do MP(i);
end;
BEGIN
Run;
END.

Không có nhận xét nào:

Đăng nhận xét