Hiểu bài toán

Bài toán yêu cầu thực hiện một chuỗi các biến đổi trên một số nguyên dương n theo quy tắc: nếu n là số chẵn thì n = n / 2, nếu n là số lẻ thì n = n * 3 + 1. Quá trình này lặp lại cho đến khi n bằng 1. Yêu cầu in ra giá trị của n sau mỗi bước biến đổi (bao gồm cả giá trị ban đầu). Với n trong khoảng 1 đến 10^6, ta cần đảm bảo quy trình kết thúc (xác suất theo giả thuyết Collatz là 100% với giới hạn này) và in đúng định dạng.

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

Cách Vòng lặp While cơ bản

#include <iostream>
using namespace std;
int main(){
    long long n;
    cin >> n;
    cout << n << " ";
    while (n != 1) {
        if (n % 2 == 0) n = n / 2;
        else n = n * 3 + 1;
        cout << n << " ";
    }
    return 0;
}

• Time Complexity: O(k) (k là số bước để về 1, nhỏ hơn ~10^6)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất, mô phỏng chính xác quy trình được mô tả. Ta đọc vào n, in giá trị ban đầu, sau đó dùng vòng lặp while để thực hiện phép chia hoặc nhân cộng cho đến khi n bằng 1. Mỗi lần tính toán xong ta in ra giá trị mới ngay lập tức. Dữ liệu dùng kiểu long long để tránh tràn số khi n nhân 3 (dù n max 10^6 vẫn an toàn với int, nhưng long long là thói quen tốt cho các bài tương tự).

Cách Tối ưu bit operation

#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    while (n != 1) {
        cout << n << ' ';
        if (n & 1) n = n * 3 + 1;
        else n >>= 1;
    }
    cout << 1;
    return 0;
}

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

Đây là biến thể tối ưu hóa tốc độ nhập xuất và phép tính. Sử dụng 'n & 1' để kiểm tra số lẻ nhanh hơn phép chia lấy dư (% 2). Sử dụng 'n >>= 1' (dịch bit sang trái) để chia cho 2 nhanh hơn phép chia toán học. Đồng thời thêm các dòng tối ưu IO (ios::syncwithstdio) để tăng tốc độ đọc ghi.

Cách Xử lý xuất ra trước vòng lặp

#include <bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    cin >> n;
    cout << n << " ";
    while (n > 1) {
        if (n % 2 == 0) n = n / 2;
        else n = n * 3 + 1;
        cout << n << " ";
    }
    return 0;
}

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

Phương pháp này in giá trị ban đầu trước, sau đó vào vòng lặp while. Trong vòng lặp, nó tính toán giá trị mới và in ngay lập tức. Điều kiện dừng là n > 1 (tương đương n != 1). Đây là cách xử lý logic khá phổ biến để đảm bảo in đúng số lượng số hạng.

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

Bài học kinh nghiệm

• Quy tắc này là biến thể của bài toán 'Dãy số Collatz', luôn dừng lại ở 1 với các n thực tế nhỏ.
• Sử dụng phép toán bit (dịch bit & bitwise AND) giúp tăng hiệu năng so với phép chia lấy dư và phép chia thường.
• Kiểu dữ liệu long long là an toàn tuyệt đối cho bài toán này, tránh tràn số trong các trường hợp bài toán tương tự có n lớn hơn.

Lỗi thường gặp

• Bỏ qua việc in số ban đầu trước khi vào vòng lặp, dẫn đến thiếu mất số đầu tiên trong dãy.
• Dùng int cho biến n, có thể gây tràn số (overflow) nếu n lớn (ví dụ n > 10^9) khi thực hiện nhân 3, dù ở bài này n <= 10^6 thì int vẫn đủ.
• In thêm dấu cách thừa ở cuối dòng output, tuy nhiều bộ chấm vẫn cho qua nhưng tốt nhất nên kiểm soát định dạng in.