Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Friday, March 28, 2014



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 abđứng kề nhau trên đường thẳng.
-          Hai cọc ab 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 ab 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)

0 comments:

Post a Comment

Popular Posts