Hiểu bài toán

Bài toán yêu cầu tính tổng S của các số nguyên từ 1 đến n, với n là một số nguyên dương nhập từ bàn phím (n ≤ 10^6). Công thức toán học là S = 1 + 2 + 3 + ... + n.

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

Cách Vòng lặp (Brute Force)

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int tong = 0;
    int i;
    for (i = 1; i <= n; i++)
    {
        tong = tong + i;
        if(i==n)
        {
            printf("%d", tong);
        }
    }
    return 0;
}

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

Approach này sử dụng một vòng lặp for để lặp qua từng số từ 1 đến n. Trong mỗi lượt lặp, nó cộng giá trị của biến lặp (i) vào biến tổng (tong). Vòng lặp dừng lại khi i vượt quá n. Đây là cách tiếp cận trực quan nhất, bắt máy tính thực hiện phép cộng từng bước một.

Cách Công thức toán học (Optimal)

#include<stdio.h>
int main() {
    int n;
    scanf("%d", &n);

    int sum = n * (n+1) / 2;
    printf("%d", sum);
    return 0;
}

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

Approach này sử dụng công thức tổng quát để tính tổng các số hạng từ 1 đến n: S = n * (n + 1) / 2. Thay vì thực hiện hàng triệu phép cộng, chương trình chỉ cần thực hiện 2 phép nhân và 1 phép chia. Đây là phương pháp hiệu quả nhất về mặt thời gian thực thi.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng hai phương pháp: mô phỏng trực tiếp (vòng lặp) hoặc sử dụng công thức toán học.
• Với giới hạn n ≤ 10^6, cả hai phương pháp đều chạy trong thời gian chấp nhận được, nhưng công thức toán học (O(1)) vượt trội hơn hẳn về tốc độ.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu n rất lớn, giá trị n * (n+1) có thể vượt quá giới hạn của kiểu số nguyên 32-bit. Tuy nhiên, với n ≤ 10^6, phép tính này (~10^12) vẫn an toàn nếu dùng kiểu dữ liệu 64-bit (long long), nhưng với int thì n cần nhỏ hơn khoảng 46,000. May mắn là trong bài này n ≤ 10^6 nên dùng int (với công thức chia 2 trước) hoặc long long là an toàn.
• Sai lệch logic vòng lặp: Vòng lặp phải chạy từ 1 đến n bao gồm cả n (i <= n).