Bài 7.314 phút đọc

Mã giả

Sau bài này bạn sẽ làm được

Viết mã giả theo bộ quy ước thống nhất
Chuyển mã giả thành mã C và ngược lại
Biết mức chi tiết nào là vừa đủ cho mã giả
Giải thích vì sao viết mã giả trước lại tiết kiệm thời gian

Mã giả là cách viết thuật toán bằng tiếng Việt có cấu trúc, đủ rõ để người khác cài đặt được nhưng không vướng cú pháp của bất kỳ ngôn ngữ nào. Nó là bước 4 trong quy trình sáu bước, và là bước tách việc nghĩ ra khỏi việc gõ.

#Vì sao viết mã giả

Khi viết mã C, bạn phải làm hai việc khó cùng lúc: nghĩ ra thuật toán, và diễn đạt nó đúng cú pháp. Mã giả tách hai việc đó ra.

Lợi ích	Cụ thể
Tập trung vào logic	Không phải lo dấu chấm phẩy, kiểu dữ liệu, hay cấp phát bộ nhớ
Phát hiện lỗi sớm	Sai logic lộ ra khi mã giả chỉ dài 10 dòng, chứ không phải khi mã C đã 200 dòng
Trao đổi được với người khác	Người không biết C vẫn đọc và góp ý được
Dùng lại cho nhiều ngôn ngữ	Cùng một mã giả cài được bằng C, Python hay bất kỳ ngôn ngữ nào
Thành tài liệu	Sáu tháng sau đọc lại vẫn hiểu ý tưởng, trong khi đọc mã C thì phải lần từng dòng

#Quy ước của khóa học

Ký hiệu	Nghĩa	Tương ứng trong C
BẮT ĐẦU, KẾT THÚC	Mốc đầu và cuối	Thân hàm main
ĐỌC x	Nhập dữ liệu vào	fgets kèm strtol
IN x	Xuất kết quả ra	printf
x ← 5	Gán giá trị	x = 5;
NẾU đk THÌ ... HẾT NẾU	Rẽ nhánh	if (...) { }
NGƯỢC LẠI	Nhánh còn lại	else
TRONG KHI đk LÀM ... HẾT TRONG KHI	Lặp có điều kiện	while
VỚI i TỪ a ĐẾN b LÀM ... HẾT VỚI	Lặp có biến đếm	for
VỚI MỖI x TRONG A LÀM	Duyệt từng phần tử	for theo chỉ số
TRẢ VỀ x	Trả kết quả về	return x;
HÀM ten(tham_so)	Định nghĩa hàm	kiểu ten(tham_so)
HOÁN ĐỔI a VÀ b	Đổi chỗ hai giá trị	Ba dòng dùng biến tạm

#Ví dụ đầy đủ

Ví dụ 1: sắp xếp nổi bọt

HÀM sap_xep_noi_bot(A, n)
    VỚI i TỪ 0 ĐẾN n-2 LÀM
        da_doi ← SAI

        VỚI j TỪ 0 ĐẾN n-2-i LÀM
            NẾU A[j] > A[j+1] THÌ
                HOÁN ĐỔI A[j] VÀ A[j+1]
                da_doi ← ĐÚNG
            HẾT NẾU
        HẾT VỚI

        NẾU da_doi = SAI THÌ
            DỪNG        // mảng đã có thứ tự, không cần duyệt tiếp
        HẾT NẾU
    HẾT VỚI
HẾT HÀM

Dịch sang C gần như là việc máy móc:

noi-bot.c

void sap_xep_noi_bot(int a[], size_t n)
{
    for (size_t i = 0; i + 1 < n; ++i) {
        int da_doi = 0;

        for (size_t j = 0; j + 1 < n - i; ++j) {
            if (a[j] > a[j + 1]) {
                int t = a[j];

                a[j] = a[j + 1];
                a[j + 1] = t;
                da_doi = 1;
            }
        }

        if (!da_doi) {
            break;
        }
    }
}

Ví dụ 2: tìm kiếm nhị phân

HÀM tim_nhi_phan(A, n, x)
    // Yêu cầu: A đã được sắp xếp tăng dần
    trai  ← 0
    phai  ← n - 1

    TRONG KHI trai <= phai LÀM
        giua ← trai + (phai - trai) / 2

        NẾU A[giua] = x THÌ
            TRẢ VỀ giua
        NGƯỢC LẠI NẾU A[giua] < x THÌ
            trai ← giua + 1
        NGƯỢC LẠI
            phai ← giua - 1
        HẾT NẾU
    HẾT TRONG KHI

    TRẢ VỀ -1        // không tìm thấy
HẾT HÀM

