Legos' writes and shares

Tháp Hà Nội và phương pháp đệ quy

Legos Light's photo
Legos Light
·

3 min read

💡
Thực ra tên chính xác của bài toán này là Tower of Hanoi, được phát minh bởi nhà toán học người Pháp Édouard Lucas, lần đầu tiên được giới thiệu vào năm 1883. Sau đó, nó được xuất bản thành một cuốn sách nhỏ vào năm 1889 và trong một tập sách được phát hành sau khi Lucas qua đời, có tựa đề Récréations mathématiques (Những trò giải trí toán học) - Wiki.

Thực ra đây là một bài toán rất cơ bản về phương pháp đệ quy mà đa số bạn sinh viên nào cũng biết. Tuy nhiên mình cực kỳ ấn tượng về lời giải của bài toán này và muốn chia sẻ với các bạn về lời giải này.

Bài toán

Có một tháp gồm \(n\) đĩa có kích thước khác nhau, được xếp chồng lên nhau theo thứ tự từ lớn đến nhỏ trên một trong ba cây cọc, tạm gọi là cọc A, B, C. Giả sử các đĩa được xếp ở cọc A, yêu cầu là phải di chuyển toàn bộ đĩa từ cọc A sang cọc C theo quy tắc sau:

  • Mỗi lần chỉ di chuyển 1 đĩa

  • Đĩa lớn không được nằm trên đĩa bé

  • Sử dụng cọc B làm cọc trung gian

Hình vẽ minh họa cho trường hợp di chuyển 6 đĩa (wiki):

Số bước ít nhất để chuyển \(n\) đĩa

Gọi \(C(n)\) là số lần ít nhất đề di chuyển \(n\) đĩa từ cọc A sang cọc C. Như vậy, để chuyển \(n+1\) đĩa, ta cần:

  • Chuyển \(n\) đĩa từ cọc A sang cọc B, lấy cọc C làm trung gian, tốn \(C(n)\) lần chuyển

  • Chuyển \(1\) đĩa lớn nhất từ cọc A sang cọc C, tốn \(1\) lần chuyển

  • Chuyển \(n\) đĩa từ cọc B sang cọc C, lấy cọc A làm trung gian, tốn \(C(n)\) lần chuyển

Như vậy để chuyển \(n+1\) đĩa từ cọc A sang cọc C ta cần tốn ít nhất là \(2C(n)+1\) lần (*).

Bây giờ, ta đi tìm công thức để tính \(C(n)\). Đây là một bài giải rất đẹp về phương pháp quy nạp.

Dự đoán công thức \(C(n) = 2^n-1\).

  • Với \(n=1, \quad C(1) = 1\) đúng vì chỉ cần chuyển 1 đĩa từ cọc A sang cọc C là xong

  • Giả sử công thức trên đúng đến \(k\), nghĩa là \(C(k)= 2^k-1\)

  • Ta cần chứng minh \(C(k+1) = 2^{k+1}-1\). Thật vậy ta có theo như (*): \(C(k+1)= 2C(k)+1 = 2(2^k-1)+1 = 2^{k+1}-1\) đúng, suy ra điều phải chứng minh.

Thuật toán

Ta dùng function \(move(n,source,middle,target)\) với \(n \) là số đĩa cần chuyển, \(source\) là tên cọc nguồn, \(middle \) là tên cọc trung gian, và \(target\) là tên cọc mục tiêu.

  • Nếu \(n = 1\), chuyển luôn từ cọc \(source \to target\)

  • Nếu \(n > 1\), ta gọi đệ quy theo các bước mô tả bên trên:

    • Chuyển \(n-1\) đĩa từ \(source \to middle\), lấy \(target\) làm trung gian: \(move(n-1, source, target, middle)\)

    • Chuyển \(1\) đĩa từ \(source \to target\): \(move(1, source, middle, target)\)

    • Chuyển \(n-1\) đĩa từ \(middle \to target\), lấy \(source\) làm trung gian: \(move(n-1, middle, source, target)\)

Code tham khảo bằng javascript

function move(n, source, middle, target){
    if (n == 1) console.log(`${source} -> ${target}`);
    // recursive calls
    move(n - 1, source, target, middle);
    move(1, source, middle, target);
    move(n-1, middle, source, target);
}

move(4, 'A', 'B', 'C');
hanoi tower