HƯỚNG DẪN GIẢI BÀI TOÁN: DÃY SỐ ĐẢO NGƯỢC (DSDN.CPP)

1. Phân tích bài toán

• Yêu cầu: Cho một dãy gồm ~n~ số nguyên. Cần in ra các phần tử của dãy theo thứ tự ngược lại (từ cuối lên đầu, tức là từ vị trí thứ ~n~ lùi về vị trí thứ ~1~).
• Giới hạn dữ liệu:
  • ~1 \le n \le 10^5~.
  • Các phần tử có giá trị tuyệt đối không vượt quá ~10^9~ (nằm trong phạm vi biểu diễn của kiểu số nguyên chuẩn int hoặc long long).
• Cấu trúc dữ liệu: Sử dụng mảng một chiều có kích thước tối thiểu ~10^5 + 5~ phần tử để lưu trữ các giá trị của dãy số.

2. Thuật toán

1. Nhập vào số nguyên dương ~n~.
2. Sử dụng vòng lặp duyệt từ ~i = 1~ đến ~n~ để nhập lần lượt các phần tử vào mảng 1 chiều ~a~.
3. Sử dụng vòng lặp duyệt ngược từ ~i = n~ giảm dần về ~1~:
   • In giá trị ~a[i]~ kèm một khoảng trắng.

3. Mã nguồn C++ (DSDN.CPP)

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

const int MAXN = 100005;
int a[MAXN];

int main() {
    // Tối ưu tốc độ nhập xuất dữ liệu
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Nhập các phần tử vào mảng 1 chiều
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // In mảng theo thứ tự ngược lại (từ cuối về đầu)
    for (int i = n; i >= 1; i--) {
        cout << a[i] << " ";
    }

    return 0;
}

4. Đánh giá độ phức tạp

• Độ phức tạp thời gian (Time Complexity): ~O(n)~ do ta chỉ duyệt qua mảng đúng 2 lần (một lần đọc dữ liệu và một lần in kết quả). Với ~n \le 10^5~, thời gian chạy thực tế khoảng ~0.02~ giây, hoàn toàn tối ưu.
• Độ phức tạp không gian (Space Complexity): ~O(n)~ dùng cho mảng 1 chiều ~10^5~ phần tử (chiếm dưới 1 MB bộ nhớ).