Hiểu bài toán

Bài toán yêu cầu tính tổng các phần tử của các hàng có chỉ số lẻ trong một mảng 2 chiều. Lưu ý: chỉ số hàng được tính bắt đầu từ 0. Ví dụ, với ma trận 3x3: 1 2 3 4 5 6 7 8 9 Các hàng có chỉ số lẻ là hàng 1 (chứa các số 4, 5, 6). Tổng cần tính là 4 + 5 + 6 = 15.

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

Cách Nhập trước, tính toán sau (Phương pháp cơ bản)

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

const int MAX = 100;

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);

    int tong = 0, i = 0, j = 0;

    int a[MAX][MAX];

    // Nhập ma trận
    while (i < n){
        j = 0;
        while (j < m){
            scanf("%d", &a[i][j]);
            j++;
        }
        i++;
    }

    i = 0;

    // Tính tổng hàng có chỉ số lẻ
    while (i < n){
        j = 0;
        if (i % 2 == 1){
            while (j < m){
                tong += a[i][j];
                j++;
            }
        }
        i++;
    }

    printf("%d", tong);

    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Cách tiếp cận này tách biệt hai giai đoạn: nhập dữ liệu vào mảng 2 chiều và sau đó xử lý tính toán.

1. Khai báo mảng 2 chiều kích thước cố định (100x100).
2. Dùng vòng lặp để nhập từng phần tử vào mảng.
3. Dùng vòng lặp khác để duyệt qua các hàng, kiểm tra xem chỉ số hàng có phải là số lẻ không (i % 2 == 1).
4. Nếu là hàng lẻ, cộng dồn các phần tử của hàng đó vào biến tổng. Phương pháp này dễ hiểu nhưng yêu cầu bộ nhớ lưu trữ toàn bộ ma trận.

Cách Nhập và Tính toán đồng thời (Tối ưu bộ nhớ)

#include <stdio.h>
#include <math.h>
#include <limits.h>
#define Nmax 10010
int a[100][100];
int main()
{
    int m,n,sum=0;
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
            if(i%2!=0) sum+=a[i][j];
        }
    }
    printf("%d",sum);
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Phương pháp này gộp việc nhập dữ liệu và tính tổng vào cùng một vòng lặp lồng nhau.

1. Khởi tạo biến tổng sum = 0.
2. Duyệt qua từng hàng i và từng cột j.
3. Trong quá trình nhập giá trị cho phần tử a[i][j], kiểm tra ngay lập tức nếu chỉ số hàng i là số lẻ (i % 2 != 0).
4. Nếu đúng, cộng giá trị vừa nhập vào sum. Cách này không cần phải duyệt lại ma trận một lần nữa nhưng vẫn cần bộ nhớ để lưu ma trận.

Cách Chỉ lưu trữ dòng cần thiết (Tối ưu bộ nhớ tối đa)

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d%d", &m, &n);

    int a[n]; // Mảng 1 chiều lưu tạm dữ liệu hàng hiện tại

    int sum = 0;

    // Duyệt qua từng hàng
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[j]);
        }
        // Chỉ cộng dồn nếu hàng có chỉ số lẻ
        if (i % 2 != 0) {
            for (int j = 0; j < n; j++) {
                sum += a[j];
            }
        }
    }

    printf("%d", sum);

    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(n)

Đây là cách tiếp cận tối ưu nhất về mặt bộ nhớ.

1. Thay vì khai báo mảng 2 chiều a[m][n], ta chỉ cần khai báo mảng 1 chiều a[n].
2. Duyệt qua từng hàng i từ 0 đến m-1.
3. Đọc toàn bộ n phần tử của hàng hiện tại vào mảng 1 chiều.
4. Kiểm tra nếu i là số lẻ, duyệt qua mảng 1 chiều và cộng vào tổng.
5. Sang hàng tiếp theo, dữ liệu cũ sẽ bị ghi đè. Cách này chỉ cần bộ nhớ phụ tối đa O(n) thay vì O(m*n).

Cách Sử dụng biến động (Không cần mảng)

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d%d", &m, &n);

    int sum = 0;
    int val;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &val);
            if (i % 2 != 0) {
                sum += val;
            }
        }
    }

    printf("%d", sum);

    return 0;
}

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

Đây là phương pháp hiệu quả nhất.

1. Không cần lưu giữ ma trận hay bất kỳ hàng nào.
2. Chỉ cần một biến val để nhận giá trị từ input.
3. Duyệt vòng lặp i (hàng) và j (cột).
4. Đọc giá trị vào val. Nếu i lẻ, cộng val vào sum. Thời gian chạy nhanh, tốn ít bộ nhớ nhất.

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

Bài học kinh nghiệm

• Chỉ số hàng bắt đầu từ 0, nên hàng có chỉ số chẵn (0, 2...) là hàng 1, 3... theo cách đếm tự nhiên. Hàng có chỉ số lẻ là hàng 2, 4... theo cách đếm tự nhiên.
• Bài toán có thể giải quyết mà không cần lưu trữ toàn bộ dữ liệu vào bộ nhớ nếu ta chỉ quan tâm đến tổng.
• Sử dụng phép chia lấy dư % để kiểm tra tính chẵn/lẻ của chỉ số.

Lỗi thường gặp

• Nhầm lẫn giữa chỉ số bắt đầu từ 0 và bắt đầu từ 1. Ví dụ: nếu coi hàng đầu tiên là hàng 1 (lẻ) thì sẽ tính sai.
• Quên khai báo mảng có kích thước đủ lớn nếu dùng phương pháp lưu trữ.
• Sử dụng sai biến vòng lặp khi truy cập phần tử mảng.