Trò chơi 1: Tháp Hà Nội trong C++ và Python: tư duy đệ quy, vì sao cần 2^n − 1 nước, tìm nước đi thứ k bằng bit

Series: Thuật toán qua trò chơi Độ khó: Trung bình Trò chơi 1 / Thuật toán qua trò chơi Đệ quy Chia để trị

// Thuật toán qua trò chơi · Trò chơi 1

Tháp Hà Nội: chơi thử, rồi để đệ quy giải hộ

Ba cái cọc, một chồng đĩa và luật chơi đơn giản tới mức học sinh lớp 6 cũng hiểu. Thế mà với 64 đĩa, vũ trụ già thêm vài chục lần vẫn chưa chơi xong! Em hãy chơi thử, rồi xem đệ quy giải hộ chỉ bằng 5 dòng code.

Lời mở đầu

Năm 1883, nhà toán học Pháp Édouard Lucas bán ra một món đồ chơi tên là Tháp Hà Nội, kèm theo một truyền thuyết rùng rợn: trong một ngôi đền cổ có ba cây cọc kim cương, trên một cọc xếp sẵn 64 chiếc đĩa vàng, to ở dưới nhỏ ở trên. Các nhà sư ngày đêm chuyển đĩa sang cọc khác theo đúng luật, mỗi lần một đĩa, không bao giờ đặt đĩa to lên đĩa nhỏ. Khi chiếc đĩa cuối cùng được đặt xong, thế giới sẽ kết thúc.

Có nên lo không? Giả sử các nhà sư chuyển cực nhanh, mỗi giây một đĩa và không bao giờ đi nhầm. Đọc xong bài này em sẽ tự tính được: họ cần $2^{64} - 1$ giây, tức khoảng 585 tỉ năm, gấp hơn 40 lần tuổi của vũ trụ. Thế giới tạm thời an toàn 😄. Điều thú vị hơn: chính con số khổng lồ đó lại được sinh ra từ một hàm đệ quy chỉ dài 5 dòng.

Đây là bài mở đầu series Thuật toán qua trò chơi: mỗi bài là một trò chơi quen thuộc mà em chơi được ngay trên trang, và đằng sau nó là một thuật toán thật sự hay gặp trong đề thi. Bài hôm nay ôn và đào sâu đệ quy. Nếu em chưa quen hàm gọi lại chính nó, hãy xem lại phần đệ quy tính $n!$ ở bài 5: Hàm và ngăn xếp lời gọi ở bài 15: Đệ quy và quay lui. Ở Phần 4 ta dùng thêm vài phép toán trên bit của bài 20, còn ý tưởng “chia bài toán làm ba khúc” chính là chia để trị ở bài 24.

Trò chơi 1Tháp Hà Nội Trò chơi 2Mê cung Trò chơi 3Sudoku Trò chơi 4Game 2048 Trò chơi 5Cờ caro

Trong bài này bạn sẽ học: luật chơi và chơi thử tháp Hà Nội ngay trên trang (có máy gợi ý, máy giải từng nước); cách nghĩ đệ quy “cứ tin là đã biết chuyển $n - 1$ đĩa”; hàm hanoi(n, nguồn, đích, trung gian), cây đệ quy và ngăn xếp lời gọi; vì sao cần đúng $2^n - 1$ nước và chứng minh không thể ít hơn; tìm nước đi thứ $k$ và trạng thái sau $k$ nước trong $O(n)$ bằng bit, không cần liệt kê; các biến thể: lời giải không đệ quy, chỉ được chuyển giữa cột kề nhau, tháp 4 cột (Frame–Stewart). Có khung chơi thử, 2 mô phỏng từng bước, 2 khung chạy tay và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Luật chơi, chơi thử Phần 2Tư duy đệ quy Phần 3Vì sao 2ⁿ − 1 nước Phần 4Nước đi thứ k Phần 5Các biến thể Bài tập8 bài + gợi ý

Phần 1Luật chơi và chơi thử

Có ba cột A, B, C. Ban đầu cột A có $n$ đĩa, đánh số $1, 2, \ldots, n$ từ nhỏ tới lớn, đĩa to nằm dưới. Nhiệm vụ: chuyển cả chồng đĩa sang cột C, tuân thủ ba luật:

Mỗi nước chỉ được chuyển một đĩa.
Chỉ được lấy đĩa trên cùng của một cột và đặt lên trên cùng của cột khác.
Không bao giờ được đặt đĩa lớn lên trên đĩa nhỏ hơn nó.

Hình 1. Bàn chơi 4 đĩa. Cột B không phải nơi cần tới nhưng không thể thiếu: nó là chỗ “gửi tạm” đĩa. Bên phải: đặt đĩa nhỏ lên đĩa lớn thì được, ngược lại thì cấm.

Đọc luật thì dễ, chơi mới thấy khó. Em hãy tự chơi trong khung dưới đây: bấm vào một cột để nhấc đĩa trên cùng (đĩa bay lên, viền cam), bấm vào cột khác để đặt. Bắt đầu với 3 đĩa, cố gắng xong trong 7 nước, rồi nâng lên 4, 5 đĩa. Khi bí, bấm 💡 Máy gợi ý; muốn xem máy giải trọn vẹn thì bấm Tiếp ▶ hoặc ▶ Tự chạy.

MÔ PHỎNGCHƠI THỬ: Tháp Hà Nội ngay trên trangBấm một cột để nhấc đĩa trên cùng, bấm cột khác để đặt xuống. Các nút ◀ ▶ bên dưới phát lại lời giải của máy.

Số đĩa

đĩa đang nhấc / cột đang chọnnước máy gợi ý

Nếu em đã chơi vài ván, chắc em đã nhận ra số nước ít nhất tăng rất nhanh khi thêm đĩa. Bảng dưới ghi lại lời giải tốt nhất với $n$ nhỏ:

$n$	Số nước ít nhất	Lời giải (đĩa: từ → tới)
1	1	1: A→C
2	3	1: A→B, 2: A→C, 1: B→C
3	7	1: A→C, 2: A→B, 1: C→B, 3: A→C, 1: B→A, 2: B→C, 1: A→C
4	15	7 nước đưa 3 đĩa A→B, 4: A→C, 7 nước đưa 3 đĩa B→C

