Giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C/C++

1
4067

Trước khi tìm hiểu cách giải bài toán tháp Hà Nội (Tower of Hanoi), mình xin nhắc lại các quy tắc của trò chơi Tháp Hà Nội này:

Bài toán tháp Hà Nội (Tower of Ha Noi )

Bài toán tháp Hà Nội ( Tower of Hà Nội ) là một trò chơi toán học gồm 3 cột và số đĩa nhiều hơn 1. Trong hình dưới mô tả trò chơi gồm có ba đĩa

Bài-Toán-Tháp-Hà-Nội
Bài toán tháp Hà Nội

Với quy tắc các đĩa nhỏ phải nằm trên các đĩa lớn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội khác nhau, tuy nhiên cách giải là vẫn vậy.

Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)

Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):

Mình xin 5 phút quảng cáo nha =))

Hình ảnh dưới đây là mô tả cách giải bài toán tháp Hà Nội

thap-ha-noi
Tháp Hà Nội

Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông dụng nhất là: “Người chơi được cho ba cái cọc và một số đĩa có kích thước khác nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

  • một lần chỉ được di chuyển một đĩa
  • một đĩa chỉ có thể được đặt lên một đĩa lớn hơn

Bài toán tháp Hà Nội với n đĩa thì có ít nhất 2^n – 1 bước thực hiện. Với ví dụ trên là 3 đĩa thì số bước giải ít nhất là 2^3-1=7 cách giải.

Cách giải bài toán tháp Hà Nội bằng đệ quy

Qui ước: Đặt tên 3 cột là A B C để tiện theo dõi. Yêu cầu bài toán là chuyển n chiếc đĩa từ cột A sang cột C

Cách giải

  • Đầu tiên ta lấy cột C làm cọc trung gian. Chuyển n-1 chiếc đĩa sang cột B.
  • Ta chuyển chiếc đĩa lớn nhất sang cột C
  • Lấy cột A làm cột trung gian chuyển n-1 chiếc đĩa từ cột B sang cột C

Hình ảnh dưới đây miêu tả cách giải này

Tower_of_Hanoi_1
Cách giải bài toán tháp Hà Nội

Code C++

Code C

Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

 

avatar
1 Comment threads
0 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
JayNg Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
JayNg
Guest
JayNg

thanks for sharing!