HomeLập trình

Bài toán Tháp Hà Nội, mô tả bằng C++ và hướng dẫn trên Scratch

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

Bài toán Tháp Hà Nội The Tower of Hanoi là một bài toán cổ điển, nổi tiếng, dù bạn có học ngôn ngữ lập trình nào thì cũng đều biết đến bài toán này, bài toán có mặt trong hầu hết các sách Toán, Tin học kinh điển, chúng ta hãy cùng xem lại bài toán này

Nội dung bài toán The Tower of Hanoi

n cái đĩa với kích thước khác nhau, được sắp xếp trong cọc A như trên hình vẽ, đĩa to ở dưới, đĩa bé ở trên. Yêu cầu cần chuyển toàn bộ các đĩa này sang cọc C, mỗi lần chỉ được chuyển một đĩa, và trong quá trình chuyển đĩa cần tuân thủ nguyên tắc: không được phép xếp đĩa lớn lên trên đĩa nhỏ hơn. Được phép dùng thêm 1 cọc B làm trung gian hỗ trợ trong quá trình chuyển.

Hình ảnh mô tả bài toán Tháp Hà Nội.

Lời giải đệ quy bài toán Tháp Hà Nội

Với n = 1, việc chuyển 1 đĩa từ cọc A sang C rất đơn giản, chỉ cần dịch chuyển theo nghĩa thông thường.

Giả sử bài toán đã được giải cho số lượng đĩa < n.

Với số lượng đĩa = n, chúng ta sẽ thực hiện lần lượt như sau:

  • Dịch chuyển n-1 đĩa ở phía trên từ cọc A sang cọc B (lấy cọc C làm trung gian). Việc này có thể làm được theo giả thiết qui nạp.
  • Còn lại 1 đĩa cuối cùng lớn nhất trong cọc A, bây giờ sẽ chuyển sang cọc
  • Dịch chuyển n-1 đĩa đang có từ cọc B sang cọc C (lấy cọc A làm trung gian). Việc này có thể làm được không ảnh hưởng gì đến đĩa hiện có tại cọc C vì đĩa này to nhất. Sau bước này toàn bộ số n đĩa đã được chuyển vào cọc

Lời giải như trên được gọi là lời giải đệ qui, có thể được mô tả bằng ngôn ngữ thuật toán, như sau:

Tháp Hà nội với n đĩa, cọc 1, cọc 2, cọc 3. Nếu n > 0 thì

Thực hiện Tháp Hà Nội với n - 1 đĩa, cọc 1, cọc 3, cọc 2.

Dịch chuyển 1 đĩa từ cọc 1 sang cọc 2.

Thực hiện Tháp Hà Nội với n - 1 đĩa, cọc 3, cọc 2, cọc 1.

Lời giải bằng ngôn ngữ lập trình C++

Thuật toán trên dễ dàng viết bằng 1 ngôn ngữ lập trình cụ thể.

Lời giải đệ qui trên, nếu mô tả bằng ngôn ngữ lập trình, ví dụ C++, thì có thể như sau: Thủ tục chính HanoiTower() như sau:

void HanoiTower(int n,int Source,int Destination,int Auxiliary)

{

if(n > 0) {

HanoiTower(n-1, Source, Auxiliary, Destination); TransferDisk(Source, Destination);

HanoiTower(n-1, Auxiliary, Destination, Source);

}

}

Thủ tục TransferDisk() như sau:

