Thuật toán mảng: tìm max, đếm, tìm kiếm, trung bình
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.
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ànhbestmớ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.
Đếm với điều kiện
- Một bộ đếm bắt đầu ở
0và tăng1mỗ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 == 0bê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.
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. -1là 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ệ.
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 chon. - Chia hai
intsẽ 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.
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.
Bây giờ bạn thử
- Truyền vào mảng và độ dài
ncủ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.
Quét qua một mảng
Một lượt quét giữ một kết quả tích lũy (giá trị lớn nhất, tổng, đếm) xuyên suốt mảng.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thành int max(const int a[], int n) để trả về phần tử lớn nhất (giả sử n >= 1). Bắt đầu từ a[0] để xử lý số âm. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thành int count_even(const int a[], int n) để trả về số lượng phần tử chẵn. Sử dụng % 2. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thành int index_of(const int a[], int n, int target) sao cho nó trả về chỉ số của target đầu tiên, hoặc -1 nếu không tìm thấy. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Hoàn thành double average(const int a[], int n) để trả về giá trị trung bình của các phần tử (giả sử n >= 1). Chuyển đổi kiểu để tránh phép chia nguyên. Không viết một main.
Nhấn Chạy để xem kết quả ở đây.