Tháp Hà Nội thẳng

Tháp Hà Nội thẳng

               Nội dung giống như bài toán tháp Hà Nội cổ chỉ sửa lại quy tắc (2) như sau: (2) Mỗi lần chỉ được chuyển 1 tầng tháp từ một cọc sang cọc kề nó, không được vòng từ 3 sang 1 hay 1 sang 3.

               Điều kiện này quy định bốn phép chuyển 1 tầng tháp như sau:

1® 2,2 ® 1, 2 ® 3, 3 ® 2

               hoặc, theo cách biểu diễn khác:

1 <-> 2 <-> 3

               tức là chỉ được chuyển qua lại giữa hai cọc kề nhau. Giả thiết là các cọc được sắp thành hàng như sau:

1 = 2  = 3

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

Bài giải

Giống như đã phân tích trong các bài toán Hà Nội trước, ta có:

-          Hình trạng xuất phát: (a:[1..n], b:[ ], c:[ ])

-          …

-          Hình trạng kết thúc: (a:[ ], b:[1..n], c:[ ])

-          Hình trạng buộc phải có: (a:[n], b:[ ], c:[1..n – 1])

Ta phân biệt hai trường hợp:

-          Hai cọc a và b đứng kề nhau trên đường thẳng.

-          Hai cọc a và b cách nhau qua c.

Trường hợp thứ nhất Nếu vị trí các cọc được bố trí như sau

1                             2                            3

thì giữa a và b có bốn tình huống, cụ thể là:

Tình huống	1	2	3
1	a	b
2	b	a
3		a	b
4		b	a
Tháp Hà Nội thẳng Đặc tả a và b kề nhau abs(a - b) = 1

Trường hợp này được đặc tả là

abs(a-b) = 1

Hình trạng	Ý nghĩa	Lệnh
(a: [1..n], b: [ ], c: [ ])	Hình trạng ban đầu với vị trí b kề vị trí a trên đường thẳng. abs(a - b) = 1 Để chuyển n tầng từ a sang b theo đường thẳng ta phải...
...
(a: [n], b: [ ], c: [1..n - 1])	Chuyển (tạm) n - 1 tầng từ a qua c = 6 - a - b.	Hnt(n - 1, a, 6 - a - b);
(a: [ ], b: [n], c: [1..n - 1])	sau đó chuyển tầng còn lại của a qua b.	a ® b
...
(a: [ ], b: [1..n], c: [ ])	Cuối cùng chuyển n - 1 tầng từ c = 6 – a – b qua b là hoàn tất.	Hnt(n - 1, 6 - a - b, b);

Trường hợp thứ hai a và b cách nhau qua c trên đường thẳng. Ta có c = 2 và chỉ có hai tình huống cho a và b như sau:

Tình huống	j	k	l
1	a	c	b
2	b	c	a

Hình trạng	Ý nghĩa	Lệnh
(a: [1..n], c: [ ], b: [ ])	Hình trạng ban đầu với vị trí b không kề với vị trí a trên đường thẳng. abs(a - b) ¹ 1 Ta có c = 2. Để chuyển n tầng từ a sang b cách qua vị trí c = 2 ta phải...
...
(a: [n], c: [ ], b: [1..n - 1]	Chuyển (tạm) n - 1 tầng từ a qua b.	Hnt(n - 1, a, b)
(a: [ ], c: [n], b: [1..n - 1])	sau đó chuyển (tạm) tầng cuối của a qua c = 2.	a ® 2
...
(a: [1..n-1], c: [n], b: [ ])	Rồi lại chuyển (tạm) n - 1 tầng từ b qua a nhằm giải phóng vị trí đích b.	Hnt(n - 1, b, a)
(a: [1..n-1], c: [ ], b: [n])	để chuyển tầng lớn nhất n từ c = 2 qua b.	2 ® b
(a: [ ], c: [ ], b: [1..n])	Cuối cùng chuyển n - 1 tầng từ a qua b là hoàn tất.	Hnt(n - 1, a, b)

(*  Pascal  *)

(****************************

HNT.PAS – Ha Noi thang

Chuyen n tang thap tu coc a

sang coc b theo duong thang

1->2, 2->1 hoac 2->3, 3->2

            1 2 3

****************************)

uses crt;

var d: longint;

f: text;

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

begin

if n = 0 then exit;

if abs(a-b) = 1 then

begin

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

inc(d);

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

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

end

else

{-----------------------------

abs(a-b)=2 tuc la a = 1, b = 3

hoac a = 3, b = 1, do do c=2

------------------------------}

begin

Hnt(n-1,a,b);

inc(d);

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

Hnt(n-1,b,a);

inc(d);

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

Hnt(n-1,a,b);

end;

end;

procedure runHnt(n: byte);

begin

d :=  0;

assign(f,'hnt.out');

rewrite(f);

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

Hnt(n,1,2);

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

close(f);

readln;

end;

BEGIN

runHnt(3);

END.

Kết quả

1. 1 -> 2

2. 2 -> 3

3. 1 -> 2

4. 3 -> 2

5. 2 -> 1

6. 2 -> 3

7. 1 -> 2

8. 2 -> 3

9. 1 -> 2

10. 3 -> 2

11. 2 -> 1

12. 3 -> 2

13. 1 -> 2

Total: 13 step(s)