Giới thiệu về Bài toán tháp Hà Nội
Bài toán tháp Hà Nội là một bài toán rất phổ biến trong lĩnh vực toán học và lập trình. Nó được sử dụng để giảng dạy về đệ quy và lập trình trong các khóa học về Toán học và Khoa học Máy Tính.
Tháp Hà Nội mô phỏng việc di chuyển đĩa từ một cọc này sang một cọc khác, tuân theo một số quy tắc nhất định. Bài toán này đòi hỏi sự logic và tư duy để giải quyết một cách hiệu quả.
Trong bài viết này, chúng ta sẽ cùng nhau khám phá cách giải quyết bài toán tháp Hà Nội bằng phương pháp đệ quy, một kỹ thuật mạnh mẽ và linh hoạt mà chúng ta thường gặp trong lập trình.
Lịch sử hình thành bài toán Tháp Hà Nội
Bài toán tháp Hà Nội có nguồn gốc từ một truyền thuyết Ấn Độ và đã được biết đến rộng rãi do nhà toán học người Pháp, Édouard Lucas, giới thiệu vào năm 1883 trong quyển sách "Récréations Mathématiques".
Truyền thuyết kể về một ngôi đền cổ ở Ấn Độ, nơi có ba cây cột đá và 64 chiếc đĩa vàng khác kích cỡ. Các linh mục ở đền thờ phải chuyển toàn bộ các đĩa từ một cột sang cột khác, tuân theo quy tắc không bao giờ đặt đĩa lớn hơn lên đĩa nhỏ hơn. Truyền thuyết nói rằng, khi toàn bộ các đĩa được chuyển đến cột mới, thế giới sẽ kết thúc.
Édouard Lucas đã lấy cảm hứng từ truyền thuyết này để tạo ra bài toán tháp Hà Nội, đặt tên theo tên thủ đô của Việt Nam vào thời đó.
Mô tả bài toán Tháp Hà Nội
Bài toán tháp Hà Nội được mô tả cụ thể như sau:
Cho 3 cọc A, B và C và n chiếc đĩa có kích thước khác nhau. Ban đầu, các chiếc đĩa được đặt ở cọc A, theo thứ tự lớn nhất ở dưới cùng, nhỏ dần khi đến chiếc đĩa cuối cùng.
Mục tiêu của bài toán là di chuyển toàn bộ chiếc đĩa từ cọc A sang cọc C, sử dụng cọc B làm trung gian, tuân thủ các quy tắc sau:
- Chỉ có 3 cọc để di chuyển, không có cọc thứ 4 nào.
- Một lần chỉ được di chuyển một đĩa, và chỉ được di chuyển đĩa nằm trên đỉnh của cọc, không được di chuyển đĩa nằm giữa.
- Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn, tuy nhiên không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất.
Cấu Trúc bài toán tháp Hà Nội
Bài toán tháp Hà Nội gồm hai yếu tố cơ bản: đĩa và cọc.
Đĩa
- Số lượng: Bài toán có n đĩa, số lượng đĩa có thể thay đổi tùy thuộc vào phiên bản cụ thể của bài toán. Thông thường, để dễ hình dung và giải quyết bài toán, con số lý tưởng là 3.
- Kích thước: Mỗi đĩa có một kích thước duy nhất và không có đĩa nào giống đĩa nào khác. Đĩa được sắp xếp theo thứ tự giảm dần từ trên xuống dưới trên cột ban đầu.
- Di chuyển: Chỉ có một đĩa có thể được di chuyển tại một thời điểm, và đĩa chỉ có thể được đặt lên một đĩa lớn hơn hoặc một cọc trống.
Cọc
- Số lượng: Có tổng cộng ba cọc, thường được gọi là A, B và C.
- Chức năng: Các cọc có chức năng giữ đĩa và hỗ trợ việc di chuyển những chiếc đĩa giữa chúng.
Quy tắc của bài toán Tháp Hà Nội
Bài toán tháp Hà Nội tuân theo các quy tắc sau:
- Di chuyển một đĩa: Trong một lần di chuyển, chỉ được phép di chuyển duy nhất chiếc đĩa trên cùng của mỗi cọc.
- Thứ tự các đĩa: Không được đặt đĩa có kích thước lớn hơn lên trên đĩa có kích thước nhỏ hơn.
Mục tiêu của bài toán Tháp Hà Nội
Bài toán tháp Hà Nội chủ yếu dựa vào sự di chuyển hợp lệ của các đĩa giữa các cọc, đồng thời tuân thủ các quy tắc, để đạt được mục tiêu di chuyển tất cả các đĩa từ cọc A sang cọc C.
Hướng giải bài toán bài toán Tháp Hà Nội
Để giải được bài toán này, chúng ta có ba bước :
- Di chuyển n-1 đĩa ở trên cùng ở cọc ban đầu đến cọc trung gian.
- Di chuyển chiếc đĩa lớn nhất ở dưới cùng của cọc đầu tiên đến cọc đích.
- Di chuyển n-1 chiếc đĩa ở cọc trung gian sang cọc đích.
Với số đĩa là 2, công việc là di chuyển từng chiếc đĩa một với các bước giải đã nêu trên.
Vậy, với số đĩa lớn hơn 2, làm thế nào để có thể chuyển n-1 chiếc đĩa sang cọc trung gian.
Từ hình ảnh, vấn đề của chúng ta là cần di chuyển cả 2 chiếc đĩa trên cùng ở cọc A sang cọc B. Để có thể di chuyển 2 chiếc đĩa này từ cọc A sang cọc B, ta sử dụng lại bài toán đã làm ở trường hợp 2 chiếc đĩa, khi đó, chúng ta có :
- Di chuyển chiếc đĩa trên cùng ở cọc A sang cọc C
- Di chuyển chiếc đĩa thứ hai sang cọc B
- Di chuyển chiếc đĩa ở cọc C, là chiếc đĩa nhỏ nhất, sang cọc B
Các bước tiếp theo diễn ra như sau :
- Di chuyển chiếc đĩa cuối cùng ở cọc A sang cọc C
- Di chuyển chiếc đĩa trên cùng ở cọc B sang cọc A
- Di chuyển chiếc đĩa còn lại ở cọc B sang cọc C
- Cuối cùng, di chuyển chiếc đĩa nhỏ nhất ở cọc A sang cọc C
Giải quyết bài toán lớn bằng một bài toán nhỏ hơn là biểu hiện rất rõ ràng cho việc chúng ta có thể xử lý bài toán này bằng đệ quy.
Chúng ta sẽ đi sâu hơn về cách giải bài toán tháp Hà Nội ở chương tiếp theo.
Cách giải quyết bài toán tháp Hà Nội bằng Đệ Quy
Sau khi biết được các vấn đề và mục tiêu của bài toán, chúng ta có thể phân tích và xử lý bài toán tháp Hà Nội bằng phương pháp đệ quy.
Cách làm đệ quy yêu cầu chúng ta xác định được 2 thứ, base case và recursion case.
Base case của bài toán tháp Hà Nội
Với bài toán này, base case chính là trường hợp mà ta di chuyển trực tiếp chiếc đĩa từ cọc ban đầu đến cọc đích, mà không cần sử dụng đến cọc trung gian.
Để có thể làm được điều này, số lượng đĩa mà chúng ta cần di chuyển là một chiếc, ứng với n = 1.
Với base case, khi số lượng đĩa = 1, chúng ta sẽ di chuyển chiếc đĩa đó từ cọc nguồn đến cọc đích.
Sở dĩ chiếc đĩa này luôn là đĩa 1, là đĩa nhỏ nhất, vì chỉ có đĩa 1 mới phù hợp với base case, nghĩa là chúng ta đã di chuyển tất cả các đĩa lớn hơn chiếc đĩa này đến vị trí mong muốn.
Recursion sẽ dừng lại tại thời điểm này vì base case không gọi lại bất kỳ đệ quy nào.
Recursion case của bài toán tháp Hà Nội
Recursion case là toàn bộ các trường hợp mà số lượng đĩa cần di chuyển lớn hơn một, khi đó chúng ta cần chia nhỏ bài toán, bằng cách liên tục thực hiện đệ quy với số lượng đĩa đã giảm dần sau mỗi lần thực hiện.
Sau mỗi lần thực thi recursion case, chúng ta sẽ tìm cách giảm số lượng đĩa cần di chuyển để chia nhỏ bài toán.
Ở câu lệnh 1 và câu lệnh 3, khi số lượng đĩa lớn, chương trình sẽ thực hiện các lời gọi đệ quy nhiều lần để giảm kích thước của bài toán, tức là số lượng đĩa sẽ được giảm dần cho đến khi chỉ còn một đĩa, lúc đó bài toán có thể được giải quyết một cách trực tiếp.
Toàn bộ code để giải bài toán tháp Hà Nội như sau:
void TowerOfHanoi(int numberOfDisks, char sourcePeg, char auxiliaryPeg, char targetPeg) {
if (numberOfDisks == 1) {
cout << "Di chuyen dia 1 tu " << sourcePeg << " sang " << targetPeg << endl;
return;
}
TowerOfHanoi(numberOfDisks - 1, sourcePeg, targetPeg, auxiliaryPeg);
cout << "Di chuyen dia " << numberOfDisks << " tu " << sourcePeg << " sang " << targetPeg << endl;
TowerOfHanoi(numberOfDisks - 1, auxiliaryPeg, sourcePeg, targetPeg);
}Phân tích BigO
Với bài toán tháp Hà Nội, mỗi lần thực hiện chương trình, ta sẽ thực hiện liên tiếp 2 chương trình con nhỏ hơn.
Giả sử ta có số lượng lời gọi hàm đệ quy T(n), ta có thể được mô tả bởi công thức đệ quy sau:
T(n) = 2T(n - 1)Khi bạn giải công thức đệ quy trên, bạn sẽ thu được:
T(n) = 2ⁿ - 1Do đó, Độ phức tạp thời gian của thuật toán là O(2ⁿ).
Độ phức tạp không gian của đoạn mã này chủ yếu tập trung vào chiều sâu của stack gọi hàm đệ quy. Vì mỗi lời gọi đệ quy tạo ra hai lời gọi đệ quy con, chiều sâu của stack có thể đạt tới n. Do đó, độ phức tạp không gian của đoạn mã này là O(n).
Kết luận về bài toán Tháp Hà Nội
Bài toán tháp Hà Nội là một bài toán kinh điển trong thuật toán, vẫn tiếp tục là một chủ đề nghiên cứu quan trọng và là một công cụ hữu ích để dạy về đệ quy và giải thuật.
Việc giải bài toán này bằng cách sử dụng đệ quy không chỉ minh họa sức mạnh và độ tinh tế của đệ quy mà còn làm nổi bật tính tự đồng nhất và tái sử dụng code.
Phân tích độ phức tạp của bài toán cho thấy nó có thể trở nên cực kỳ phức tạp với số lượng đĩa tăng lên, với độ phức tạp thời gian là O(2ⁿ) và độ phức tạp không gian là O(n).
Nhưng mặc dù vậy, việc tìm hiểu về bài toán này có thể mang lại nhiều hiểu biết về thuật toán và lập trình, đặc biệt là đệ quy, giúp phát triển kỹ năng tư duy lập trình và tư duy phân tích vấn đề.
Hy vọng rằng việc tìm hiểu về bài toán tháp Hà Nội và cách giải quyết sẽ giúp bạn nâng cao hiểu biết về đệ quy và áp dụng nó trong những bài toán phức tạp hơn trong lập trình.
