Hiểu bài toán

Bài toán yêu cầu tính giá trị S theo công thức: S = (2 + 3 + 4 + ... + n) + 2n, với n là số nguyên dương nhập vào (n ≥ 2). Nói cách khác, ta cần tính tổng các số từ 2 đến n, rồi cộng thêm 2n vào kết quả đó.

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

Cách Vòng lặp For

#include <stdio.h>

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

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

Cách tiếp cận này sử dụng một vòng lặp để duyệt từ 2 đến n, cộng dồn từng số vào biến tổng. Sau đó, cộng thêm 2n vào tổng thu được và in ra kết quả. Đây là cách làm trực quan nhất, dễ hiểu và dễ cài đặt.

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

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a;
    scanf("%d", &a);
    printf("%d", (a * (a + 1) / 2) - 1 + 2 * a);
    return 0;
}

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

Thay vì dùng vòng lặp, ta sử dụng công thức tổng quát của cấp số cộng. Tổng các số từ 1 đến n là n(n+1)/2. Để lấy tổng từ 2 đến n, ta lấy tổng từ 1 đến n rồi trừ đi 1. Cuối cùng cộng thêm 2n. Công thức rút gọn là: S = (n(n+1)/2) - 1 + 2n. Cách này tối ưu nhất về mặt thời gian chạy.

Cách Vòng lặp For với kiểu dữ liệu lớn

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

    for(int i = 2; i <=n; i++){
        s += i;
    }
    printf ("%lld", s+ (2*n));
}

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

Đây là biến thể của phương pháp vòng lặp, được tối ưu hóa một chút bằng cách sử dụng kiểu dữ liệu 'long long' cho biến tổng. Điều này đảm bảo tính chính xác nếu kết quả vượt quá phạm vi của kiểu 'int' (mặc dù với n ≤ 10^4, 'int' vẫn đủ).

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

Bài học kinh nghiệm

• Công thức tổng quát của tổng các số nguyên liên tiếp giúp giải quyết bài toán với độ phức tạp thời gian O(1).
• Bài toán có thể được coi là tổng của một dãy số cộng hoặc trừ một cách đơn giản.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow) nếu n đủ lớn và ta chỉ dùng kiểu int cho biến lưu kết quả.
• Nhập sai định dạng input/output theo yêu cầu của đề bài.