Hiểu bài toán

Bài toán yêu cầu tính số bước cần thiết để biến một số nguyên dương $N$ về 1 dựa trên quy luật sau:

• Nếu $N$ chẵn: $N = N / 2$
• Nếu $N$ lẻ: $N = 3N + 1$ Quy trình này lặp lại cho đến khi $N = 1$. Đây chính là biến thể của bài toán 'Dãy Collatz' (hay còn gọi là bài toán 3n+1). Đầu vào là số $N$, đầu ra là số bước thực hiện.

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

Cách Mô phỏng trực tiếp (Simulation)

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("change.INP", "r", stdin);
    freopen("change.OUT", "w", stdout);

    long long N;
    cin >> N;

    int steps = 0;
    while (N != 1) {
        if (N % 2 == 0)
            N /= 2;
        else
            N = 3 * N + 1;
        ++steps;
    }

    cout << steps << endl;

    return 0;
}

• Time Complexity: O(k) (với k là số bước để về 1)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất và trực quan nhất. Ta bắt đầu với giá trị $N$ ban đầu và lặp lại quy tắc:

1. Kiểm tra $N$ chẵn hay lẻ.
2. Nếu chẵn, chia đôi $N$.
3. Nếu lẻ, nhân 3 và cộng 1.
4. Tăng biến đếm số bước lên 1.
5. Lặp lại cho đến khi $N = 1$.

Trong code, biến N được khai báo kiểu long long để tránh tràn số integer khi $N$ tăng giá trị lớn (đặc biệt ở các bước lẻ). Biến steps đếm số lần thực hiện phép toán.

Cách Tối ưu hóa IO

#include <bits/stdc++.h>
#define ll long long
#define DOWNTIME ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); 
#define FIXED(x) fixed << setprecision(x)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
#define pb push_back

using namespace std;

const int MAX = 1e6 + 1; 

int main() {
    freopen("change.inp","r", stdin);
    freopen("change.out", "w", stdout);
    DOWNTIME
    ll n; cin >> n;
    int dem = 0;
    while (n != 1) {
        if (n % 2 != 0) n = n * 3 + 1;
        else n /= 2;
        dem++;
    }
    cout << dem;
    return 0;
}

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

Về bản chất thuật toán vẫn là mô phỏng quy luật Collatz. Tuy nhiên, cách tiếp cận này tập trung vào việc tối ưu hóa tốc độ nhập xuất (I/O) và khai báo thư viện.

• Sử dụng #include <bits/stdc++.h>: Bao gồm hầu hết các thư viện chuẩn.
• Sử dụng ios_base::sync_with_stdio(false); cin.tie(NULL);: Tắt đồng bộ hóa giữa C và C++ streams và bỏ việc flush cout trước khi cin, giúp nhập xuất nhanh hơn đáng kể.
• Biến n kiểu ll (long long) đảm bảo không tràn số.
• Logic toán học tương tự Approach 1.

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

Bài học kinh nghiệm

• Bài toán là mô phỏng chuẩn của dãy Collatz (3n+1), đảm bảo luôn kết thúc tại 1.
• Phép nhân 3 có thể gây tràn số nếu dùng int, bắt buộc phải dùng long long (hoặc unsigned long long) cho biến $N$.
• Vòng lặp while là sufficient để giải quyết bài toán này cho các dữ kiện thực tế của đề thi (thường $N \le 10^18$).

Lỗi thường gặp

• Sử dụng biến kiểu int cho $N$: Khi $N$ là số lẻ lớn, $3N+1$ rất dễ vượt quá giới hạn của int (khoảng $2 \times 10^9$), dẫn đến lỗi tràn số và kết quả sai.
• Quên tăng biến đếm bước (steps): Cần nhớ tăng dem hoặc steps sau mỗi lần thay đổi giá trị $N$.