Bảng 1. Lời giải tối ưu với $n = 1 \ldots 4$. Nhìn dòng $n = 3$: ba nước tím chính là lời giải 2 đĩa (chỉ khác là đích là B), nước giữa đưa đĩa to nhất sang C, ba nước xanh lại là lời giải 2 đĩa (từ B sang C).

Quan sát dòng $n = 3$ là chìa khoá của cả bài: lời giải 3 đĩa được ghép từ hai lời giải 2 đĩa và một nước ở giữa. Lời giải 4 đĩa cũng ghép từ hai lời giải 3 đĩa. Một bài toán chứa bên trong nó chính bài toán ấy nhưng nhỏ hơn: đó là dấu hiệu nhận biết đệ quy.

Mẹo chơi tay không cần nhớ gì

Có một quy tắc rất gọn để chơi tay mà luôn tối ưu: các nước lẻ (1, 3, 5, …) luôn là đĩa 1, và đĩa 1 luôn đi vòng theo cùng một chiều: A → C → B → A nếu $n$ lẻ, A → B → C → A nếu $n$ chẵn. Các nước chẵn: không đụng vào đĩa 1, khi đó chỉ có đúng một nước hợp lệ giữa hai cột còn lại. Em thử áp dụng vào khung chơi ở trên với 5 đĩa xem, rồi ở Phần 5 mình sẽ giải thích vì sao nó đúng.

Phần 2Tư duy đệ quy: chỉ cần lo cho đĩa to nhất

Đừng cố hình dung cả $2^n - 1$ nước. Hãy đặt một câu hỏi duy nhất: đĩa $n$ (to nhất) rời cột A lúc nào? Lúc nó đi từ A sang C thì:

trên đĩa $n$ không có đĩa nào (chỉ được lấy đĩa trên cùng);
cột C phải trống, vì mọi đĩa khác đều nhỏ hơn đĩa $n$, không được nằm dưới nó.

Vậy $n - 1$ đĩa còn lại bắt buộc phải đang nằm gọn ở cột B. Từ đó lời giải tự hiện ra, gồm ba bước:

Bước 1: chuyển $n - 1$ đĩa trên cùng từ A sang B (dùng C làm trung gian).
Bước 2: chuyển đĩa $n$ từ A sang C: đúng 1 nước.
Bước 3: chuyển $n - 1$ đĩa từ B sang C, chồng lên đĩa $n$ (dùng A làm trung gian).

Bước 1 và bước 3 là đúng bài toán tháp Hà Nội, chỉ là với $n - 1$ đĩa và đổi vai các cột. Có một điều tinh tế: trong lúc $n - 1$ đĩa nhỏ di chuyển, đĩa $n$ nằm dưới đáy và to hơn tất cả, nên với chúng nó giống như mặt đất, không cản trở gì. Vì thế ta yên tâm giao bước 1 và bước 3 cho lời gọi đệ quy.

Hình 2. Ba bước của lời giải đệ quy. Khối tím đại diện cho cả $n - 1$ đĩa nhỏ: ta không cần biết bên trong nó chuyển thế nào, chỉ cần tin hàm đệ quy làm đúng.

Khuôn mẫu: niềm tin đệ quy

Viết một hàm đệ quy chỉ cần trả lời ba câu, không cần tưởng tượng máy chạy thế nào:

void hanoi(int n, char a, char c, char b){   // n đĩa: a -> c, trung gian b
    if(n == 0) return;          // 1. trường hợp cơ sở: không có đĩa thì không làm gì
    hanoi(n - 1, a, b, c);      // 2. TIN rằng hàm đã đúng với n - 1 đĩa...
    chuyen(n, a, c);            // 3. ...và dùng nó để giải bài n đĩa
    hanoi(n - 1, b, c, a);
}

Hàm đúng với $n = 0$; nếu đúng với $n - 1$ thì theo lập luận ở trên nó đúng với $n$. Đó chính là quy nạp toán học, nên hàm đúng với mọi $n$.

Chương trình đầy đủ: đọc $n$, in từng nước dạng đĩa: từ -> tới và cuối cùng in tổng số nước. Ở bản C++ em để ý thứ tự tham số (n, a, c, b): nguồn, đích, rồi mới tới trung gian. Bước 1 đổi vai thành (a, b, c) vì đích tạm là B, bước 3 đổi thành (b, c, a) vì nguồn mới là B.