void TransferDisk(int Source, int Destination)
{
cout<<"Di chuyển đĩa từ cọc:"<<Source<<"sang cọc:"<<Destination
<<"\n";

Lệnh chính thực hiện mô phỏng bài toán như sau:

int n = 10;
HanoiTower(n, 1, 3, 2);

Mô phỏng lời giải bằng Scratch

Chúng ta sẽ bắt đầu mô phỏng bài toán Tháp Hà Nội bằng ngôn ngữ lập trình Scratch.

Hình ảnh mô phỏng bài toán Tháp Hà Nội trên Scratch

Giao diện ban đầu của chương trình như hình trên. Khi chạy chương trình sẽ mô phỏng quá trình di chuyển từng đĩa để cuối cùng sẽ chuyển toàn bộ các đĩa từ cọc 1 sang cọc 3.

Việc mô phỏng lời giải của bài toán Tháp Hà Nội trong Scratch tương đối dễ dàng vì Scratch hỗ trợ thủ tục và đệ qui.

Thủ tục lõi của chương trình Hanoi tower () được mô tả như sau:

Chúng ta sẽ thiết kế chương trình này như sau:

  • Khi bắt đầu chạy, chương trình sẽ yêu cầu nhập số tự nhiên N là số các đĩa sẽ được mô phỏng của bài toán. Chú ý là do sự hạn chế của không gian sân khấu nên số N sẽ bị hạn chế. Trong thiết kế của chúng ta, N < 7. Sau khi nhập, màn hình sẽ hiện trạng thái ban đầu của bài toán như hình vẽ trên.
  • Bấm phím Space để bắt đầu quá trình mô phỏng. Quá trình mô phỏng sẽ kết thúc khi toàn bộ số đĩa từ Cọc 1 đã được chuyển sang Cọc đích (ví dụ 2 hoặc 3).

Thiết kế nhân vật chính.

Các nhân vật chính của chương trình.

Stt Tên  Ý nghĩa Ghi chú
1 Disk Disk. Nhân vật trung tâm, chính của chương trình. Nhân vật này sẽ có 6 trang phục với kích thước chính là hình ảnh các đĩa cần chuyển. Sử dụng kỹ thuật Clone để thể hiện các disk này trên màn hình. Chiều cao của các trang phục là như nhau và = 40. Chiều rộng của các trang phục từ 90 à 140.
2  Pencil Pencil. Bút chì có nhiệm vụ vẽ hình ảnh các cọc đĩa trên màn hình.
3

Hanoi tower

Title. Biển hiệu tên của chương trình.

Nhân vật Disk được thiết kế với các trang phục là hình ảnh các đĩa như sau

Nhân vật Disk sẽ có 6 trang phục tương ứng với 6 hình ảnh của đĩa, ứng với các giá trị số từ 1 đến 6. Các hình ảnh đĩa này có chiều cao = 40 và chiều rộng tương ứng từ 90 à 140.

Tính toán tọa độ thể hiện các đĩa trên màn hình.

Để thể hiện các đĩa trên màn hình, chúng ta sẽ vẽ 1 lưới kích thước 7 hàng x 3 cột.

Tọa độ các vị trí tâm của lưới được xác định bởi 2 mảng dữ liệu XList (hàng ngang) và YList (hàng dọc). Mỗi ô lưới có kích thước 160 x 40.

Hình ảnh dưới đây mô tả ý nghĩa của lưới trên màn hình và vị trí vẽ các cọc đĩa tương ứng.

Các đĩa sẽ được đặt từ dưới lên. Hàng trên cùng để trống dành không gian cho việc mô phỏng dịch chuyển đĩa.

Danh sách các biến nhớ chính.

  •  Number (biến nhớ): Số lượng đĩa được mô tả của chương trình. Theo thiết kế nhân vật Disk chỉ có 6 trang phục, do đó giá trị Number phải thỏa mãn: 1<=Number<=6. (Giá trị này sẽ được nhập ngay đầu chương trình)
  • Disk1, Disk2, Disk3 (list): Các dãy số mô tả thông tin của các đĩa trong cọc 1, 2, 3. Ban đầu các giá trị của các đĩa là 1, 2, 3, …, Number được lưu trong Disk1. (Ban đầu các mảng Disk2, Disk3 là rỗng)
  • ID (biến nhớ riêng của nhân vật Disk): Biến nhớ riêng của Disk mô tả giá trị tương ứng của Clone – đĩa được thể hiện trên màn hình. Mỗi Clone tương ứng với 1 đĩa trên màn hình (Giá trị ID sẽ nhận là 1, 2, 3, …, Number.)
  • N1, N2 (biến nhớ): Các biến nhớ này được dùng trong thủ tục dịch chuyển 1 đĩa trên màn hình, từ cọc có số N1 sang cọc có số N2.
  • Position (biến nhớ): Biến nhớ trung gian dùng trong thủ tục di chuyển đĩa trên màn hình (Tại 1 thời điểm của chương trình, Position = length của bảng Disk N2).
  • s (biến nhớ): Biến nhớ dùng để lưu giá trị ID của đĩa (Clone) cần dịch chuyển (Tại 1 thời điểm của chương trình, s = ID của đĩa nằm trên cùng của cọc N1. Vậy s = phần tử đầu tiên của bảng Disk N1 tương ứng).

 Sơ đồ hoạt động chương trình

Mô tả phần lõi chính của chương trình

Phần lõi chính của chương trình bắt đầu ngay sau khi người dùng nhập giá trị Number = số lượng đĩa cần thể hiện. Thủ tục Init<n> sẽ thiết lập 3 mảng Disk1, Disk2, Disk3 các giá trị ban đầu của 3 Cọc đĩa. Disk1 bao gồm Number phần tử 1, 2, …, Number. Các Disk2 và Disk3 rỗng.

 

Khi người dùng bấm phím Space thì sẽ thực hiện thủ tục chính của chương trình.

Thủ tục chính sẽ gọi, ví dụ Hanoi Tower (Number, 1, 2, 3) để thực hiện việc chuyển toàn bộ số đĩa từ Cọc 1 sang Cọc 3 với trung gian là Cọc 2.

Trong thủ tục chính trên, phần phức tạp nhất chính là đoạn thủ tục con Transfer Disk dùng để dịch chuyển 1 đĩa ở trên cùng của Cọc N1 sang Cọc N2. Chúng ta cùng phân tích kỹ cách thực hiện của thủ tục này. Thuật toán xử lý thủ tục này có thể mô tả chung như sau:

  1. Tính giá trị s = ID của đĩa cần chuyển. Giá trị này chính = ID của Clone của nhân vật Disk tương ứng.
  2. Cập nhật mảng Disk của N2 tương ứng. Đưa giá trị s vào mảng này và tính toán giá trị Position = length của mảng này trước khi cập nhật.
  3. Thực hiện việc di chuyển Clone có ID = s từ Cọc N1 sang vị trí mới trên Cọc N2. Cụ thể như sau:

Tính giá trị s = ID của đĩa cần chuyển. Giá trị này chính = ID của Clone của nhân vật Disk tương ứng.

Cập nhật mảng Disk của N2 tương ứng. Đưa giá trị s vào mảng này và tính toán giá trị Position = length của mảng này trước khi cập nhật

Sau khi thực hiện xong 2 công việc trên, cập nhật các giá trị N1, N2 (là 2 biến tổng thể hệ thống) và gửi thông điệp MoveDisk cho nhân vật Disk để tiến hành di chuyển

Sơ đồ sau mô tả trạng thái của các Cọc và các bảng Disk1, Disk2, Disk3 tại thời điểm có thông điệp MoveDisk. Clone với ID = s sẽ phải di chuyển qua 3 đoạn thẳng được ký hiện (1), (2), (3) trên hình sau. Tọa độ các điểm cuối đã được tính toán chính xác như đã chỉ ra trong hình

Đoạn chương trình xử lý cho 1 đĩa dịch chuyển từ Cọc N1 sang Cọc N2 như sau

Lập trình chi tiết.

Sân khấu là nơi thực hiện đầu tiên việc yêu cầu người dùng nhập từ bàn phím giá trị Number = số lượng disk sẽ được mô phỏng. Giá trị này phải > 0 và <

Sau khi nhập xong, sân khấu sẽ thực hiện việc thiết lập bộ dữ liệu chính: Disk1, Disk2, Disk3 và gửi thông điệp Start cho nhân vật Disk.

 

 

 

 

 

Thủ tục Init dữ liệu như sau

Đồng thời nhân vật Pencil sẽ thực hiện việc vẽ 3 Cọc trên màn hình. Chương trình sau của Pencil sẽ thực hiện công việc vẽ này. Sẽ vẽ 3 vạch thẳng và 1 vạch ngang.

Khi bắt đầu chương trình, gán ID = 0 cho nhân vật Disk và ẩn đi.

Nhận thông điệp Start, Disk sẽ tạo ra Number phân thân – Clone của mình và thể hiện tại Cọc 1. Đoạn chương trình này như

Khi người dùng bấm phím Space, sân khấu sẽ thực hiện thủ tục chính của chương trình là Hanoi Tower. Ví dụ chương trình như sau

Đoạn chương trình thủ tục chính có dạng tổng quát hơn như sau

Trong thủ tục trên, quan trọng nhất là thủ tục Transfer Disk có nhiệm vụ thực hiện việc dịch chuyển 1 đĩa trên màn hình.

Toàn bộ chương trình của Transfer Disk như sau.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Thủ tục trên chỉ thực hiện cập nhập dữ liệu vào các bảng Disk, cập nhật biến nhớ s và Position.

Phần thực hiện di chuyển cụ thể sẽ được chuyển sang nhân vật Disk bằng thông điệp MoveDisk.

Nhận được MoveDisk, Clone tương ứng của Disk sẽ thực hiện theo chương trình sau:

Chúc các bạn thành công!

Bài viết dựa trên giáo trình của Thầy Bùi Việt Hà

 

 

 

 

 

 

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *