Hiểu bài toán

Bài toán yêu cầu tìm số bước tối thiểu để chuyển N đĩa từ cột A sang cột C, tuân theo luật của trò chơi Tháp Hà Nội: chỉ di chuyển một đĩa mỗi lần và không bao giờ để đĩa nhỏ hơn lên trên đĩa lớn hơn. Với N đĩa, số bước cần thiết là một dãy số quen thuộc (số nhị phân 2^N - 1). Do N có thể lên tới 500, kết quả sẽ rất lớn nên cần in ra số dư khi chia cho 10^9 + 7.

Các cách tiếp cận

Cách Đệ quy cơ bản

#include <bits/stdc++.h>
using namespace std;
long long thn(long long n) 
{
    if (n==1) 
        return 1 ;
    return (2*thn(n-1)%1000000007+1)%1000000007 ;
}
int main() 
{
    long long n ;
    cin >> n ;
    cout << thn(n) ;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này dựa trên công thức truy hồi của bài toán Tháp Hà Nội: T(n) = 2 * T(n-1) + 1. Với T(1) = 1. Hàm thn gọi đệ quy từ N xuống 1, tính toán kết quả dựa trên kết quả của N-1. Tuy nhiên, với N lớn (ví dụ N=500), đệ quy có thể gây tràn bộ nhớ ngăn xếp (Stack Overflow) nếu không được tối ưu hóa Tail Call, và độ phức tạp không gian là O(N) do lưu các lần gọi hàm.

Cách Vòng lặp lũy thừa (Lặp đơn)

#include <bits/stdc++.h>

using namespace std;

long long n, t;
int main()
{
    cin >> n; t = 1;
    for (int i = 1; i <= n; i++){
        t = (t * 2) % 1000000007;
    }
    cout << t - 1;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Phương pháp này dựa trên nhận thấy rằng số bước cần thiết chính là công thức 2^N - 1. Thay vì đệ quy, ta sử dụng một vòng lặp for để nhân liên tục biến t (ban đầu là 1) với 2, N lần. Sau đó trừ đi 1 để in ra kết quả. Phương pháp này an toàn về bộ nhớ (không lo tràn ngăn xếp) và dễ hiểu. Độ phức tạp thời gian là O(N).

Cách Nhị phân nhân nhanh (Binary Exponentiation)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int MOD = 1e9 + 7;


int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n; cin >> n;
    ll res = 1;
    ll a = 2;
    while (n){
        if (n % 2 == 1) res = (res * a) % MOD;
        n /= 2;
        a = (a * a) % MOD;
    }
    cout << (res - 1) % MOD;

    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất. Thay vì nhân 2 N lần (O(N)), ta tính 2^N bằng phương pháp nhân nhanh (Binary Exponentiation). Phương pháp này chia số mũ N thành các thừa số nhị phân (ví dụ: 2^13 = 2^8 * 2^4 * 2^1) và thực hiện nhân trong vòng lặp while. Độ phức tạp thời gian giảm xuống đáng kể O(log N), rất nhanh ngay cả với N lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Số bước tối thiểu để chuyển N đĩa là 2^N - 1.
• Vì N có thể lên tới 500, giá trị 2^500 rất lớn, bắt buộc phải thực hiện tính toán modulo 10^9 + 7 trong từng bước.
• Phương pháp Binary Exponentiation (Nhân nhanh) giúp giảm độ phức tạp từ O(N) xuống O(log N).

Lỗi thường gặp

• Quên trừ đi 1 ở công thức 2^N - 1 trước khi in kết quả.
• Tràn số nguyên khi tính lũy thừa (ví dụ: t *= 2 quá giới hạn của kiểu int hoặc long long nếu không chia lấy dư thường xuyên).
• Sử dụng đệ quy quá sâu dẫn đến lỗi Stack Overflow với N lớn (nếu N=500, đệ quy 500 cấp độ thường an toàn ở hầu hết cấu hình, nhưng không phải là phương pháp tối ưu).