- [VB.NET] Hướng dẫn giải captcha sử dụng dịch vụ AZCaptcha API trên winform
- [C#] Hướng dẫn chứng thực đăng nhập ứng dụng bằng vân tay (Finger Print) trên máy tính
- [C#] Color Thief cách xuất màu sắc thiết kế từ hình ảnh
- [C#] Cách tạo bản quyền và cho phép dùng thử ứng dụng Winform
- [C#] Hướng dẫn sử dụng trình duyệt web Chrome convert HTML sang tập tin file PDF
- [C#] Kết nôi điện thoại Android, IOS với App Winform via Bluetooth
- [DATABASE] Cách query cộng trừ dồn dần trong Sqlserver
- [C#] Thiết kế ứng dụng Console đẹp với thư viện Spectre.Console
- [C#] Thiết kế ứng dụng Single Instance và đưa ứng dụng lên trước nếu kiểm tra ứng dụng đang chạy
- [C#] Giới thiệu JSON Web Token và cách đọc chuỗi token
- [C#] Cách tăng giảm font chữ tất cả các control trên winform
- [DEVEXPRESS] Tích hợp chức năng Tìm kiếm Search vào CheckedComboboxEdit
- [C#] Gởi email Metting Calendar Reminder kèm nhắc thời gian lịch họp
- [C#] Tìm kiếm xem danh sách từ khóa có tồn tại trong đoạn văn bản hay không
- [C#] Thiết kế giao diện ứng dụng trên Console sử dụng thư viện Terminal.Gui
- [C#] Hướng dẫn tạo mã VietQR Payment API Winform
- [C#] Sử dụng thư viện BenchmarkDotNet đo hiệu năng của hảm Method
- [DEVEXPRESS] Tìm kiếm không dấu tô màu highlight có dấu trên C# Winform
- [C#] Chia sẻ source code tạo hiệu ứng pixel Image trên winform
- [C#] Hướng dẫn kiểm tra số Container hợp lệ hay không
[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