Xem code C++ / Python: tháp hà nội bằng đệ quy (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int cnt = 0;

// chuyển n đĩa trên cùng từ cột a sang cột c, dùng cột b làm trung gian
void hanoi(int n, char a, char c, char b){
    if(n == 0) return;                 // không còn đĩa nào: không làm gì
    hanoi(n - 1, a, b, c);             // bước 1: dọn n - 1 đĩa nhỏ sang b
    cnt++;                             // bước 2: chuyển đĩa n từ a sang c
    cout << n << ": " << a << " -> " << c << "\n";
    hanoi(n - 1, b, c, a);             // bước 3: đưa n - 1 đĩa từ b lên c
}

int main(){
    int n;
    cin >> n;
    hanoi(n, 'A', 'C', 'B');
    cout << "Tong so nuoc: " << cnt << "\n";
    return 0;
}

import sys

out = []

def hanoi(n, a, c, b):
    """Chuyển n đĩa trên cùng từ cột a sang cột c, dùng b làm trung gian."""
    if n == 0:                       # không còn đĩa nào: không làm gì
        return
    hanoi(n - 1, a, b, c)            # bước 1: dọn n - 1 đĩa nhỏ sang b
    out.append(f"{n}: {a} -> {c}")   # bước 2: chuyển đĩa n từ a sang c
    hanoi(n - 1, b, c, a)            # bước 3: đưa n - 1 đĩa từ b lên c

n = int(sys.stdin.readline())
hanoi(n, 'A', 'C', 'B')
out.append(f"Tong so nuoc: {len(out)}")
print('\n'.join(out))

Bây giờ em chạy tay từng dòng để thấy máy tính thực sự làm gì. Để ý cột “Độ sâu đệ quy”: lời gọi nào chưa xong thì tạm dừng, chờ lời gọi con trả về rồi mới chạy tiếp đúng dòng đã dừng.

C++▶ Chạy tay từng dòng codehanoi(n, a, c, b): dọn n − 1 đĩa sang b, chuyển đĩa n sang c, rồi đưa n − 1 đĩa từ b lên c (ô đỏ: đĩa vừa chuyển).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int cnt = 0;

6void hanoi(int n, char a, char c, char b){

7 if(n == 0) return;

8 hanoi(n - 1, a, b, c);

9 cnt++;

10 cout << n << ": " << a << " -> " << c << "\n";

11 hanoi(n - 1, b, c, a);

12}

14int main(){

15 int n;

16 cin >> n;

17 hanoi(n, 'A', 'C', 'B');

18 cout << "Tong so nuoc: " << cnt << "\n";

19 return 0;

20}

Khung chạy tay đi từng dòng nên hơi dài. Mô phỏng dưới đây nhìn từ trên cao: mỗi lời gọi là một ô trong cây đệ quy, và bên cạnh là ngăn xếp lời gọi, nơi máy tính cất các lời gọi đang tạm dừng. Em sẽ thấy thứ tự các nước đi chính là thứ tự đọc cây từ trái sang phải, và ngăn xếp không bao giờ cao quá $n$ tầng:

MÔ PHỎNGCây đệ quy và ngăn xếp lời gọi của hanoi(n, A, C, B)Nhập số đĩa n (1 … 4). Theo dõi lời gọi nào đang chạy, lời gọi nào đang tạm dừng chờ trong ngăn xếp.

Số đĩa n

chưa gọi tớiđang chạytạm dừng trong ngăn xếpđã xong

Ba lỗi hay gặp khi viết hàm đệ quy

1. Quên trường hợp cơ sở if(n == 0) return;: hàm gọi mãi $n = -1, -2, \ldots$ tới khi tràn ngăn xếp (lỗi stack overflow, chương trình bị dừng đột ngột).
2. Truyền nhầm vai các cột: viết hanoi(n - 1, a, c, b) ở bước 1 thì $n - 1$ đĩa chạy thẳng sang C, đĩa $n$ không còn chỗ đặt. Hãy luôn tự hỏi: ở bước này, nguồn, đích, trung gian là cột nào?
3. Dùng biến toàn cục làm “cột hiện tại”: mỗi lời gọi phải có bộ tham số riêng. Tham số truyền theo giá trị nên khi lời gọi con trả về, các biến a, b, c của lời gọi cha vẫn nguyên như cũ.

Phần 3Vì sao cần đúng $2^n - 1$ nước?

Gọi $T(n)$ là số nước mà hàm hanoi thực hiện với $n$ đĩa. Bước 1 và bước 3 mỗi bước tốn $T(n - 1)$ nước, bước 2 tốn 1 nước, nên:

$T(0) = 0, \qquad T(n) = 2\,T(n - 1) + 1.$

Tính thử: $T(1) = 1$, $T(2) = 3$, $T(3) = 7$, $T(4) = 15$, $T(5) = 31$… Thấy quen không? Mỗi số đều kém một lũy thừa của 2 đúng 1 đơn vị. Mẹo chứng minh: cộng 1 vào hai vế, $T(n) + 1 = 2\,\big(T(n - 1) + 1\big)$. Vậy dãy $T(n) + 1$ cứ thế nhân đôi, bắt đầu từ $T(0) + 1 = 1$, nên $T(n) + 1 = 2^n$, tức là

$T(n) = 2^n - 1.$

Một cách nhìn khác: đĩa $n$ đi 1 lần, đĩa $n - 1$ đi 2 lần (một lần trong bước 1, một lần trong bước 3), đĩa $n - 2$ đi 4 lần… đĩa $d$ đi đúng $2^{n - d}$ lần. Riêng đĩa 1 đi $2^{n-1}$ lần, chiếm một nửa số nước (khớp với mẹo “nước lẻ là đĩa 1” ở Phần 1). Cộng lại: $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$.

Số đĩa $n$	Số nước $2^n - 1$	Nếu mỗi giây một nước
3	7	7 giây
10	1 023	khoảng 17 phút
20	1 048 575	khoảng 12 ngày
30	1 073 741 823	khoảng 34 năm
40	1 099 511 627 775	khoảng 35 nghìn năm
64	18 446 744 073 709 551 615	khoảng 585 tỉ năm

Bảng 2. Số nước tăng gấp đôi mỗi khi thêm một đĩa. Đây là ví dụ điển hình của độ phức tạp hàm mũ $O(2^n)$: chương trình in hết các nước chỉ chạy nổi khi $n$ khoảng 25 trở xuống.

Có cách nào nhanh hơn không? Không! Gọi $M(n)$ là số nước ít nhất có thể (với bất kỳ cách chơi nào). Ta chứng minh $M(n) \ge 2\,M(n - 1) + 1$:

Đĩa $n$ phải di chuyển ít nhất một lần. Xét lần đầu tiên nó rời A: như đã lập luận ở Phần 2, lúc đó $n - 1$ đĩa nhỏ nằm gọn ở một cột khác. Đưa được chúng từ A sang đó là cả một ván tháp Hà Nội $n - 1$ đĩa, tốn ít nhất $M(n - 1)$ nước.
Xét lần cuối cùng đĩa $n$ đặt xuống C: ngay trước nước đó, $n - 1$ đĩa nhỏ cũng nằm gọn ở cột thứ ba. Sau nước đó còn phải đưa chúng lên C, lại ít nhất $M(n - 1)$ nước.
Hai giai đoạn trên không chồng lên nhau, và còn ít nhất 1 nước của chính đĩa $n$ ở giữa.

Vậy $M(n) \ge 2\,M(n - 1) + 1$ với $M(0) = 0$, suy ra $M(n) \ge 2^n - 1$. Hàm hanoi đạt đúng $2^n - 1$, nên nó tối ưu. Lập luận còn cho thấy: lời giải tối ưu là duy nhất, trong đó đĩa $n$ chỉ đi đúng một lần. Khung chơi thử ở Phần 1 kiểm tra em có đạt con số này không.

Xem code C++ / Python: đếm số nước với n tới 64 (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;                                   // 0 <= n <= 64
    cin >> n;
    unsigned long long T = 0;                // T(0) = 0
    for(int i = 1; i <= n; i++) T = 2 * T + 1;   // T(i) = 2 T(i - 1) + 1
    cout << T;                               // T(64) = 2^64 - 1 vẫn vừa unsigned long long
    return 0;
}

n = int(input())
T = 0                      # T(0) = 0
for i in range(1, n + 1):
    T = 2 * T + 1          # T(i) = 2 T(i - 1) + 1
print(T)                   # bằng 2**n - 1, Python không lo tràn số

Cẩn thận tràn số

$2^{64} - 1 = 18\,446\,744\,073\,709\,551\,615$ vượt quá long long (tối đa $2^{63} - 1$) nhưng vừa khít unsigned long long. Còn viết 1 << n thì số 1 là int, sai ngay từ $n = 31$; phải viết 1LL << n (đúng tới $n = 62$). Khi $n$ lớn tới $10^{18}$ thì đề sẽ hỏi số nước chia lấy dư cho $10^9 + 7$: dùng lũy thừa nhanh (bài tập 2).

Phần 4Nước đi thứ $k$ và trạng thái sau $k$ nước

Câu hỏi kiểu thi: “Cho $n \le 60$ và $k \le 2^n - 1$. Ở nước thứ $k$ của lời giải tối ưu, đĩa nào đi, từ cột nào sang cột nào?” Với $n = 60$ thì $k$ có thể tới $10^{18}$, liệt kê từng nước tới khi gặp nước thứ $k$ là không tưởng. Nhưng em nhớ lại ba khúc của lời giải $n$ đĩa:

Khúc	Nước thứ	Việc đang làm
Bước 1	$1 \ldots 2^{n-1} - 1$	$n - 1$ đĩa đi từ A sang B (trung gian C)
Bước 2	$2^{n-1}$	đĩa $n$ đi từ A sang C
Bước 3	$2^{n-1} + 1 \ldots 2^n - 1$	$n - 1$ đĩa đi từ B sang C (trung gian A)

Bảng 3. Nước thứ $k$ rơi vào khúc nào chỉ cần so sánh $k$ với $\text{half} = 2^{n-1}$.

Đặt $\text{half} = 2^{n-1}$:

$k = \text{half}$: xong, đó là nước của đĩa $n$, đi từ nguồn sang đích.
$k < \text{half}$: đó là nước thứ $k$ của bài toán $n - 1$ đĩa đi từ A sang B. Đích đổi thành B, trung gian đổi thành C.
$k > \text{half}$: bỏ qua $\text{half}$ nước đầu, đó là nước thứ $k - \text{half}$ của bài toán $n - 1$ đĩa đi từ B sang C. Nguồn đổi thành B, trung gian đổi thành A.

Mỗi bước bớt một đĩa nên chỉ mất $O(n)$ bước. Đây là chia để trị “đi một nhánh”, giống tìm kiếm nhị phân: không cần giải cả hai bài con, chỉ đi vào bài con chứa đáp án. Ví dụ $n = 4$, $k = 6$: $6 < 8$ nên xét 3 đĩa A→B; $6 > 4$ nên còn $k = 2$, xét 2 đĩa C→B; $2 = 2$ nên đáp án là đĩa 2 từ C sang B. Em có thể kiểm tra bằng khung chơi thử: chọn 4 đĩa, bấm Tiếp 6 lần.

C++▶ Chạy tay từng dòng codeTìm nước đi thứ k: mỗi vòng so sánh k với half = 2^(d−1) để biết đi vào khúc đầu hay khúc cuối, rồi đổi vai các cột.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int main(){

5 int n;

6 long long k;

7 cin >> n >> k;

8 char a = 'A', c = 'C', b = 'B';

9 for(int d = n; d >= 1; d--){

10 long long half = 1LL << (d - 1);

11 if(k == half){

12 cout << d << ": " << a << " -> " << c;

13 return 0;

14 }

15 if(k < half) swap(c, b);

16 else { k -= half; swap(a, b); }

17 }

18 return 0;

19}

Xem code C++ / Python: tìm nước đi thứ k trong o(n) (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    long long k;                         // 1 <= k <= 2^n - 1, n <= 60
    cin >> n >> k;
    char a = 'A', c = 'C', b = 'B';      // bài toán: n đĩa từ a sang c, trung gian b
    for(int d = n; d >= 1; d--){
        long long half = 1LL << (d - 1); // nước thứ half là nước của đĩa d
        if(k == half){
            cout << d << ": " << a << " -> " << c;
            return 0;
        }
        if(k < half) swap(c, b);         // khúc đầu: d - 1 đĩa đi từ a sang b
        else { k -= half; swap(a, b); }  // khúc cuối: d - 1 đĩa đi từ b sang c
    }
    return 0;
}

n, k = map(int, input().split())
a, c, b = 'A', 'C', 'B'            # bài toán: n đĩa từ a sang c, trung gian b
for d in range(n, 0, -1):
    half = 1 << (d - 1)            # nước thứ half là nước của đĩa d
    if k == half:
        print(f"{d}: {a} -> {c}")
        break
    if k < half:                   # khúc đầu: d - 1 đĩa đi từ a sang b
        c, b = b, c
    else:                          # khúc cuối: d - 1 đĩa đi từ b sang c
        k -= half
        a, b = b, a

Nhìn bằng con mắt nhị phân. Vì $k < 2^d$ ở mọi vòng, phép so sánh $k$ với $2^{d-1}$ thực chất là xem bit thứ $d - 1$ của $k$ bằng 0 hay 1, và “trừ đi half” là xoá bit đó. Vòng lặp dừng khi phần còn lại của $k$ đúng bằng một lũy thừa của 2, tức là khi chỉ còn bit 1 thấp nhất. Hệ quả rất đẹp:

đĩa đi ở nước thứ $k$ = (số chữ số 0 ở cuối $k$ trong hệ nhị phân) + 1.

Ví dụ $k = 6 = 110_2$ có 1 chữ số 0 ở cuối, nên nước 6 là của đĩa 2. Mọi nước lẻ ($k$ tận cùng bằng 1) đều là đĩa 1. Trong C++ có sẵn __builtin_ctzll(k) đếm số bit 0 ở cuối.

Trạng thái sau $k$ nước. Cùng cách đi xuống đó trả lời được câu hỏi: sau $k$ nước, mỗi đĩa nằm ở cột nào? Xét đĩa $d$ trong bài toán con hiện tại: nếu $k < 2^{d-1}$ thì đĩa $d$ chưa đi, vẫn ở cột nguồn; ngược lại nó đã sang cột đích. Mỗi đĩa quyết định bằng đúng một bit, tổng cộng $O(n)$. Em xem mô phỏng, đổi $n$ và $k$ tuỳ ý (thử $k = 0$ và $k = 2^n - 1$ nữa nhé):

MÔ PHỎNGTrạng thái sau k nước: mỗi đĩa chỉ cần nhìn một bit của kNhập n (1 … 10) và k (0 … 2^n − 1). Đi từ đĩa lớn nhất xuống, mỗi bước quyết định xong vị trí một đĩa.

Số đĩa nk

bit / đĩa đang xétđĩa đi ở nước thứ kchưa biết vị trí

Công thức “ảo thuật” chỉ dùng phép toán bit

Đánh số cột 0, 1, 2. Với $n$ lẻ, nước thứ $k$ của lời giải chuyển tháp từ cột 0 sang cột 2 là: từ cột (k & (k - 1)) % 3 sang cột ((k | (k - 1)) + 1) % 3. Với $n$ chẵn, công thức đó đưa tháp sang cột 1, nên em chỉ cần đổi tên cột 1 và cột 2. Thử $k = 6$, $n = 4$: 6 & 5 = 4, $4 \bmod 3 = 1$; 6 | 5 = 7, $8 \bmod 3 = 2$; đổi tên 1 ↔ 2 thành “từ cột 2 sang cột 1”, tức C → B, khớp với ví dụ trên. Công thức này không cần nhớ để đi thi, nhưng rất vui để tự kiểm chứng.

Phần 5Các biến thể của tháp Hà Nội

5.1. Lời giải không dùng đệ quy. Mẹo chơi tay ở Phần 1 chính là một thuật toán vòng lặp: nước lẻ là đĩa 1 đi vòng theo một chiều, nước chẵn là nước hợp lệ duy nhất không đụng đĩa 1. Vì sao đĩa 1 luôn đi cùng chiều? Theo Phần 3, đĩa $d$ chỉ đi ở các nước $k$ có đúng $d - 1$ bit 0 ở cuối, và mỗi lần đi nó luôn bước theo cùng một chiều vòng tròn: chiều A→C→B nếu $n - d$ chẵn, chiều A→B→C nếu $n - d$ lẻ (em tự chứng minh bằng quy nạp theo ba bước của Phần 2 nhé). Kết hợp với công thức bit ở trên, ta in được cả lời giải chỉ bằng một vòng for, không cần đệ quy, cho kết quả giống hệt chương trình ở Phần 2:

Xem code C++ / Python: lời giải không đệ quy bằng phép toán bit (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    char name[3] = {'A', 'B', 'C'};
    if(n % 2 == 0) swap(name[1], name[2]);   // n chẵn: công thức đưa tháp về cột 1, nên đổi tên B, C
    long long total = (1LL << n) - 1;
    for(long long k = 1; k <= total; k++){
        int d = __builtin_ctzll(k) + 1;               // đĩa đi ở nước k
        int from = (k & (k - 1)) % 3;
        int to = ((k | (k - 1)) + 1) % 3;
        cout << d << ": " << name[from] << " -> " << name[to] << "\n";
    }
    cout << "Tong so nuoc: " << total << "\n";
    return 0;
}

import sys

n = int(sys.stdin.readline())
name = ['A', 'B', 'C']
if n % 2 == 0:                          # n chẵn: công thức đưa tháp về cột 1, nên đổi tên B, C
    name[1], name[2] = name[2], name[1]
total = (1 << n) - 1
out = []
for k in range(1, total + 1):
    d = (k & -k).bit_length()           # đĩa đi ở nước k
    fr = (k & (k - 1)) % 3
    to = ((k | (k - 1)) + 1) % 3
    out.append(f"{d}: {name[fr]} -> {name[to]}")
out.append(f"Tong so nuoc: {total}")
print('\n'.join(out))

5.2. Chỉ được chuyển giữa hai cột kề nhau. Ba cột xếp thành hàng A, B, C và luật thêm: cấm chuyển thẳng giữa A và C, mọi đĩa phải ghé qua B.

Hình 3. Biến thể cột kề nhau: đĩa muốn từ A sang C bắt buộc phải dừng ở B.

Vẫn hỏi câu cũ: đĩa $n$ phải đi A→B rồi B→C. Lúc đĩa $n$ đi A→B thì $n - 1$ đĩa nhỏ phải ở C (A và B đều bận); lúc nó đi B→C thì $n - 1$ đĩa nhỏ phải ở A. Vậy lời giải gồm năm khúc:

Khúc	Việc làm	Số nước
1	$n - 1$ đĩa A → C (đệ quy, cùng luật cột kề)	$T(n - 1)$
2	đĩa $n$: A → B	1
3	$n - 1$ đĩa C → A (đệ quy)	$T(n - 1)$
4	đĩa $n$: B → C	1
5	$n - 1$ đĩa A → C (đệ quy)	$T(n - 1)$

Bảng 4. $T(n) = 3\,T(n - 1) + 2$, $T(0) = 0$. Cộng 1 hai vế: $T(n) + 1 = 3\,(T(n - 1) + 1)$, nên $T(n) = 3^n - 1$.

Điều bất ngờ: tháp $n$ đĩa có đúng $3^n$ trạng thái hợp lệ (mỗi đĩa chọn 1 trong 3 cột, thứ tự trong cột thì đã bị luật cố định), và lời giải cột kề dùng $3^n - 1$ nước, tức là nó đi qua mọi trạng thái, mỗi trạng thái đúng một lần! Code đếm số nước chỉ là một vòng lặp; bài tập 5 sẽ yêu cầu in cả các nước đi.

Xem code C++ / Python: đếm số nước khi chỉ được chuyển giữa cột kề nhau (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;                                    // n <= 39 để 3^n - 1 vừa long long
    cin >> n;
    long long T = 0;                          // T(0) = 0
    for(int i = 1; i <= n; i++) T = 3 * T + 2;    // T(i) = 3 T(i - 1) + 2
    cout << T;                                // bằng 3^n - 1
    return 0;
}

n = int(input())
T = 0                       # T(0) = 0
for i in range(1, n + 1):
    T = 3 * T + 2           # T(i) = 3 T(i - 1) + 2
print(T)                    # bằng 3**n - 1

5.3. Tháp Hà Nội 4 cột. Có thêm một cột phụ thì nhanh hơn bao nhiêu? Cách làm do Frame và Stewart đề xuất năm 1941: chọn một số $k$, rồi

chuyển $k$ đĩa trên cùng sang một cột phụ, được dùng cả 4 cột: $F(k)$ nước;
chuyển $n - k$ đĩa còn lại sang đích, lúc này chỉ còn 3 cột dùng được (cột đang giữ $k$ đĩa nhỏ thì không đặt đĩa to lên): $2^{n-k} - 1$ nước;
chuyển $k$ đĩa từ cột phụ lên đích bằng 4 cột: $F(k)$ nước.

Thử mọi $k$ và lấy tốt nhất: $F(n) = \min\limits_{0 \le k < n} \big(2F(k) + 2^{n-k} - 1\big)$, với $F(0) = 0$. Đây là một công thức quy hoạch động (xem bài 19), tính trong $O(n^2)$.

$n$	1	2	3	4	5	6	7	8	9	10
3 cột: $2^n - 1$	1	3	7	15	31	63	127	255	511	1023
4 cột: $F(n)$	1	3	5	9	13	17	25	33	41	49

Bảng 5. Thêm một cột, 10 đĩa chỉ cần 49 nước thay vì 1023. Năm 2014, Thierry Bousch đã chứng minh cách Frame–Stewart là tối ưu với 4 cột; với 5 cột trở lên đây vẫn là bài toán mở.

Dấu hiệu bài toán “kiểu tháp Hà Nội” trong đề thi

Đề có một cấu trúc tự đồng dạng (bài lớn chứa hai, ba bản sao của bài nhỏ hơn một bậc), đáp án lớn như $2^n$, $3^n$ và hỏi phần tử thứ $k$ hoặc trạng thái sau $k$ bước. Cách giải chung: (1) viết công thức truy hồi cho độ dài mỗi khúc; (2) đi từ bài lớn xuống, mỗi lần chọn đúng khúc chứa $k$ như Phần 4. Các bài “Xâu Fibonacci”, “Tìm ký tự thứ K” trong danh sách luyện tập dưới đây giải đúng theo khuôn này.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

Xem toàn bộ bài cùng chủ đề: nhãn Đệ quy.

Bài tậpLuyện tập với tháp Hà Nội

Bài 1In các nước điDễ

Tháp có $n$ đĩa ($1 \le n \le 16$) ở cột 1, cần chuyển sang cột 3 với số nước ít nhất. Dòng đầu in số nước $m$, sau đó $m$ dòng, mỗi dòng hai số $x\ y$: lấy đĩa trên cùng của cột $x$ đặt lên cột $y$.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đúng hàm hanoi ở Phần 2, chỉ đổi tên cột thành số và không in số hiệu đĩa. Số nước là $2^n - 1$ nên in được ngay ở dòng đầu (C++: (1 << n) - 1). Với $n = 16$ có 65 535 dòng, nên gom kết quả vào một xâu hoặc danh sách rồi in một lần cho nhanh.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

string out;

void hanoi(int n, int a, int c, int b){
    if(n == 0) return;
    hanoi(n - 1, a, b, c);
    out += char('0' + a); out += ' '; out += char('0' + c); out += '\n';
    hanoi(n - 1, b, c, a);
}

int main(){
    int n;
    cin >> n;
    hanoi(n, 1, 3, 2);
    cout << (1 << n) - 1 << "\n" << out;
    return 0;
}

import sys

res = []

def hanoi(n, a, c, b):
    if n == 0:
        return
    hanoi(n - 1, a, b, c)
    res.append(f"{a} {c}")
    hanoi(n - 1, b, c, a)

n = int(sys.stdin.readline())
hanoi(n, 1, 3, 2)
print(len(res))
print('\n'.join(res))

Bài 2Đếm số nước theo moduloDễ

Cho $n$ ($0 \le n \le 10^{18}$). In số nước ít nhất để chuyển tháp $n$ đĩa, lấy phần dư khi chia cho $10^9 + 7$.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đáp án là $2^n - 1$. Tính $2^n \bmod (10^9 + 7)$ bằng lũy thừa nhanh (chia để trị trên số mũ, đã gặp ở bài tập 2 của bài 24), rồi trừ 1. Chú ý: nếu $2^n \bmod p$ bằng 0 thì trừ 1 ra số âm, nên viết (x - 1 + MOD) % MOD cho an toàn.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long power(long long a, long long b){
    long long res = 1;
    a %= MOD;
    while(b > 0){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main(){
    long long n;
    cin >> n;
    cout << (power(2, n) - 1 + MOD) % MOD;
    return 0;
}

MOD = 10**9 + 7
n = int(input())
print((pow(2, n, MOD) - 1) % MOD)

Bài 3Đĩa d đã đi mấy lần?Trung bình

Xét lời giải tối ưu của tháp $n$ đĩa ($1 \le n \le 60$). Có $q$ câu hỏi ($q \le 10^5$), mỗi câu gồm $d, k$ ($1 \le d \le n$, $0 \le k \le 2^n - 1$): trong $k$ nước đầu tiên, đĩa $d$ đã di chuyển bao nhiêu lần? Dòng đầu là $n, q$, mỗi dòng sau là một câu hỏi; in mỗi đáp án trên một dòng.

Input

Output

4
2
0

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Theo Phần 4, đĩa $d$ đi ở nước $k$ khi $k$ có đúng $d - 1$ bit 0 ở cuối, tức là $k$ có dạng $2^{d-1}, 3 \cdot 2^{d-1}, 5 \cdot 2^{d-1}, \ldots$ (bội lẻ của $2^{d-1}$). Số bội lẻ của $2^{d-1}$ không vượt quá $k$ là $\left\lfloor \dfrac{k + 2^{d-1}}{2^d} \right\rfloor$. Với mẫu: đĩa 1 đi ở các nước 1, 3, 5, 7 (4 lần); đĩa 2 ở nước 2, 6 (2 lần); đĩa 3 ở nước 4, nên trong 3 nước đầu nó chưa đi. Dùng long long: $k + 2^{d-1}$ có thể tới khoảng $1{,}7 \cdot 10^{18}$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    while(q--){
        int d;
        long long k;
        cin >> d >> k;
        long long h = 1LL << (d - 1);
        cout << (k + h) / (2 * h) << "\n";    // số bội lẻ của 2^(d-1) không vượt quá k
    }
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
out = []
for i in range(q):
    d, k = int(data[2 + 2 * i]), int(data[3 + 2 * i])
    h = 1 << (d - 1)
    out.append((k + h) // (2 * h))           # số bội lẻ của 2^(d-1) không vượt quá k
print('\n'.join(map(str, out)))

Bài 4Trạng thái sau k nướcTrung bình

Tháp $n$ đĩa ($1 \le n \le 60$) chuyển từ cột 1 sang cột 3 theo lời giải tối ưu. Cho $k$ ($0 \le k \le 2^n - 1$), in $n$ số $p_1, p_2, \ldots, p_n$: $p_i$ là cột chứa đĩa $i$ sau $k$ nước đầu tiên (đĩa 1 nhỏ nhất).

Input

4 6

Output

1 2 2 1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Làm đúng như mô phỏng thứ ba ở Phần 4. Giữ bộ ba (nguồn $a$, đích $c$, trung gian $b$) = (1, 3, 2), đi $d$ từ $n$ về 1: nếu $k < 2^{d-1}$ thì $p_d = a$ và đổi chỗ $c, b$; ngược lại $p_d = c$, $k$ bớt đi $2^{d-1}$ và đổi chỗ $a, b$. Với mẫu: sau 6 nước (1: A→B, 2: A→C, 1: B→C, 3: A→B, 1: C→A, 2: C→B) thì đĩa 1 ở A, đĩa 2, 3 ở B, đĩa 4 vẫn ở A.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    long long k;
    cin >> n >> k;
    vector<int> p(n + 1);
    int a = 1, c = 3, b = 2;
    for(int d = n; d >= 1; d--){
        long long half = 1LL << (d - 1);
        if(k < half){ p[d] = a; swap(c, b); }          // đĩa d chưa đi
        else { p[d] = c; k -= half; swap(a, b); }      // đĩa d đã sang đích
    }
    for(int i = 1; i <= n; i++) cout << p[i] << " ";
    return 0;
}

n, k = map(int, input().split())
p = [0] * (n + 1)
a, c, b = 1, 3, 2
for d in range(n, 0, -1):
    half = 1 << (d - 1)
    if k < half:                 # đĩa d chưa đi
        p[d] = a
        c, b = b, c
    else:                        # đĩa d đã sang đích
        p[d] = c
        k -= half
        a, b = b, a
print(*p[1:])

Bài 5Chỉ được chuyển giữa hai cột kề nhauTrung bình

Ba cột 1, 2, 3 xếp thành hàng. Tháp $n$ đĩa ($1 \le n \le 8$) ở cột 1 cần chuyển sang cột 3, nhưng mỗi nước chỉ được chuyển giữa cột 1 và 2, hoặc giữa cột 2 và 3. In số nước ít nhất $m$, sau đó $m$ dòng, mỗi dòng hai số $x\ y$ là một nước đi.

Input

Output

2
1 2
2 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dùng năm khúc ở Phần 5.2. Viết hàm go(n, a, c) chuyển $n$ đĩa giữa hai cột ngoài $a$ và $c$ (một cái là 1, cái kia là 3, cột 2 luôn ở giữa): go(n-1, a, c), đĩa $n$ từ $a$ sang 2, go(n-1, c, a), đĩa $n$ từ 2 sang $c$, go(n-1, a, c). Số nước là $3^n - 1$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

string out;

void mv(int x, int y){ out += char('0' + x); out += ' '; out += char('0' + y); out += '\n'; }

void go(int n, int a, int c){        // a, c là hai cột ngoài, cột 2 ở giữa
    if(n == 0) return;
    go(n - 1, a, c);
    mv(a, 2);                        // đĩa n: a -> 2
    go(n - 1, c, a);
    mv(2, c);                        // đĩa n: 2 -> c
    go(n - 1, a, c);
}

int main(){
    int n;
    cin >> n;
    int m = 1;
    for(int i = 0; i < n; i++) m *= 3;
    go(n, 1, 3);
    cout << m - 1 << "\n" << out;
    return 0;
}

import sys

res = []

def go(n, a, c):                     # a, c là hai cột ngoài, cột 2 ở giữa
    if n == 0:
        return
    go(n - 1, a, c)
    res.append(f"{a} 2")             # đĩa n: a -> 2
    go(n - 1, c, a)
    res.append(f"2 {c}")             # đĩa n: 2 -> c
    go(n - 1, a, c)

n = int(sys.stdin.readline())
go(n, 1, 3)
print(len(res))
print('\n'.join(res))

Bài 6Đã đi bao nhiêu nước?Khá

Tháp $n$ đĩa ($1 \le n \le 60$) đang được chuyển từ cột 1 sang cột 3 theo lời giải tối ưu. Bạn nhìn thấy trạng thái hiện tại: $p_1, \ldots, p_n$ ($p_i$ là cột chứa đĩa $i$). Hỏi đã đi bao nhiêu nước? Nếu trạng thái này không bao giờ xuất hiện trong lời giải tối ưu thì in $-1$.

Input

4
1 2 2 1

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Làm ngược bài tập 4. Đi $d$ từ $n$ về 1 với bộ ba (nguồn $a$, đích $c$, trung gian $b$) = (1, 3, 2) và $k = 0$: nếu $p_d = a$ thì đĩa $d$ chưa đi, đổi chỗ $c, b$; nếu $p_d = c$ thì đĩa $d$ đã đi, cộng $2^{d-1}$ vào $k$ và đổi chỗ $a, b$; còn nếu $p_d = b$ thì không thể: trong lời giải tối ưu đĩa $d$ không bao giờ ghé cột trung gian của bài toán con chứa nó, in $-1$. Chẳng hạn với $n = 1$, đĩa 1 nằm ở cột 2 là trạng thái không xuất hiện.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for(int i = 1; i <= n; i++) cin >> p[i];
    int a = 1, c = 3, b = 2;
    long long k = 0;
    for(int d = n; d >= 1; d--){
        if(p[d] == a) swap(c, b);                                 // đĩa d chưa đi
        else if(p[d] == c){ k += 1LL << (d - 1); swap(a, b); }    // đĩa d đã đi
        else { cout << -1; return 0; }                            // nằm ở trung gian: không thể
    }
    cout << k;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
p = [0] + list(map(int, data[1:n + 1]))
a, c, b = 1, 3, 2
k = 0
for d in range(n, 0, -1):
    if p[d] == a:                  # đĩa d chưa đi
        c, b = b, c
    elif p[d] == c:                # đĩa d đã đi
        k += 1 << (d - 1)
        a, b = b, a
    else:                          # nằm ở trung gian: không thể
        k = -1
        break
print(k)

Bài 7Tháp Hà Nội 4 cộtKhá

Có 4 cột và $n$ đĩa ($1 \le n \le 1000$). Theo cách Frame–Stewart ở Phần 5.3, số nước cần là $F(n) = \min\limits_{0 \le k < n} \big(2F(k) + 2^{n-k} - 1\big)$, $F(0) = 0$. Hãy tính $F(n)$ (đảm bảo kết quả nhỏ hơn $10^{18}$).

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Quy hoạch động tính $F(1), F(2), \ldots, F(n)$ theo thứ tự, mỗi giá trị thử mọi $k$: $O(n^2) = 10^6$ phép tính. Cái bẫy là $2^{n-k}$: với $n - k$ lớn thì số này tràn long long. Nhận xét: $F(n) < 10^{18} < 2^{60}$, nên mọi $k$ có $n - k \ge 61$ chắc chắn không tốt hơn, bỏ qua luôn (chỉ thử $k \ge n - 60$). Với $n = 10$, tốt nhất là $k = 6$: $2F(6) + 2^4 - 1 = 2 \cdot 17 + 15 = 49$ (thử $k = 5$ chỉ được $2 \cdot 13 + 31 = 57$).

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

long long F[1005];

int main(){
    int n;
    cin >> n;
    F[0] = 0;
    for(int m = 1; m <= n; m++){
        F[m] = LLONG_MAX;
        for(int k = max(0, m - 60); k < m; k++)          // n - k > 60 thì 2^(n-k) quá lớn, bỏ qua
            F[m] = min(F[m], 2 * F[k] + (1LL << (m - k)) - 1);
    }
    cout << F[n];
    return 0;
}

n = int(input())
F = [0] * (n + 1)
for m in range(1, n + 1):
    F[m] = min(2 * F[k] + (1 << (m - k)) - 1 for k in range(max(0, m - 60), m))
print(F[n])

Bài 8Tháp đĩa hai màuKhá

Tháp có $2n$ đĩa: mỗi kích thước $1, 2, \ldots, n$ có hai đĩa, một trắng một đen. Ban đầu ở cột 1, với mỗi kích thước thì đĩa đen nằm ngay dưới đĩa trắng. Luật như cũ, nhưng hai đĩa cùng kích thước được đặt lên nhau theo thứ tự nào cũng được. Cần chuyển cả tháp sang cột 3 sao cho cuối cùng, với mọi kích thước, đĩa trắng vẫn nằm trên đĩa đen. Cho $n$ ($1 \le n \le 10^{18}$), in số nước ít nhất chia lấy dư cho $10^9 + 7$.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Trước hết, nếu không quan tâm màu thì cứ coi mỗi cặp là một đĩa “dày”, mỗi nước của nó thành 2 nước: $B(n) = 2(2^n - 1)$. Nhưng mỗi lần chuyển như vậy, hai đĩa cùng cỡ bị đảo thứ tự (đĩa trên đi trước nên nằm dưới); chuyển hai lần thì về như cũ. Với $n = 1$: trắng sang 2, đen sang 3, trắng sang 3 là 3 nước. Với $n$ cặp: đưa $n - 1$ cặp trên sang cột 3 ($B(n-1)$, bị đảo), cặp dưới cùng sang cột 2 (2 nước, bị đảo), $n - 1$ cặp về cột 1 ($B(n-1)$, hết đảo), cặp dưới cùng sang cột 3 (2 nước, hết đảo), cuối cùng giải bài toán $n - 1$ cặp có giữ màu từ cột 1 sang cột 3. Vậy $A(n) = A(n - 1) + 2B(n - 1) + 4 = A(n - 1) + 2^{n+1}$, $A(1) = 3$, suy ra $A(n) = 2^{n+2} - 5$ (người ta chứng minh được đây là ít nhất; mình đã kiểm tra bằng duyệt mọi trạng thái với $n \le 4$). Mẫu: $2^4 - 5 = 11$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long power(long long a, long long b){
    long long res = 1;
    a %= MOD;
    while(b > 0){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main(){
    long long n;
    cin >> n;
    cout << ((power(2, n + 2) - 5) % MOD + MOD) % MOD;   // 2^(n+2) - 5
    return 0;
}

MOD = 10**9 + 7
n = int(input())
print((pow(2, n + 2, MOD) - 5) % MOD)    # 2^(n+2) - 5

Trò chơi tiếp theo · Trò chơi 2

Mê cung: tìm đường bằng BFS và DFS

Lạc trong mê cung thì đi thế nào? Chơi thử mê cung ngay trên trang, rồi xem máy tìm đường ngắn nhất bằng BFS và đi thử mọi ngả bằng DFS.

Chơi trò 2 →

← Lộ trình học thuật toán Xem cả series Thuật toán qua trò chơi

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!

Lập Trình Thuật Toán

Trò chơi 1: Tháp Hà Nội trong C++ và Python: tư duy đệ quy, vì sao cần 2^n − 1 nước, tìm nước đi thứ k bằng bit

Lời mở đầu

Phần 1Luật chơi và chơi thử

Phần 2Tư duy đệ quy: chỉ cần lo cho đĩa to nhất

Phần 3Vì sao cần đúng $2^n - 1$ nước?

Phần 4Nước đi thứ $k$ và trạng thái sau $k$ nước

Phần 5Các biến thể của tháp Hà Nội

Bài tậpLuyện tập với tháp Hà Nội

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++