Tìm giá trị nhỏ nhất và lớn nhất
Sau bài này bạn sẽ làm được
- Tránh sai lầm khởi tạo biến min bằng 0
- Trả về cả giá trị lẫn vị trí tìm thấy
- Xử lý đúng trường hợp mảng rỗng
- Cài thuật toán so sánh theo cặp tiết kiệm 25 phần trăm phép so sánh
Tìm giá trị lớn nhất và nhỏ nhất trông như bài dễ nhất của chương. Nó có đúng ba cái bẫy, và cả ba đều là loại chương trình vẫn chạy nhưng cho kết quả sai, tức là loại khó phát hiện nhất.
#Cách viết cơ bản
int lon_nhat(const int *a, size_t n)
{
int m = a[0]; /* khởi tạo bằng phần tử đầu, không phải bằng 0 */
for (size_t i = 1; i < n; ++i) /* bắt đầu từ 1 vì đã lấy a[0] rồi */
if (a[i] > m)
m = a[i];
return m;
}
int nho_nhat(const int *a, size_t n)
{
int m = a[0];
for (size_t i = 1; i < n; ++i)
if (a[i] < m)
m = a[i];
return m;
}Hai chi tiết đáng chú ý. Biến kết quả khởi tạo bằng a[0], và vòng lặp bắt đầu từ chỉ số 1. Bắt đầu từ 0 cũng đúng nhưng thừa đúng một phép so sánh, vì a[0] > a[0] luôn sai.
Tìm cả hai trong một lượt
void tim_min_max(const int *a, size_t n, int *mn, int *mx)
{
if (n == 0) return; /* không có gì để tìm */
*mn = *mx = a[0];
for (size_t i = 1; i < n; ++i) {
if (a[i] < *mn) *mn = a[i];
if (a[i] > *mx) *mx = a[i];
}
}
int nho, lon;
tim_min_max(a, n, &nho, &lon);Đây là mẫu tham số ra ở Bài 8.6. Hàm cần trả về hai giá trị nên nó nhận hai con trỏ. Một lượt duyệt duy nhất, thay vì gọi hai hàm riêng và duyệt mảng hai lần.
#Sai lầm khởi tạo bằng 0
int lon_nhat(const int *a, size_t n)
{
int m = 0; /* sai nếu MỌI phần tử đều âm */
for (size_t i = 0; i < n; ++i)
if (a[i] > m) m = a[i];
return m;
}
int a[3] = { -5, -1, -9 };
printf("%d\n", lon_nhat(a, 3)); /* in ra 0, nhưng 0 không có trong mảng */int lon_nhat(const int *a, size_t n)
{
int m = a[0];
for (size_t i = 1; i < n; ++i)
if (a[i] > m) m = a[i];
return m;
}
int a[3] = { -5, -1, -9 };
printf("%d\n", lon_nhat(a, 3)); /* -1, đúng */Phương án dùng giá trị cực trị của kiểu
#include <limits.h>
int lon_nhat(const int *a, size_t n)
{
int m = INT_MIN; /* nhỏ hơn hoặc bằng mọi giá trị int */
for (size_t i = 0; i < n; ++i)
if (a[i] > m) m = a[i];
return m;
}| Cách khởi tạo | Ưu điểm | Nhược điểm |
|---|---|---|
| m = a[0] | Kết quả luôn là một phần tử thật có trong mảng | Phải xử lý riêng trường hợp mảng rỗng |
| m = INT_MIN | Vòng lặp chạy từ 0, không cần trường hợp đặc biệt | Với mảng rỗng trả về INT_MIN, giá trị không có thật |
| m = 0 | Không có ưu điểm nào | Sai khi mọi phần tử cùng dấu ngược lại |
Cách dùng INT_MIN chỉ hợp khi bạn chắc chắn mảng không rỗng, hoặc khi giá trị cực trị là câu trả lời chấp nhận được. Nếu dùng cách này thì đừng quên #include <limits.h>, và nhớ rằng mỗi kiểu có hằng riêng: LONG_MIN, LLONG_MIN, DBL_MAX trong float.h.
#Trả về cả vị trí
Thường bạn không chỉ cần giá trị mà còn cần biết nó ở đâu. Ví dụ tìm sinh viên có điểm cao nhất thì cần chỉ số để tra tên.
/* Trả về chỉ số của phần tử lớn nhất. Trả về n nếu mảng rỗng. */
size_t vi_tri_lon_nhat(const int *a, size_t n)
{
if (n == 0) return n;
size_t vt = 0;
for (size_t i = 1; i < n; ++i)
if (a[i] > a[vt])
vt = i;
return vt;
}
size_t vt = vi_tri_lon_nhat(diem, n);
if (vt < n)
printf("Cao nhat: %s duoc %d diem\n", ten[vt], diem[vt]);Trả về chỉ số tiện hơn trả về giá trị, vì từ chỉ số bạn lấy được giá trị bằng a[vt], còn chiều ngược lại thì không. Quy ước trả về n khi mảng rỗng cũng thuận tiện vì n luôn là chỉ số không hợp lệ.
Trả về cả bốn thông tin bằng struct
typedef struct {
int min, max;
size_t vt_min, vt_max;
int hop_le; /* 0 nếu mảng rỗng */
} ThongKe;
ThongKe phan_tich(const int *a, size_t n)
{
ThongKe t = { 0, 0, 0, 0, 0 };
if (n == 0) return t;
t.min = t.max = a[0];
t.hop_le = 1;
for (size_t i = 1; i < n; ++i) {
if (a[i] < t.min) { t.min = a[i]; t.vt_min = i; }
if (a[i] > t.max) { t.max = a[i]; t.vt_max = i; }
}
return t;
}#Xử lý mảng rỗng
Mảng rỗng là trường hợp biên mà mọi hàm nhận mảng đều phải trả lời được. Có ba cách xử lý, và bạn phải chọn một cách rồi ghi rõ vào tài liệu của hàm.
| Cách | Cài thế nào | Người gọi phải làm gì |
|---|---|---|
| Trả về mã lỗi | int tim_max(const int *a, size_t n, int *kq) trả về 0 hoặc âm một | Kiểm tra giá trị trả về trước khi dùng kq |
| Trả về chỉ số không hợp lệ | Trả về n khi mảng rỗng | Kiểm tra kết quả có nhỏ hơn n không |
| Coi là lỗi lập trình | assert(n > 0) ở đầu hàm | Bảo đảm không bao giờ gọi với mảng rỗng |
#include <assert.h>
/* Cách 1: mã lỗi */
int tim_max1(const int *a, size_t n, int *kq)
{
if (n == 0) return -1;
*kq = a[0];
for (size_t i = 1; i < n; ++i)
if (a[i] > *kq) *kq = a[i];
return 0;
}
/* Cách 3: khẳng định. Chỉ hoạt động khi biên dịch không có NDEBUG. */
int tim_max3(const int *a, size_t n)
{
assert(a != NULL && n > 0);
int m = a[0];
for (size_t i = 1; i < n; ++i)
if (a[i] > m) m = a[i];
return m;
}#Tìm cả hai bằng ít phép so sánh hơn
Cách viết thông thường tốn 2(n - 1) phép so sánh. Có một thuật toán tốn khoảng 1.5 n, tiết kiệm khoảng một phần tư.
/* Ý tưởng: xét từng cặp. So hai phần tử trong cặp với nhau trước,
rồi chỉ so cái nhỏ hơn với min và cái lớn hơn với max.
Ba phép so sánh cho hai phần tử, thay vì bốn. */
void tim_min_max_nhanh(const int *a, size_t n, int *mn, int *mx)
{
if (n == 0) return;
size_t i;
if (n % 2 == 1) {
*mn = *mx = a[0];
i = 1;
} else {
if (a[0] < a[1]) { *mn = a[0]; *mx = a[1]; }
else { *mn = a[1]; *mx = a[0]; }
i = 2;
}
while (i + 1 < n) {
int nho, lon;
if (a[i] < a[i + 1]) { nho = a[i]; lon = a[i + 1]; }
else { nho = a[i + 1]; lon = a[i]; }
if (nho < *mn) *mn = nho;
if (lon > *mx) *mx = lon;
i += 2;
}
}| Cách | Số phép so sánh | Với n bằng 1 000 000 |
|---|---|---|
| Thông thường | 2(n - 1) | 1 999 998 |
| Theo cặp | khoảng 1.5n | khoảng 1 500 000 |
thong thuong: 1999998 phep so sanh theo cap: 1499998 phep so sanh ti le: 0.75
Tự làm thử
- Cài
lon_nhatvới khởi tạo bằng 0 rồi chạy với mảng toàn số âm. Ghi lại kết quả sai. - Viết
tim_min_maxtrả về cả bốn thông tin bằng struct, thử với mảng có nhiều phần tử cùng giá trị lớn nhất. - Viết ba phiên bản xử lý mảng rỗng theo ba cách trong bảng, so sánh mã ở chỗ gọi.
- Cài phiên bản theo cặp, đếm số phép so sánh thật sự bằng một biến đếm và đối chiếu với công thức.
- Viết hàm tìm giá trị lớn thứ hai trong mảng, chỉ duyệt đúng một lượt. Xử lý trường hợp mọi phần tử bằng nhau.
- Viết hàm tìm k phần tử lớn nhất, so sánh cách sắp xếp trước với cách duyệt k lượt.
Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.
Tóm tắt
- Khởi tạo biến kết quả bằng
a[0], không bao giờ bằng 0. Khởi tạo bằng 0 cho kết quả sai khi mọi phần tử cùng dấu ngược lại. - Trả về chỉ số hữu ích hơn trả về giá trị, vì từ chỉ số lấy được giá trị nhưng không ngược lại.
- Dấu
>giữ vị trí đầu tiên đạt cực trị, dấu>=giữ vị trí cuối cùng. - Mảng rỗng phải được xử lý rõ ràng bằng một trong ba cách, và cách đó phải ghi vào tài liệu của hàm.
assertbiến mất khi biên dịch vớiNDEBUG, nên chỉ dùng nó cho lỗi lập trình chứ không cho dữ liệu người dùng.