Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 9.616 phút đọc

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

min-max.c
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

ca-hai.c
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

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 */
Khởi tạo bằng phần tử đầu
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ểmNhược điểm
m = a[0]Kết quả luôn là một phần tử thật có trong mảngPhải xử lý riêng trường hợp mảng rỗng
m = INT_MINVòng lặp chạy từ 0, không cần trường hợp đặc biệtVới mảng rỗng trả về INT_MIN, giá trị không có thật
m = 0Không có ưu điểm nàoSai 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.

vi-tri.c
/* 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áchCài thế nàoNgười gọi phải làm gì
Trả về mã lỗiint tim_max(const int *a, size_t n, int *kq) trả về 0 hoặc âm mộtKiể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ỗngKiểm tra kết quả có nhỏ hơn n không
Coi là lỗi lập trìnhassert(n > 0) ở đầu hàmBảo đảm không bao giờ gọi với mảng rỗng
ba-cach.c
#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ư.

theo-cap.c
/* Ý 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áchSố phép so sánhVới n bằng 1 000 000
Thông thường2(n - 1)1 999 998
Theo cặpkhoảng 1.5nkhoảng 1 500 000
terminal
# Kiểm chứng bằng cách đếm phép so sánh thật
./dem-so-sanh 1000000
thong thuong: 1999998 phep so sanh
theo cap:     1499998 phep so sanh
ti le:        0.75

Tự làm thử

  1. Cài lon_nhat vớ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.
  2. Viết tim_min_max trả 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  • assert biến mất khi biên dịch với NDEBUG, nên chỉ dùng nó cho lỗi lập trình chứ không cho dữ liệu người dùng.