Ví dụ 3: đếm từ trong một dòng

HÀM dem_tu(dong)
    so_tu       ← 0
    dang_trong_tu ← SAI

    VỚI MỖI c TRONG dong LÀM
        NẾU c là khoảng trắng THÌ
            dang_trong_tu ← SAI
        NGƯỢC LẠI
            NẾU dang_trong_tu = SAI THÌ
                so_tu ← so_tu + 1
                dang_trong_tu ← ĐÚNG
            HẾT NẾU
        HẾT NẾU
    HẾT VỚI

    TRẢ VỀ so_tu
HẾT HÀM

Mã giả này cho thấy rõ ý tưởng cốt lõi: đếm số lần chuyển từ ngoài từ vào trong từ, chứ không đếm khoảng trắng. Nhìn mã C thì ý tưởng đó bị lẫn trong chi tiết cú pháp.

#Mức chi tiết vừa đủ

Đây là chỗ người mới hay sai theo cả hai hướng: quá sơ sài thành vô dụng, hoặc quá chi tiết thành viết C bằng tiếng Việt.

Quá sơ sài

HÀM sap_xep(A, n)
    Sắp xếp mảng A cho có thứ tự
HẾT HÀM

// Không nói làm thế nào. Người đọc không cài đặt được.

Vừa đủ

HÀM sap_xep(A, n)
    VỚI i TỪ 0 ĐẾN n-2 LÀM
        vi_tri_nho_nhat ← i

        VỚI j TỪ i+1 ĐẾN n-1 LÀM
            NẾU A[j] < A[vi_tri_nho_nhat] THÌ
                vi_tri_nho_nhat ← j
            HẾT NẾU
        HẾT VỚI

        HOÁN ĐỔI A[i] VÀ A[vi_tri_nho_nhat]
    HẾT VỚI
HẾT HÀM

Quá chi tiết

HÀM dao_chuoi(s)
    KHAI BÁO size_t i KIỂU KHÔNG DẤU
    KHAI BÁO size_t j KIỂU KHÔNG DẤU
    KHAI BÁO char t KIỂU KÝ TỰ
    i ← 0
    j ← strlen(s) - 1
    ...

// Đây là viết C bằng tiếng Việt, không còn lợi ích gì.

Bỏ chi tiết kỹ thuật

HÀM dao_chuoi(s)
    trai  ← đầu chuỗi
    phai  ← cuối chuỗi

    TRONG KHI trai < phai LÀM
        HOÁN ĐỔI s[trai] VÀ s[phai]
        trai ← trai + 1
        phai ← phai - 1
    HẾT TRONG KHI
HẾT HÀM

Những thứ mã giả nên bỏ qua

Khai báo kiểu dữ liệu cụ thể
Cấp phát và giải phóng bộ nhớ
Chi tiết cú pháp như dấu chấm phẩy hay ngoặc nhọn
Xử lý lỗi thường quy, ví dụ kiểm tra con trỏ rỗng
Tối ưu vi mô, ví dụ dùng phép dịch bit thay phép chia

Những thứ mã giả bắt buộc phải có

Điều kiện tiên quyết, ví dụ mảng phải đã sắp xếp
Trường hợp biên được xử lý ra sao
Giá trị trả về trong mọi nhánh
Ý nghĩa của từng biến, nếu tên chưa đủ rõ

Tự làm thử

Viết mã giả cho thuật toán Euclid tìm ước chung lớn nhất, rồi dịch sang C.
Viết mã giả cho bài toán kiểm tra một số có phải số nguyên tố không, có ghi rõ điều kiện tiên quyết và trường hợp biên.
Cho đoạn mã C bất kỳ trong Chương 6, viết ngược lại thành mã giả.
Viết mã giả cho bài toán gộp hai mảng đã sắp xếp thành một mảng sắp xếp, rồi đưa cho bạn cùng lớp cài đặt mà không giải thích thêm. Nếu họ phải hỏi lại thì mã giả của bạn chưa đủ rõ.
Viết mã giả cho bài toán tìm số lớn thứ hai ở Bài 7.1, so sánh với bản đã có trong bài đó.

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

Mã giả tách việc nghĩ thuật toán ra khỏi việc viết đúng cú pháp.
Không có chuẩn chính thức, quan trọng là nhất quán và đủ rõ để người khác cài đặt được.
Thụt lề thể hiện cấu trúc vì mã giả không có ngoặc nhọn.
Bỏ qua kiểu dữ liệu, cấp phát bộ nhớ và cú pháp. Giữ lại điều kiện tiên quyết và trường hợp biên.
Thước đo: người biết lập trình nhưng chưa nghe bài toán vẫn cài đặt được mà không cần hỏi.