Tháp Hà Nội cổ

Có ba cọc cắm tại ba vị trí là 1, 2 và 3 như hình 5. Trên một cọc, gọi là cọc a có một chồng gồm n đĩa bằng gỗ hình tròn to nhỏ khác nhau được xuyên lỗ ở giữa tựa như những đồng xu và đặt chồng lên nhau để tạo ra một toà tháp. Người chơi phải chuyển được toà tháp sang cọc b ¹ a theo các quy tắc sau:

(1) Người chơi được sử dụng cọc còn lại để đặt tạm các tầng tháp.

(2) Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang một trong hai cọc còn lại.

(3) Không bao giờ được đặt tầng tháp lớn lên trên tầng tháp nhỏ.

Hãy tìm cách giải bài toán trên với số lần chuyển ít nhất.

Thuật toán

Chắc chắn là bạn đã biết cách giải bài toán trên. Tuy nhiên để có thể giải dễ dàng các biến thể của bài toán tháp Hà Nội chúng ta thử tìm hiểu một cách lập luận sau.

Giả sử ta quan sát một người chơi giỏi, tức là người chuyển được n tầng tháp từ cọc 1 sang cọc 2 với số lần chuyển tối thiểu. Ta dùng một chiếc máy ảnh chụp từng kết quả trung gian sau mỗi bước chuyển của người chơi này. Tổng số bức ảnh, trừ tấm ảnh ban đầu, chính là số bước chuyển các tầng. Trong số các bức ảnh chắc chắn phải có một bức như hình 10. 

Tại sao vậy? Tại vì chừng nào chưa dỡ được n - 1 tầng tháp ở phía trên của vị trí 1 để chuyển sang vị trí 3 thì anh ta không thể chuyển được tầng tháp cuối, tức là tầng lớn nhất sang vị trí 2.

Gọi Hn(n,a,b) là thủ tục chuyển n tầng tháp từ vị trí a sang vị trí b ¹ a, ta thấy:

-          Nếu n = 0: không phải làm gì;

-          Nếu n > 0 ta phải thực hiện ba bước sau:

·    Thoạt tiên chuyển n – 1 tầng tháp từ vị trí a sang vị trí c = 6 – a – b:

Hn(n-1,a,6-a-b)

·    Sau đó chuyển tầng lớn nhất từ vị trí a sang vị trí b:

a ® b

·    Cuối cùng chuyển n – 1 tầng tháp từ c sang b:

Hn(n-1,6-a-b,b)

Để ý rằng, do ta mã hoá các cọc là 1, 2 và 3 cho nên biết hai trong ba vị trí đó, là x, y chẳng hạn, ta dễ dàng tính được vị trí còn lại z theo hệ thức

z = 6–x–y

Thủ tục chuyển tháp n tầng từ cọc a sang cọc b được viết bằng Pascal như sau:

procedure Hn(n,a,b: byte);

begin

if n = 0 then exit;

Hn(n-1,a,6-a-b);

write(a, '->',b,' ');

Hn(n-1,6-a-b,b);

end;

Chọn phương thức ghi tệp hoặc màn hình

Có thể chọn một trong hai cách ghi kết quả vào tệp văn bản hoặc hiển thị lên màn hình. Bạn chỉ cần lưu ý rằng màn hình được định nghĩa như là một tệp văn bản. Chính xác hơn là như sau. Trong Turbo Pascal vùng đệm màn hình, tức là nơi chứa dữ liệu để xuất ra màn hình, được định nghĩa dưới dạng một tệp. Nếu ta mở một tệp với tên rỗng như sau:

assign(f,'');

rewrite(f);

trong đó f là biến kiểu tệp văn bản được khai báo như sau

var f: text;

thì sau đó mọi lệnh

write(f,…);

sẽ xuất dữ liệu ra màn hình.

Ngược lại, khi tên tệp trong lệnh mở tệp nói trên khác rỗng, thí dụ:

assign(f,'hanoi.out');

rewrite(f);

thì sau đó mọi lệnh

write(f,…);

sẽ ghi dữ liệu vào tệp hanoi.out trên đĩa.

Chương trình hoàn chỉnh dưới đây sẽ ghi kết quả vào tệp văn bản hanoi.out được mở trên đĩa. Trước khi ghi chính thức, bạn hãy chạy thử chương trình với lệnh mở tệp có tên rỗng để kiểm tra kết quả trên màn hình. Sau khi thấy ưng ý, bạn hãy viết tên tệp cụ thể để lưu kết quả vào đĩa.

Chương trình sử dụng biến đếm d nhằm đếm số bước chuyển.

(*   Pascal   *)

uses crt;

var d: longint;

f: text;

procedure Hn(n,a,b: byte);

begin

if n = 0 then exit;

Hn(n-1,a,6-a-b);

inc(d);

writeln(f,d,'. ',a,' -> ',b);

Hn(n-1,6-a-b,b);

end;

procedure runHn(n: byte);

begin

d :=  0;

assign(f,'hanoi.out');

rewrite(f);

writeln('-----------------');

Hn(n,1,2);

writeln(f,'Total: ',d,' step(s)');

close(f);

readln;

end;

BEGIN

runHn(3);

END.

Khi thực hiện chương trình Hanoi.pas với n = 3 ta thu được kết quả sau:

1. 1 -> 2

2. 1 -> 3

3. 2 -> 3

4. 1 -> 2

5. 3 -> 1

6. 3 -> 2

7. 1 -> 2

Total: 7 step(s)

 

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 n² 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):

S_n = (1 + 2 + ... + n²)/n = n(n² + 1)/2.

Theo các thí dụ trên ta có:

Đặc số của ma phương bậc 3: S₃ = 3(9 + 1)/2 = 15.

Đặc số của ma phương bậc 4: S₄ = 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 n cho trước ta xét tính chẵn lẻ của nó. Nếu n lẻ 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 n là 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 = (n div 2) +1.

Bước 3. Điền số: Với mỗi k biến thiên từ 1 đến n² 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 n² 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, n – j + 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 đó len chí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 s vớ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 n cho trước hay không.

Thủ tục Test sẽ 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 là 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 n là biến kiểu word thì 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.