Công thức hồi quy T(n):
- T(n) = T(n-1) + 1 + T(n-1)
Giả sử có 3 cột được đánh số lần lượt là 0, 1, 2. Ban đầu cột 0 có n đĩa, cột 2 có 0 đĩa, cột 3 có 0 đĩa. Công việc là chuyển n đĩa từ cột 0 sang cột 2:
- Bước 0:
- Chưa thực hiện di chuyển
- Cột 0 có n đĩa, cột 1 có 0 đĩa, cột 2 có 0 đĩa
- Bước T(n-1):
- Chuyển n-1 đĩa từ cột 0 sang cột 1, cột 2 là cột trung gian
- Cột 0 có 1 đĩa, cột 1 có n-1 đĩa, cột 2 có 0 đĩa
- Bước T(n-1) + 1:
- Chuyển đĩa thứ n từ cột 0 sang cột 2
- Cột 0 có 0 đĩa, cột 1 có n-1 đĩa, cột 2 có 1 đĩa
- Bước T(n-1) + 1 + T(n-1):
- Chuyển n-1 từ cột 1 sang cột 2, cột 0 là cột trung gian
- Cột 0 có 0 đĩa, cột 1 có 0 đĩa, cột 2 có n đĩa
Tổng quát hơn, 3 cột được đánh số id0, id1, id2, nhận giá trị trong tập { 0; 1; 2 }. Ban đầu cột id0 có d0 đĩa, cột id1 có d1 đĩa, cột id2 có d2 đĩa. Công việc là chuyển n đĩa từ cột id0 sang cột id2: (d0, d1, d2, n >= 0, n <= d0)
- Bước 0:
- Chưa thực hiện di chuyển
- Cột id0 có d0 đĩa, cột id1 có d1 đĩa, cột id2 có d2 đĩa
- Bước T(n-1):
- Chuyển n-1 đĩa từ cột id0 sang cột id1, cột id2 là cột trung gian
- Cột id0 có d0 - (n-1) đĩa, cột id1 có d1 + (n-1) đĩa, cột id2 có d2 đĩa
- Bước T(n-1) + 1:
- Chuyển đĩa thứ n từ cột id0 sang cột id2
- Cột id0 có d0 - n đĩa, cột id1 có d1 + (n-1) đĩa, cột 2 có d2 + 1 đĩa
- Bước T(n-1) + 1 + T(n-1):
- Chuyển n-1 từ cột id1 sang cột id2, cột id0 là cột trung gian
- Cột id0 có d0 - n đĩa, cột id1 có d1 đĩa, cột id2 có d2 + n đĩa
Chứng minh toán học
Giả sử T(n) là số lần di chuyển n đĩa ít nhất mà vẫn thoả mãn điều kiện đề bài.
Thử với các giá trị n nhỏ:
- n = 0, T(0) = 0, T(0) + 1 = 1 = 20
- n = 1, T(1) = 1, T(1) + 1 = 2 = 21
- n = 2, T(2) = 3, T(2) + 1 = 4 = 22
Nếu đặt S(n) = T(n) + 1, thì S(n) là cấp số nhân với số hạng đầu là 1, công bội là 2.
- Công thức tổng quát S(n) = 1.2n = 2n
- Công thức tổng quát của T(n) = S(n) - 1 = 2n - 1
Mặt khác, triển khai T(n):
- T(n) = 2n - 1
- T(n) = 2.2n-1 - 2 + 1
- T(n) = 2(2n-1 - 1) + 1
- T(n) = 2T(n-1) + 1
Do đó, công thức hồi quy của T(n) như sau:
- T(0) = 0
- T(n) = 2T(n-1) + 1, n > 0
Giải thuật
Với input n và k.
Nếu k < T(n-1):
- Bài toán từ input (n, k) thành bài toán nhỏ hơn có input (n-1, k) từ cột id0 sang cột id1 với cột id2 là cột trung gian.
Nếu k = T(n-1), chỉ có 1 lần di chuyển:
- Di chuyển k = T(n-1) lần, cấu hình (d0, d1, d2) thành (d0 - (n-1), d1 + (n-1), d2).
Nếu T(n-1) < k < T(n), có 2 lần di chuyển:
- Di chuyển T(n-1) + 1 lần từ cấu hình (d0, d1, d2) sang cấu hình (d0 - n, d1 + (n-1), d2 + 1).
- Di chuyển k - (T(n-1)+1) lần từ cột id1 sang cột id2 với cột id0 là cột trung gian.
- Bài toán từ input (n, k) thành bài toán nhỏ hơn có input (n-1, k - T(n-1)) từ cột id1 sang cột id2 với cột id0 là cột trung gian.
Nếu k = T(n) = T(n-1) + 1 + T(n-1), có 1 lần di chuyển:
- Di chuyển T(n-1) + 1 + T(n-1) lần từ cấu hình (d0, d1, d2) sang cấu hình (d0 - n, d1, d2 + n).
Mã nguồn (JavaScript)
Input:
-
n : số nguyên biểu hiện số đĩa cần di chuyển.
-
k : số nguyên biểu hiện số bước mà vị thần đã di chuyển.
Các biến sử dụng:
-
d : là mảng số nguyên gồm 3 phần tử
-
d[0] : số đĩa có ở cột 1, giống d0
-
d[1] : số đĩa có ở cột 2, giống d1
-
d[2] : số đĩa có ở cột 3, giống d2
-
id: mảng số nguyên 3 phần tử chỉ với index của d, nhận giá trị trong { 0; 1; 2 }, đóng vai trò như id0, id1, id2
-
Tc : số bước di chuyển ít nhất, tương ứng T(n)
-
Tp : số bước di chuyển ít nhất, tương ứng T(n-1)
-
Tp được tính theo Tc dựa trên công thức truy hồi, trong code tính theo công thức T(n)/2 thay vì (T(n) - 1) / 2.
Chú thích:
- Từ bước 0 tới bước T(n-1)-1 tương ứng với điều kiện
k < Tp
- Bước T(n-1) tương ứng điều kiện
k == Tp
- Bước T(n-1)+1 tới T(n)-1 tương ứng với phần
else
- Bước T(n) tương ứng với điều kiện
k == Tc
- Code chưa xử lý edge case.
function towerOfHanoi(n, k) {
let d = [n, 0, 0];
let id = [0, 1, 2];
let Tc = Math.pow(2, n) - 1;
let Tp = Math.floor(Tc / 2);
while (k > 0) {
if (k < Tp) {
Tc = Tp;
Tp = Math.floor(Tc / 2);
// [ id[0], id[1], id[2] ] = [ id[0], id[2], id[1] ];
[ id[1], id[2] ] = [ id[2], id[1] ];
} else if (k == Tp) {
k = 0;
d[id[0]] -= n-1;
d[id[1]] += n-1;
} else if (k == Tc) {
k = 0;
d[id[0]] -= n;
d[id[2]] += n;
} else { // Tp+1 <= k < Tc
k-= Tp + 1;
Tc = Tp;
Tp = Math.floor(Tc / 2);
d[id[0]] -= n;
d[id[1]] += n-1;
d[id[2]] += 1;
// [ id[0], id[1], id[2] ] = [ id[1], id[0], id[2] ];
[ id[0], id[1] ] = [ id[1], id[0] ];
}
n--;
}
return d;
}
for (let i = 0; i <= 31; ++i) {
const [ d1, d2, d3 ] = towerOfHanoi(5, i);
console.log(`(${d1}, ${d2}, ${d3})`);
}
Thực hiện mã nguồn với 1 ví dụ cụ thể
Input:
- Số đĩa n = 4, vị thần đã di chuyển k = 10 lần.
Khởi tạo:
- Tc = T(4) = 24 - 1 = 15
- Tp = T(3) = 7
- d = [4, 0, 0]
- id = [0, 1, 2]
Lần lặp 1:
- n = 4, k = 10, id = [0, 1, 2], d = [4, 0, 0], Tp = 7 < k = 10 < Tc
- Từ bước 0 đến bước 7 (T(n-1)): di chuyển 3 đĩa từ cột 0 sang cột 1 với cột 2 là trung gian, d từ [4, 0, 0] thành [1, 3, 0]
- Bước 8 (T(n-1) + 1): di chuyển 1 đĩa từ cột 0 sang cột 2, d từ [1, 3, 0] thành [0, 3, 1]
- Hoán đổi id từ [0, 1, 2] thành [1, 0, 2].
- Giảm k = 10 - 8 = 2
- Giảm Tc = 7, Tp = 3
- Giảm n = 3
- Kết thúc vòng lặp, chuyển sang bài toán nhỏ hơn:
- n = 3, k = 2, Tc = T(3) = 7, Tp = T(2) = 3, di chuyển 2 đĩa từ cột 1 sang cột 2 với cột 0 trung gian.
Lần lặp 2:
- n = 3, k = 2, id = [1, 0, 2], d = [0, 3, 1], k = 2 < Tp = 3.
- Giảm Tc = 3, Tp = 1, n = 2
- id đổi từ [1, 0, 2] thành [1, 2, 0]
- Kết thúc vòng lặp, chuyển sang bài toán nhỏ hơn:
- n = 2, k = 2, Tc = T(2) = 3, Tp = T(1) = 1, di chuyển 2 đĩa từ cột 1 sang cột 0 với cột 2 làm trung gian.
Lần lặp 3:
- n = 2, k = 2, id = [1, 2, 0], d = [0, 3, 1], k = 2 >= Tp + 1
- Bước 0 tới bước 1, di chuyển 1 đĩa từ cột 1 sang cột 2, d từ [0, 3, 1] thành [0, 2, 2].
- Bước 1 tới bước 2, di chuyển 1 đĩa từ cột 1 sang cột 0, d từ [0, 2, 2] thành [1, 1, 2].
Thoát khỏi vòng lặp:
Complexity
Bước khởi tạo:
- Khởi tạo biến: O(1)
-
Math.pow(2, n): O(n) hoặc O(logn)
Vòng lặp, mỗi lần lặp giảm n một giá trị. n -> 0 thì k -> 0 (vì 0 <= k < 2n). Các lệnh trong vòng lặp là O(1) => O(n)
Tóm lại, O(n)
. Mỗi lần xong 1 vòng lặp là được 1 bài toán con tương tự nhưng với n và k nhỏ hơn, thoả mãn 0 <= k < 2n.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?