Luận văn Thuật toán Frame – Stewart giải bài toán tháp Hà Nội tổng quát

Đĩa thứ 7 và đĩa thứ 8 cũng là 0, do đó nó nằm trên đĩa số 6, trên cọc giữa. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 34 Bước 8 22 1 11111111  : Đĩa lớn nhất là 1, do đó nó nằm trên cọc phải (cọc đích). Mọi đĩa khác cũng là 1, do đó chúng được đặt lên trên đĩa lớn nhất. Vậy mọi đĩa nằm trên cọc đích và trò chơi kết thúc. §3 Đồ thị Hà Nội 3.1 Đồ thị Hà Nội Trò chơi Tháp Hà Nội có thể biểu diễn như một đồ thị không có hướng. Các đỉnh biểu thị phân bố của các đĩa và các cạnh biểu thị chuyển động của các đĩa. Với một đĩa, đồ thị là một tam giác: Với hai đĩa, đồ thị là ba tam giác được sắp xếp thành một tam giác lớn: Các nút tại các đỉnh của tam giác phía ngoài cùng biểu thị các phân bố với mọi đĩa trên cùng một cọc. Với 1n  đĩa, ta lấy đồ thị của n đĩa và thay mỗi tam giác nhỏ với đồ thị của hai đĩa. Đồ thị cho ba đĩa có dạng: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 35 1) Gọi các cọc là A, B, C. 2) Liệt kê các vị trí của các đĩa từ trái sang phải theo chiều tăng của kích thước. Các cạnh của các tam giác ngoài biên biểu thị con đường ngắn nhất để chuyển tháp từ một cọc này sang cọc khác. Cạnh ở giữa của các biên của tam giác lớn nhất biểu thị chuyển động của đĩa lớn nhất. Cạnh ở giữa của các biên của mỗi tam giác nhỏ hơn tiếp theo biểu thị chuyển động của mỗi đĩa nhỏ hơn tiếp theo. Các cạnh của tam giác nhỏ nhất biểu thị chuyển động của đĩa nhỏ nhất. Đồ thị của trò chơi tháp Hà Nội có liên quan mật thiết với tam giác Sierpinski (Sierpiński Triangle) hay còn được gọi là thảm Sierpinski. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 36 Đồ thị của trò chơi với n đĩa sẽ có 3n nút. Mỗi nút có ba cạnh đi tới nút khác, ngoại trừ ba nút ở góc chỉ có hai cạnh. Luôn luôn có thể chuyển đĩa nhỏ nhất sang một trong hai cọc khác. Và có thể chuyển một đĩa giữa hai cọc này ngoại trừ trường hợp khi tất cả các đĩa nằm trên một cọc. Các nút góc biểu thị ba trường hợp, khi mọi đĩa nằm trên một cọc. Biểu đồ cho n đĩa nhận được từ biểu đồ cho 1n  đĩa bằng cách copy ba lần-mỗi copy biểu thị mọi trạng thái và chuyển động của các đĩa nhỏ hơn cho một vị trí riêng của một đĩa mới lớn hơn và cùng với chúng tại các góc với ba cạnh mới biểu thị chỉ có ba khả năng chuyển đĩa lớn nhất. Do đó kết quả sẽ có 13n nút và vẫn có ba góc với hai cạnh. Khi số đĩa được thêm vào, đồ thị biểu diễn trò chơi sẽ tạo thành một hình Fractal, thảm Sierpinski. Rõ ràng rằng phần lớn các vị trí trong trò chơi sẽ không bao giờ đạt được nếu sử dụng lời giải ngắn nhất. Thật vậy, nếu các vị thầy tu trong truyền thuyết sử dụng lời giải dài nhất có thể (không trở lại vị trí cũ nào) thì cần 643 1 lần chuyển, nhiều hơn 2310 năm. 3.2 Bài toán Tháp Hà Nội và đƣờng Hamilton Đường Hamilton khép kín cho ba đĩa là: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 37 Đồ thị chỉ ra rằng: • Từ mỗi phân bố bất kì của các đĩa, tồn tại một con đường ngắn nhất chuyển mọi đĩa từ một trong ba cọc sang cọc khác. • Giữa mỗi cặp phân bố bất kì tồn tại một hoặc hai đường ngắn nhất khác nhau. • Từ mỗi phân bố bất kì của các đĩa, tồn tại một hoặc hai đường dài nhất không tự cắt chuyển mọi đĩa tới một trong ba cọc. • Giữa mọi cặp của các phân bố bất kì của các đĩa tồn tại một hoặc hai đường dài nhất không tự cắt. • Gọi nN là số các đường không tự cắt để chuyển tháp n đĩa từ cọc này sang cọc khác. Khi ấy: 1 2N  ; 2 3 1n n nN N N   . Thí dụ, 795 8 1.5656 10N   . Đồ thị nH tương ứng với các chuyển động được phép trong bài toán tháp Hà Nội. Hình trên chỉ ra một số đồ thị Hà Nội với 1,2,3,4n  . Đồ thị Hà Nội có thể xây dựng bằng cách chọn các đỉnh làm các hệ số nhị thức lẻ của tam giác Pascan được tính trên các số nguyên từ 0 đến 2 1n  và vẽ các đỉnh khi các hệ số là kề nhau theo đường chéo hoặc theo chiều ngang (xem Pool, 1994, [15]). Đồ thị nH có 3n đỉnh và  3 3 1 2 n  cạnh. Mỗi đồ thị Hà Nội có duy nhất một đường Hamilton (tương ứng, mỗi đồ thị Hà Nội có chính xác hai đường tròn Hamilton có hướng khác nhau). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 38 §4 Giải bài toán Tháp Hà Nội trên máy tính Code (mã) thể hiện thuật giải đệ qui bài toán Tháp Hà Nội: def Hanoi(n, A, C, B): if n == 1: print 'Move the plate from', A, 'to', C else: Hanoi(n - 1, A, B, C) print 'Move the plate from', A, 'to', C Hanoi(n - 1, B, C, A) Thuật giải đệ qui bài toán Tháp Hà Nội trên ngôn ngữ Pascal: VAR n: Integer; Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG: Char); Begin If sodia>0 then begin chuyen(sodia-1, CotNguon, CotTG, CotDich); Writeln(CotNguon,'->',CotDich); { Dia lon nhat hien tai } chuyen(sodia-1, CotTG, CotDich, CotNguon) End; End; BEGIN Write('Hay nhap so dia: '); Readln(n); chuyen(n,'A','C','B');//Thực hiện chuyển từ cột A sang cột C với cột B làm trung gian Readln; END. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 39 Chƣơng 3 BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi Reve-The Reve’s Puzzle) §1 Trò chơi Tháp Hà Nội với bốn cọc 1.1 Trò chơi Tháp Hà Nội với bốn cọc Trong Chương 2 chúng ta đã giải bài toán Tháp Hà Nội với ba cọc và n đĩa. Nó có thể giải được dễ dàng theo thuật giải đệ qui. Hơn nữa, có thể biết chính xác số lần chuyển tối ưu cho bài toán với n đĩa là 2 1n  . Như vậy, một bài toán với thuật giải đơn giản và tối ưu cũng có thể có độ phức tạp tính toán lớn (thời gian mũ), do đó có thể không giải được trong thời gian thực tế. Một mở rộng tự nhiên của trò chơi Tháp Hà Nội là trò chơi Tháp Hà Nội với bốn hoặc nhiều cọc (bài toán Tháp Hà Nội tổng quát). Như là sự tiếp nối của chương trước và chuẩn bị cho chương sau, chương này nghiên cứu bài toán Tháp Hà Nội cho bốn cọc. Bài toán này lần đầu tiên được Dudeney (1902) đặt ra và gọi tên là The Reve’s Puzzle (xem [7]). Gần đây, nhiều kết quả thú vị cũng đã được phát hiện cho bài toán này, các kết quả này là cơ sở để phát triển nghiên cứu bài toán Tháp Hà Nội tổng quát, vì vậy nó xứng đáng được xem xét tỉ mỉ trong một chương riêng, mặc dù, để thuận tiện, nhiều kết quả trong chương này cũng được trình bày cho bài toán nhiều cọc . Bài toán 2 (Bài toán Tháp Hà Nội với bốn cọc) Có bốn cọc được đánh số 1P , 2P , 3P , 4P . Cọc 1P được gọi là cọc nguồn. Ban đầu cọc nguồn chứa n đĩa có lỗ ở giữa và kích thước to Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 40 nhỏ khác nhau được xếp theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên” . Bài toán đặt ra là phải chuyển tất cả n đĩa từ cọc nguồn sang một trong các cọc 2P , 3P , 4P , sắp xếp cũng theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên”. Mỗi lần chỉ được chuyển một đĩa (trên cùng của cọc nào đó) từ cọc này sang cọc khác. Khi chuyển có thể sử dụng tất cả các cọc để đặt tạm thời các đĩa. Cọc cuối cùng chứa các đĩa theo thứ tự như trên cọc nguồn được gọi là cọc đích. Các cọc còn lại được gọi là cọc trung gian. Theo một số tài liệu, chính tác giả của bài toán Tháp Hà Nội, E. Lucas cũng là người đầu tiên xét bài toán với nhiều cọc. Năm 1889 Ông đã xét bài toán năm cọc và sắp xếp đĩa theo bốn màu khác nhau. Dudeney đã viết về bài toán Tháp Hà Nội với bốn cọc từ năm 1902. Trong hai trang đầu tiên của cuốn sách nổi tiếng của Ông The Canterbury Puzzle (xuất bản năm 1907 tại London và năm 1908 tại New York), Ông xét trò chơi với số cọc là 4 và số đĩa là 8, 10 hoặc 21, chỉ có khác là Ông đã thay các đĩa bằng các quân cờ (xem [7]) và được Ông gọi là Reve's puzzle. Trong phần lời giải (trang 131- 132), Dudeney đã khẳng định (không chứng minh) rằng số lần chuyển cần thiết tương ứng với 8, 10 hoặc 21 đĩa là 33, 49 hoặc 321. Hơn nữa, Ông còn xét trường hợp với số đĩa là số tam giác. Giả sử ( 1) 2 k k k t   là số tam giác thứ k và giả sử 4( )H n là số lần chuyển tối thiểu cần thiết để chuyển xong n đĩa. Dudeney tuyên bố rằng    4 4 12 2 1 k k kH t H t    ,  4 1 1H  . Từ đây ta có  4 3 5H  ;  4 6 17H  ,  4 10 49H  ,… Dudeney không cho một thuật toán nào cho phép tìm ra các số này, và cũng không có một gợi ý nào cho trường hợp số đĩa không phải là số tam giác, thí dụ như 8n  . Bài toán tổng quát với 3p  cọc, p là số tự nhiên bất kì với số đĩa n bất kì được B. M. Stewart đề xuất năm 1939 (xem [17]). Lời giải của bài toán này đã được Stewart [18] và Frame [9] trình bày đồng thời trong năm 1941. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 41 Bài toán tháp Hà Nội với bốn cọc được nhiều tác giả quan tâm (xem tài liệu đầy đủ trong [5]), Các thuật toán của Stewart và Frame cùng với một số thuật toán cải biên khác đã được chứng minh là tương đương (xem [11]). Vì vậy người ta thường gọi thuật toán của hai ông hoặc các thuật toán cải biên tương tự là thuật toán Frame-Stewart. Thuật toán Stewart-Frame cho bài toán Tháp Hà Nội tổng quát sẽ được nghiên cứu kĩ ở Chương 4. Dưới đây trình bày thuật toán Frame-Stewart cho bài toán bốn cọc (do Stewart đề xuất 1941). 1.2 Thuật toán Frame-Stewart (1941) cho bài toán Tháp Hà Nội với bốn cọc Bƣớc 0 Đánh số cọc là 1P , 2P , 3P , 4P . Mục đích của chúng ta là chuyển tất cả các đĩa từ cọc 1P sang cọc 4P , với qui tắc là mỗi lần chỉ chuyển một đĩa, và đĩa nhỏ không bao giờ nằm dưới đĩa lớn. Bƣớc 1 Chuyển l đĩa nhỏ nhất ( 0 l n  ) từ cọc 1P sang cọc 2P , trong quá trình chuyển có quyền sử dụng tất cả bốn cọc. Kí hiệu số lần chuyển tối ưu là 4( )S l . Bƣớc 2 Chuyển n l đĩa lớn nhất (còn lại) từ cọc 1P sang cọc 4P , không sử dụng cọc 2P (vì cọc 2P đang chứa l đĩa nhỏ). Nói cách khác, chuyển n l đĩa này bằng cách sử dụng phương pháp tối ưu giải bài toán ba cọc trong Chương 2, số lần chuyển tối ưu n l đĩa từ cọc 1P sang cọc 4P , không sử dụng cọc 2P là 2 1n l  . Bƣớc 3 Chuyển l đĩa nhỏ nhất từ cọc 2P sang cọc 4P , sử dụng tất cả bốn cọc. Như vậy, gọi 4( )S n là số lần chuyển tối ưu n đĩa trong bài toán Tháp Hà Nội với bốn cọc theo thuật toán Frame-Stewart thì với mỗi l , số lần chuyển tối ưu n đĩa từ cọc 1P sang cọc 4P phụ thuộc vào l và bằng 42 ( ) 2 1 n lS l   . Số lần chuyển tối ưu n đĩa trong bài toán Tháp Hà Nội với bốn cọc theo thuật toán Stewart là  4 4 4 0 ( ) 2 ( ) 2 1 min 2 ( ) 2 1n i n l l n S n S i S l          . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 42 1.3 Thuật toán Frame-Stewart cho bài toán Tháp Hà Nội với nhiều cọc Với 3p  , kí hiệu ( )pS n số lần chuyển ít nhất giải bài toán Tháp Hà Nội với p cọc và n đĩa theo thuật toán Frame-Stewart. Thí dụ, 3( ) 2 1 nS n   và 4(5) 13S  . Tương tự như trong bài toán bốn cọc, ta cũng có thuật toán Frame- Stewart cho bài toán với số cọc bất kì như sau. Nếu số cọc 3p  thì sử dụng thuật toán tối ưu cho bài toán Tháp Hà Nội với ba cọc trong Chương 2. Với 3p  và 0n  chọn số 0 i n  làm cực tiểu số lần chuyển các đĩa theo qui tắc (thuật toán Frame-Stewart) sau.  Chuyển l đĩa nhỏ trên cùng từ cọc nguồn sang cọc 1 ( n l đĩa dưới cùng vẫn ở trên cọc nguồn). Trong quá trình chuyển sử dụng tất cả các cọc. Điều này có thể làm được với số lần chuyển ít nhất được kí hiệu là ( )pS l .  Chuyển n l đĩa dưới cùng từ cọc nguồn sang cọc đích mất 1( )pS n l  lần chuyển (vì cọc 1 đang được sử dụng chứa các đĩa nhỏ nên chỉ còn sử dụng được 1p  cọc).  Chuyển l đĩa từ cọc 1 sang cọc đích. Trong quá trình chuyển sử dụng tất cả các cọc. Để làm được điều này cần ( )pS l lần chuyển. Công thức truy hồi cho lời giải bài toán Tháp Hà Nội dựa trên thuật toán Frame-Stewart là:  1 0 0 khi 0; ( ) 2 1 khi 3, 0; min 2 ( ) ( ) khi 3, 0. n p p p l n n S n p n S l S n l p n               (1.1) Như vậy, Bài toán Tháp Hà Nội với nhiều cọc trở thành bài toán tối ưu rời rạc: Tìm  1 0 ( ) min 2 ( ) ( )p p p l n S n S l S n l      . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 43 Nhận xét 1.1 Một điều thú vị là ta có thể nhận được kết quả của bài toán Tháp Hà Nội với ba cọc từ trường hợp hai cọc theo thuật toán Frame-Stewart như sau. Xuất phát từ thực tế, theo logic, ta đặt (khi số cọc 2p  và số đĩa 2n  thì bài toán không giải được): 2(0) 0S  , 2(1) 1S  , 2( )S n  với mọi 1n  . Với 3p  , 1n  ta chỉ có thể đặt 1l n  (để thành phần thứ hai 1 2( ) ( )pS n l S n l    là hữu hạn. Khi ấy công thức (1.1) trở thành: 3 3 2 3( ) 2 ( 1) (1) 2 ( 1) 1S n S n S S n      . Đây chính là công thức truy hồi tính số làn chuyển tối ưu khi 3p  . Như vậy, tổng cộng cần 12 ( ) ( )p pS l S n l  lần chuyển cho bài toán p cọc. Bài toán đặt ra là, cần tính số l để tổng này là nhỏ nhất. Thuật toán Frame-Stewart nói trên (với cách chọn l như trên) cho phép tìm ra một (một số) giá trị i sao cho  1 1 1 1 ( ) 2 ( ) ( ) min 2 ( ) ( )p p p p p l n S n S i S n i S l S n l           . (1.2) Nói cách khác, các giá trị i thỏa mãn (1.2) là số bước chuyển tối ưu trong lớp các thuật toán đề nghị. Stewart và Frame cũng đã chứng minh rằng, nếu n là số tam giác kn t , thì cách chọn tối ưu nhất cho l là l k , trong khi đó nếu 1k kt n t   thì cả hai giá trị 1k  và k đều là cách chọn tối ưu cho l . Như vậy, Stewart và Frame đã đề xuất các thuật toán hiển cho bài toán Tháp Hà Nội với bốn cọc. Từ đây ta cũng có nhận xét rằng, khác với trường hợp bài toán với ba cọc, lời giải cho bài toán với bốn cọc có thể là không duy nhất. §2 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với bốn cọc Như đã thấy trong mục trước, bài toán tìm số bước chuyển đĩa ít nhất trong trò chơi tháp Hà Nội được đưa về bài toán tối ưu rời rạc. Trong mục này chúng tôi trình bày các đánh giá bước chuyển tối ưu cho bài toán Tháp Hà Nội theo [13]. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 44 2.1 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với p cọc và n đĩa. Trƣờng hợp ( 1) 2 p p n   . Trước tiên ta xét các trường hợp đơn giản sau. Vì các nhận xét dưới đây đúng cho số cọc p bất kì nên ta phát biểu cho bài toán với số cọc bất kì. Nhắc lại rằng ( )pH n là kí hiệu số bước chuyển tối thiểu cần thiết để chuyển n đĩa từ cọc nguồn sang cọc đích trong bài toán tháp Hà Nội với p cọc và ( )pS n là kí hiệu số bước chuyển tối thiểu cần thiết để chuyển n đĩa từ cọc nguồn sang cọc đích trong bài toán tháp Hà Nội với p cọc theo thuật toán Frame-Stewart. Ta có Nhận xét 2.1 Dễ dàng thấy rằng (2) 3PH  với mọi 3p  và (3) 5PH  với mọi 4p  .Với 3p  và 1n p  thì ( ) 2 1pH n n  . Chứng minh Hiển nhiên vì 1n p  nên có thể chuyển mỗi đĩa từ số 1 đến số n từ cọc 1P sang mỗi cọc 2 1,..., nP P  tương ứng, mất n lần chuyển. Sau đó lại chuyển các đĩa từ số 1n  đến số 1 (đĩa to trước) từ các cọc tương ứng 2,...,nP P sang cọc 1nP  , mất 1n  lần chuyển. Như vậy, tổng cộng mất 2 1n  lần chuyển hay ( ) 2 1pH n n  . Nhận xét 2.2 Với 3p  và n p thì ( ) 2 1pH n n  . Chứng minh Trước tiên xây dựng tháp gồm 2 đĩa (đĩa số 1 và đĩa số 2) trên cọc nP , mất ba lần chuyển (xem §1 Chương 2). Sau đó lại chuyển các đĩa từ số 3 đến số n (tổng cộng 2n  đĩa) từ cọc 1P sang các cọc 2 1,..., nP P  tương ứng, mất 2n  lần chuyển. Sau đó chuyển 3n  đĩa từ số 1n  đến số 3 từ các cọc tương ứng 2 2,...,nP P sang cọc 1nP  , mất 3n  lần chuyển. Lại chuyển tháp Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 45 gồm 2 đĩa (đĩa số 1 và đĩa số 2) trên cọc nP sang cọc 1nP  , mất ba lần chuyển. Như vậy, tổng cộng mất    3 2 3 3 2 1n n n       lần chuyển hay ( ) 2 1pH n n  . Bây giờ ta xét trường hợp p n . Ta có Nhận xét 2.3 Ta luôn có: 1) ( 1) ( )p pH n H n  với mọi 1n  , 3p  ; 2) 1( ) ( )p pH n H n  với mọi 1n  , 3p  . Ta có Định lí 2.1 Với 3p  và ( 1) 2 p p p n    thì ( ) 4 2 1pH n n p   . Chứng minh Xét các trường hợp sau đây. Trƣờng hợp 1 2 3p n p   . Đặt 1n p l   , 0 2l p   . Thực hiện thuật toán sau. Bƣớc 1 Lần lượt chuyển 1p  đĩa nhỏ nhất từ cọc 1P sang các cọc 2,..., pP P tương ứng sao cho mỗi cọc có một đĩa và đĩa số 1 nằm trên cọc 2P . Còn lại  1n p l   đĩa nằm trên cọc 1P . Đã sử dụng hết p cọc. Bƣớc 2 Lần lượt chuyển l đĩa nhỏ nhất (đĩa số 1 đến đĩa số l ) từ các cọc 1 2,...,lP P (đĩa to nằm trên cọc 1lP chuyển trước) sang cọc 2lP . Như vậy, cọc 2lP chứa 1l  đĩa nhỏ nhất. Các cọc 2 1,..., lP P được giải phóng; Các đĩa số 2l  đến số 1p  ( 2p l  đĩa) vẫn nằm trên các cọc 3,...,l pP P tương ứng. Bƣớc 3 Lần lượt chuyển l đĩa còn lại (đĩa số p đến đĩa số  1p l n   ) từ cọc 1P sang các cọc tự do 1 2,...,lP P sao cho mỗi cọc có một đĩa và đĩa lớn nhất (số n ) nằm trên cọc 2P . Cọc 1P được giải phóng. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 46 Bƣớc 4 Lần lượt chuyển 1l  đĩa lớn (đĩa số 1n l p   đến đĩa số 1n  ) từ các cọc 3 1,..., lP P sang cọc 2P . Như vậy, cọc 2P chứa l đĩa lớn nhất. Các cọc 3 1,..., lP P được giải phóng. Bƣớc 5 Lần lượt chuyển 2p l  đĩa tiếp theo (còn lại trên các cọc 3,...,l pP P , đĩa số 1p  đến đĩa số 2l  ) sang cọc 2P . Như vậy, cọc 2P chứa 2p  đĩa lớn nhất. Các cọc 3,...,l pP P được giải phóng. Bƣớc 6 Lần lượt chuyển l đĩa nhỏ nhất (đĩa số 1 đến đĩa số l ) từ cọc 2lP sang cọc 1 3 4 1, , ,..., lP P P P tương ứng sao cho mỗi cọc có một đĩa và đĩa số 1 nằm trên cọc 1P , đĩa số 2 nằm trên cọc 3P ,…, đĩa số l nằm trên cọc 1lP . Sau đó chuyển đĩa 1l  từ cọc 2lP sang cọc 2P và chuyển l đĩa nhỏ nhất từ các cọc 1 4 3 1, ,..., , ,l lP P P P P sang cọc 2P . Tổng cộng số lần chuyển mất là:           ( ) 1 1 2 1 2 4 3 2 4 1 3 4 2 1. pH n p l l l p l l l p l p n p n p                        Trƣờng hợp 2  1 2 p p n   . Thực hiện thuật toán sau. Bƣớc 1 Lần lượt chuyển 2p  đĩa nhỏ nhất từ cọc 1P sang các cọc 2 1,..., pP P  sao cho mỗi cọc có một đĩa, đĩa nhỏ nhất nằm trên cọc 2P . Sau đó chuyển đĩa số 1p  từ cọc 1P sang cọc pP và lần lượt chuyển 2p  đĩa từ các cọc 1 2,...,pP P sang cọc pP . Mất tất cả    2 1 2 2 3p p p      lần chuyển 1p  đĩa từ cọc 1P sang cọc pP . Các cọc 2 1,..., pP P  được giải phóng (các đĩa lớn từ số p trở đi vẫn nằm trên cọc 1P , các đĩa nhỏ từ số 1 đến số 1p  nằm trên cọc pP ). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 47 Bƣớc 2 Lần lượt chuyển 3p  đĩa tiếp theo (các đĩa số p đến 2 4p  ) từ cọc 1P sang các cọc 2 2,..., pP P  tương ứng sao cho mỗi cọc có một đĩa. Sau đó chuyển đĩa số 2 3p  sang cọc 1pP  và lần lượt chuyển 3p  đĩa từ các cọc 1 2,...,pP P sang cọc 1pP  . Như vậy, để chuyển 2p  đĩa từ cọc 1P sang cọc 1pP  mất tất cả    3 1 3 2 5p p p      lần chuyển. Các cọc 2 2,..., pP P  được giải phóng. Bƣớc 3 Lần lượt chuyển 4p  đĩa tiếp theo (đĩa số 2 2p  đến đĩa số 3 5p  ) từ cọc 1P sang các cọc 2 3,..., pP P  sao cho mỗi cọc có một đĩa. Sau đó chuyển đĩa số 3 4p  sang cọc 2pP  và lần lượt chuyển 4p  đĩa từ các cọc 3 2,...,pP P sang cọc 2pP  . Như vậy, mất tất cả    4 1 4 2 7p p p      lần để chuyển 3p  đĩa từ cọc 1P sang cọc 2pP  . Các cọc 2 3,..., pP P  được giải phóng. Tương tự cho các bước tiếp theo. Bƣớc cuối cùng (bƣớc thứ 1p  ) Chuyển đĩa cuối cùng (đĩa thứ n ) từ cọc 1P sang cọc 2P . Như vậy, cọc kP , 2,3,...,k p có 1k  đĩa, cọc 1P trống. Tổng cộng số lần chuyển 1p  đĩa từ cọc 1P sang cọc pP , 2p  đĩa từ cọc 1P sang cọc 1pP  ,…, đến đĩa cuối cùng (thứ n ) từ cọc 1P sang cọc 2P mất là:           2 1 2 3 1 1 2 3 2 5 ... 1 1 2 p p p p p p              . Tổng số đĩa đã chuyển từ cọc 1P sang các cọc pP , 1pP  ,…, 3P là:          1 1 1 1 1 2 ... 1 2 2 p p p p p p n             . Lại lần lượt chuyển 1n  các đĩa từ các cọc 3,..., pP P sang cọc 2P như sau. Vì cọc 1P trống, cọc 2P chứa đĩa số n , cọc 3P chứa hai đĩa số 1n  , 2n  nên chuyển đĩa số 2n  từ cọc 3P sang cọc 1P , đĩa số 1n  từ cọc 3P Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 48 sang cọc 2P và lại chuyển đĩa số 2n  từ cọc 1P sang cọc 2P . Mất 3 lần chuyển. Và được 3 đĩa to nhất trên cọc 2P . Cọc 1P và 3P trống. Vì cọc 1P và 3P trống, cọc 2P chứa 3 đĩa to nhất n , 1n  , 2n  , cọc 4P chứa ba đĩa số đĩa số 3, 4, 5n n n   nên chuyển đĩa số 5n  sang cọc 1P , 4n  sang cọc 3P và 3n  sang cọc 2P , sau đó lại chuyển đĩa số 4n  từ cọc 3P sang cọc 2P và chuyển đĩa số 5n  từ cọc 1P sang cọc 2P . Mất 5 lần chuyển. Và được thêm 3 đĩa (thành 1+2+3=6) to nhất trên cọc 2P . Cọc 1P , 3P , 4P trống. Tương tự, đến bước cuối cùng ta có: Các cọc 1P , 3P ,…, 1pP  trống, cọc 2P chứa các đĩa từ có số từ n đến p , cọc pP chứa các đĩa có số từ 1p  đến số 1. Chuyển các đĩa có số 1 đến 2p  sang các cọc 1P , 3P ,…, 1pP  tương ứng. Sau đó chuyển đĩa số 1p  từ cọc pP sang cọc 2P . Lại chuyển các đĩa có số 2p  đến số 1 từ các cọc 1pP  ,…, 3P , 1P sang cọc 2P . Mất    2 1 2 2 3p p p      lần chuyển. Tất cả các đĩa ở trên cọc 2P . Công việc hoàn thành. Tổng số lần chuyển đĩa từ các cọc 3,..., pP P sang cọc 2P mất:         2 2 3 3 2 3 5 ... 2 3 2 2 p p p p p p             . Vậy tổng số lần chuyển đĩa là:       2 21 2 2 4 1 2 1 2 1 4 2 1p p p p p p p p n p             . Nhận xét 2.4 Ta cũng có thể viết số lần chuyển đĩa trên bằng       2 221 2 2 4 1 2 1 1p p p p p p         . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 49 Trƣờng hợp 3  1 2 3 2 p p p n     . Đặt  1 2 p p i n    . Thực hiện thuật toán như trên, nhưng số lần chuyển đĩa lúc này giảm đi 4i và bằng      2 2 1 ( ) 2 1 1 4 2 1 1 4 4 2 1 2 p p p S n p i p n n p                  . Định lí 2.1 chứng minh xong. Như vậy, nếu  1 2 p p n   thì ta có công thức hiển tính số bước chuyển tối ưu giải bài toán Tháp Hà Nội. Trường hợp  1 2 p p n   với số cọc p bất kì sẽ được xem xét trong Chương 4. Dưới đây chúng ta xét trường hợp 4p  . 2.2 Tính số bƣớc chuyển tối ƣu trong trò chơi Tháp Hà Nội với bốn cọc và n đĩa Định lí 2.2 Giả sử n là số đĩa cố định và    1 1 2 2 x x x x n     . Số bước chuyển tối ưu theo thuật toán Frame-Stewart là   224( ) 2 2 2 1xS n n x x     . (2.1) Chứng minh Xét các trường hợp sau. Trƣờng hợp 1  1 2 x x n   ( n là số tam giác) Thuật toán Frame-Stewart chuyển n đĩa từ cọc 1P sang cọc 4P như sau: Bước 1: Với 0 l n  chọn trước, chuyển l đĩa nhỏ nhất (trên cùng) từ cọc 1P sang cọc 4P (sử dụng tất cả bốn cọc). Số lần chuyển tối ưu là 4( )S l . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 50 Bước 2: Chuyển n l đĩa lớn nhất (dưới cùng) từ cọc 1P sang cọc 2P , sử dụng ba cọc (vì cọc 4P đang chứa l đĩa nhỏ nhất). Số lần chuyển tối ưu là 2 1n l  . Bước 3: Lại chuyển l đĩa nhỏ nhất (trên cùng) từ cọc 4P sang cọc 2P (sử dụng tất cả bốn cọc). Số lần chuyển tối ưu là 4( )S l . Như vậy, với mỗi 0 l n  chọn trước, số lần chuyển tối ưu là 4 4( ) 2 ( ) 2 1 n lS n S l    . (2.2) Rõ ràng, vì cọc 3P trống nên trong Bước 1, để chuyển l đĩa từ cọc 1P sang cọc 4P , ta có thể áp dụng thuật toán Frame-Stewart chuyển j đĩa nhỏ nhất (trên cùng, 0 j l  ) từ cọc 1P sang cọc 3P (sử dụng bốn cọc) và l j đĩa