Quy trình giải bài toán

#Vì sao cần quy trình

Cách làm phổ biến của người mới là đọc đề xong mở editor gõ ngay. Cách đó chạy được với bài dễ, nhưng gặp bài khó thì tắc, và tắc theo kiểu không biết mình đang tắc ở đâu.

#Sáu bước

1. 1

   Hiểu bài toán

   Trả lời bốn câu hỏi trước khi làm gì khác. Nếu đề không nói rõ thì phải hỏi lại, đừng tự giả định.

   • Vào là gì: kiểu dữ liệu, miền giá trị, kích thước tối đa, nguồn dữ liệu
   • Ra là gì: định dạng, cách làm tròn, đơn vị
   • Ràng buộc: giới hạn thời gian, giới hạn bộ nhớ, độ chính xác
   • Trường hợp biên: n bằng 0, n bằng 1, số âm, dữ liệu trùng nhau, tràn số
2. 2

   Lấy ví dụ cụ thể

   Làm bằng tay vài ví dụ nhỏ trước khi nghĩ tới mã. Lấy một ví dụ bình thường, một ví dụ biên, và một ví dụ xấu nhất. Nếu bạn không giải được bằng tay thì chắc chắn không viết được chương trình.

3. 3

   Tìm quy luật hoặc chia nhỏ

   Hai câu hỏi mở khóa phần lớn bài toán:

   • Bài này giống bài nào mình đã biết cách giải?
   • Có chia được thành các bài toán con nhỏ hơn cùng dạng không?
4. 4

   Viết mã giả

   Diễn đạt thuật toán bằng tiếng Việt có cấu trúc, chưa quan tâm cú pháp C. Bước này tách việc nghĩ ra khỏi việc gõ, nên bạn không phải làm hai việc khó cùng lúc. Cách viết mã giả ở Bài 7.3.

5. 5

   Cài đặt

   Dịch mã giả sang C, từng phần một, biên dịch thường xuyên. Nếu bước 4 làm tốt thì bước này gần như máy móc và ít lỗi.

6. 6

   Kiểm thử và tối ưu

   Chạy lại đúng những ví dụ đã làm tay ở bước 2, cộng thêm các trường hợp biên ở bước 1. Chỉ tối ưu sau khi đã chạy đúng, và chỉ tối ưu chỗ đã đo được là chậm.

#Áp dụng vào một bài toán

Bước 1: hiểu bài toán

Vào    : mảng n số nguyên, n >= 1
Ra     : một số nguyên, là giá trị lớn thứ hai
Ràng buộc: n có thể tới 10^6, nên thuật toán phải nhanh hơn O(n^2)

Trường hợp biên:
  n = 1              -> không có số thứ hai, phải báo lỗi
  [5, 5, 5]          -> mọi phần tử bằng nhau, có số thứ hai không?
  [3, 3, 1]          -> giá trị lớn nhất lặp lại, số thứ hai là 3 hay 1?
  mảng toàn số âm    -> không được khởi tạo biến đếm bằng 0

Bước 2: lấy ví dụ cụ thể

Bước 3: tìm hướng giải

Bước 4: viết mã giả

HÀM lon_thu_hai(A, n)
    NẾU n < 2 THÌ TRẢ VỀ "không có"

    max1 ← âm vô cùng
    max2 ← âm vô cùng

    VỚI MỖI x TRONG A
        NẾU x > max1 THÌ
            max2 ← max1
            max1 ← x
        NGƯỢC LẠI NẾU x > max2 VÀ x ≠ max1 THÌ
            max2 ← x
        HẾT NẾU
    HẾT VỚI

    NẾU max2 = âm vô cùng THÌ TRẢ VỀ "không có"

    TRẢ VỀ max2
HẾT HÀM

Bước 5: cài đặt

#include <stdio.h>
#include <limits.h>

/* Trả về 0 nếu tìm được, khác 0 nếu mảng không có giá trị lớn thứ hai. */
int lon_thu_hai(const int *a, size_t n, int *out)
{
    if (n < 2) {
        return -1;
    }

    long long max1 = LLONG_MIN;
    long long max2 = LLONG_MIN;

    for (size_t i = 0; i < n; ++i) {
        if (a[i] > max1) {
            max2 = max1;
            max1 = a[i];
        } else if (a[i] > max2 && a[i] != max1) {
            max2 = a[i];
        }
    }

    if (max2 == LLONG_MIN) {
        return -1;
    }

    *out = (int)max2;

    return 0;
}

Bước 6: kiểm thử

static void kiem_thu(const int *a, size_t n, const char *mo_ta)
{
    int kq;

    if (lon_thu_hai(a, n, &kq) == 0) {
        printf("%-24s -> %d\n", mo_ta, kq);
    } else {
        printf("%-24s -> không có\n", mo_ta);
    }
}

int main(void)
{
    kiem_thu((int[]){3,1,4,1,5,9,2,6}, 8, "bình thường");
    kiem_thu((int[]){1,2},             2, "n = 2");
    kiem_thu((int[]){5},               1, "n = 1");
    kiem_thu((int[]){5,5,5},           3, "mọi phần tử bằng nhau");
    kiem_thu((int[]){3,3,1},           3, "lớn nhất lặp lại");
    kiem_thu((int[]){-5,-2,-9},        3, "toàn số âm");

    return 0;
}

Chú ý là bộ kiểm thử này chính là bảng ví dụ đã lập ở bước 2. Đó là phần thưởng của việc làm bước 2 nghiêm túc: bạn có sẵn bộ ca kiểm thử mà không phải nghĩ thêm.

#Ba sai lầm phổ biến

Sai lầm 1: gõ trước, hiểu sau

Sai lầm 2: tối ưu quá sớm

Sai lầm 3: bỏ qua trường hợp biên

Phần lớn lỗi trong chương trình thật nằm ở biên chứ không nằm ở luồng chính. Danh sách biên cần kiểm tra gần như giống nhau ở mọi bài toán:

• Dữ liệu rỗng, tức n bằng 0
• Chỉ có một phần tử
• Mọi phần tử bằng nhau
• Số âm, số 0, giá trị lớn nhất và nhỏ nhất của kiểu
• Dữ liệu đã sắp xếp sẵn, và dữ liệu sắp xếp ngược
• Kích thước tối đa mà đề cho phép