Array algorithms: max, count, search, average

English

Four classic array jobs

Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
Each one is a single for loop over the array, with a variable that remembers something.
Once you know these four, most array problems are a small change to one of them.

Tiếng Việt

Bốn công việc mảng kinh điển

Hầu hết công việc với mảng là một trong bốn phép quét: tìm giá trị lớn nhất, đếm số lần trùng khớp, tìm kiếm một giá trị, hoặc tính trung bình cộng.
Mỗi loại đều là một vòng lặp for đơn giản trên mảng, kèm theo một biến nhớ giữ dữ liệu.
Một khi bạn nắm vững bốn kỹ thuật này, hầu hết các bài toán mảng chỉ là một thay đổi nhỏ của một trong chúng.

English

Finding the maximum

Start by assuming the first item is the biggest: int best = a[0];.
Then look at the rest. If an item is bigger than best, it becomes the new best.
This works for negative numbers too, because you start from a real item, not 0.

Tiếng Việt

Tìm giá trị lớn nhất

Bắt đầu bằng cách giả sử mục đầu tiên là lớn nhất: int best = a[0];.
Sau đó xem xét phần còn lại. Nếu một mục lớn hơn best, nó sẽ trở thành best mới.
Cách này hoạt động với cả số âm, vì bạn bắt đầu từ một mục thực tế, chứ không phải 0.

English

Counting with a condition

A counter starts at 0 and adds 1 each time an item passes a test.
For example, count even numbers by testing a[i] % 2 == 0 inside the loop.
The counter's final value is your answer.

Tiếng Việt

Đếm với điều kiện

Một bộ đếm bắt đầu ở 0 và tăng 1 mỗi khi một mục vượt qua điều kiện kiểm tra.
Ví dụ, đếm số chẵn bằng cách thử nghiệm a[i] % 2 == 0 bên trong vòng lặp.
Giá trị cuối cùng của bộ đếm chính là câu trả lời của bạn.

English

Linear search

To search, walk the array and compare each item to the target.
Return the index as soon as you find a match. If the loop ends with no match, return -1.
-1 is a common "not found" signal because it is never a valid index.

Tiếng Việt

Tìm kiếm tuyến tính

Để tìm kiếm, hãy duyệt qua mảng và so sánh từng mục với giá trị mục tiêu.
Trả về chỉ số ngay khi bạn tìm thấy sự trùng khớp. Nếu vòng lặp kết thúc mà không có matches, hãy trả về -1.
-1 là tín hiệu "không tìm thấy" phổ biến vì nó chưa bao giờ là chỉ số hợp lệ.

English

Average without integer-division bugs

Add all the items into an int total, then divide by n.
Dividing two ints drops the fraction, so cast: (double)total / n.
Return a double so the caller gets the exact average.

Tiếng Việt

Trung bình cộng mà không gặp lỗi chia nguyên

Cộng tất cả các mục vào một tổng int, sau đó chia cho n.
Chia hai int sẽ bỏ phần thập phân, nên cần ép kiểu: (double)total / n.
Trả về một double để người gọi nhận được giá trị trung bình chính xác.

English

Common mistakes

Start a max or min from the first element, then compare the rest.
Do not read past the end of the array.

Tiếng Việt

Lỗi thường gặp

Khởi tạo max hoặc min từ phần tử đầu tiên, sau đó so sánh với các phần tử còn lại.
Đừng đọc vượt quá giới hạn của mảng.

English

Now you try

Pass the array and its length n, and pick the right "remember" variable for each job.
Do not write a main — the checker provides one.

Tiếng Việt

Bây giờ bạn thử

Truyền vào mảng và độ dài n của nó, và chọn đúng biến "nhớ" cho mỗi công việc.
Không viết một main — trình kiểm tra sẽ cung cấp cho bạn một cái.

Explore · ⁨Khám phá⁩

Scanning an array

One pass keeps a running result (max, sum, count) across the array.

Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not write a main.

/* Return the largest of a[0..n-1] (n >= 1). Do not write main(). */
int max(const int a[], int n) {
    return 0;   /* start from a[0], not 0 */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main.

/* Count the even items of a[0..n-1]. Do not write main(). */
int count_even(const int a[], int n) {
    return 0;   /* test a[i] % 2 == 0 */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not write a main.

/* Return the index of the first target, or -1. Do not write main(). */
int index_of(const int a[], int n, int target) {
    return -1;   /* return i as soon as a[i] == target */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not write a main.

/* Return the average of a[0..n-1] as a double. Do not write main(). */
double average(const int a[], int n) {
    return 0.0;   /* sum, then (double)total / n */
}

Click Run to see the output here. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Four classic array jobs

Bốn công việc mảng kinh điển

Finding the maximum

Tìm giá trị lớn nhất

Counting with a condition

Đếm với điều kiện

Linear search

Tìm kiếm tuyến tính

Average without integer-division bugs

Trung bình cộng mà không gặp lỗi chia nguyên

Common mistakes

Lỗi thường gặp

Now you try

Bây giờ bạn thử

Scanning an array

Handout · ⁨Tài liệu⁩

Log in or create account · ⁨Đăng nhập hoặc tạo tài khoản⁩

Your subject · ⁨Môn học của bạn⁩

All sections · ⁨Tất cả các mục⁩

Feedback & help · ⁨Phản hồi & hỗ trợ⁩