- [DEVEXPRESS] Chia sẻ code các tạo report in nhiều hóa đơn trên XtraReport C#
- [POWER AUTOMATE] Hướng dẫn gởi tin nhắn zalo từ file Excel - No code
- [C#] Chia sẻ code lock và unlock user trong domain Window
- [SOFTWARE] Giới thiệu bộ phần mềm tính Kết Cấu Thép HatteSale, Mộng Đơn, Dầm, Sàn, Móng Cọc, Vách, Xà Gồ, Tính Tải Trọng
- [DEVEXPRESS] Vẽ Biểu Đồ Stock Chứng Khoán - Công Cụ Thiết Yếu Cho Nhà Đầu Tư trên Winform
- [C#] Hướng dẫn bảo mật ứng dụng 2FA (Multi-factor Authentication) trên Winform
- [C#] Hướng dẫn convert HTML code sang PDF File trên NetCore 7 Winform
- [C#] Hướng dẫn viết ứng dụng chat với Gemini AI Google Winform
- Hướng dẫn khóa file bằng nhiều process id, không cho xóa tập tin
- Hướng dẫn cách tạo Product Id cho ứng dụng phần mềm XXXXX-XXXXX-XXXXX-XXXXX
- [SQLSERVER] Hướng dẫn tạo script sql từ ứng dụng Sqlserver management Studio
- [C#] Hướng dẫn sử dụng thư viện AutoITx lấy id và password Ultraviewer trên winform
- [VB.NET] Hướng dẫn lấy thông tin tài khoản đăng nhập windows và khởi động lại ứng dụng ở chế độ Administrator
- [C#] Sử dụng thư viện Polly gửi lại request api khi request bị lỗi hay rớt mạng
- [DEVEXPRESS] Chia sẻ source code tạo báo cáo report in tem nhãn label trên C# winform
- [DEVEXPRESS] Hướng dẫn vẽ biểu đồ Bar Chart trên Winform
- [C#] Tạo form đăng nhập và đăng ký với hiệu ứng Sliding Animation Effect
- [C#] Hướng dẫn tạo thanh toán đơn hàng qua mã vạch VietQR sử dụng API PayOS hoàn toàn miễn phí
- [C#] Hướng dẫn ghi log ra RichTextBox giống Console trên Winform sử dụng thư viện Serilog
- [C#] Hướng dẫn cách tạo mã QR Code trên file Excel
[C#] Sử dụng đệ quy để giải bài toán Tháp Hà Nội
Bài viết hôm nay, mình sẽ chia sẽ đến các bạn cách sử dụng đệ quy để giải bài toán tháp Hà Nội trong lập trình C#.
Tháp Hà Nội (Tower of Hanoi) là gì ?
Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.
Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.
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ỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
- Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
- Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.
Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.
Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1
. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7
bước.
Giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi)
Để viết giải thuật cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi), đầu tiên chúng ta cần tìm hiểu cách giải bài toán với số đĩa là 1 và 2. Chúng ta gán 3 cột với các tên là:
-
cotNguon: cột ban đầu chứa các đĩa
-
cotDich: cột cần di chuyển các đĩa tới
-
cotTrungGian: cột trung gian có mục đích làm trung gian trong quá trình di chuyển đĩa
Nếu chỉ có 1 đĩa, chúng ta chỉ cần di chuyển từ cotNguon tới cotDich.
Nếu có 2 đĩa:
- Đầu tiên chúng ta di chuyển đĩa trên cùng (đĩa nhỏ nhất) tới cotTrungGian.
- Sau đó chúng ta di chuyển đĩa ở dưới cùng (đĩa to hơn) tới cotDich.
- Và cuối cùng di chuyển đĩa nhỏ nhất từ cotTrungGian về cotDich.
Từ hai giải thuật phần giải thuật trên chúng ta sẽ có giải thuật cho bài toán Tháp Hà Nội (Tower of Hanoi) cho 3 đĩa trở lên. Chúng ta chia ngăn xếp các đĩa thành hai phần: đĩa thứ lớn nhất (đĩa thứ n) là phần thứ nhất và (n-1) đĩa còn lại là phần thứ hai.
Mục đích của chúng ta là di chuyển đĩa thứ n từ cotNguon tới cotDich và sau đó đặt tất cả (n-1) đĩa còn lại lên trên nó. Bây giờ chúng ta có thể tưởng tượng ra cách giải bài toán trên dựa vào đệ qui theo các bước sau:
Bước 1: Di chuyển n-1 đĩa từ cotNguon tới cotTrungGian
Bước 2: Di chuyển đĩa thứ n từ cotNguon tới cotDich
Bước 3: Di chuyển n-1 đĩa từ cotTrungGian về cotDich
Giải thuật đệ qui cho bài toán Tháp Hà Nội (Tower of Hanoi) là:
Bắt đầu giải thuật Tháp Hà nội Hanoi(disk, cotNguon, cotDich, cotTrungGian)
IF disk == 0, thì
di chuyển đĩa từ cotNguon tới cotDich
ELSE
Hanoi(disk - 1, cotNguon, cotTrungGian, cotDich) // Bước 1
di chuyển đĩa từ cotNguon tới cotDich // Bước 2
Hanoi(disk - 1, cotTrungGian, cotDich, cotNguon) // Bước 3
Kết thúc IF
Kết thúc giải thuật
Và bây giờ mình sẽ sử dụng Code C# để giải bài toán Tháp Hà Nội này:
Source code Tháp Hà Nội C#:
public class TowersOfHanoi
{
public static void Main(String[] args)
{
char startPeg = 'A';
char endPeg = 'C';
char tempPeg = 'B';
int totalDisks = 3;
solveTowers(totalDisks, startPeg, endPeg, tempPeg);
}
private static void solveTowers(int n, char startPeg, char endPeg, char tempPeg)
{
if (n > 0)
{
solveTowers(n - 1, startPeg, tempPeg, endPeg);
Console.WriteLine("Move disk from " + startPeg + ' ' + endPeg);
solveTowers(n - 1, tempPeg, endPeg, startPeg);
}
}
}
Kết quả:
Move disk from A to C
Move disk from A to B
Move disk from C to B
Move disk from A to C
Move disk from B to A
Move disk from B to C
Move disk from A to C
CHÚC CÁC BẠN THÀNH CÔNG!
laptrinhvb via vietjack.com