Chuyển tới nội dung chính

BÀI 2. CƠ BẢN VỀ GIẢI THUẬT

Mục tiêu​

Sau bài này, học viên:

  • Phát biểu được thuật toán và năm tính chất: đầu vào, đầu ra, xác định, hữu hạn, hiệu quả.
  • Biểu diễn được cùng một thuật toán bằng ngôn ngữ tự nhiên, mã giả và lưu đồ.
  • Nhận diện được ba cấu trúc điều khiển: tuần tự, rẽ nhánh, lặp — ở mức ý tưởng, trước khi học cú pháp C ở Bài 4 và Bài 5.
  • Đánh giá được tính đúng bằng ca kiểm thử, tiền điều kiện và hậu điều kiện.
  • Ước lượng được chi phí bằng ý niệm bậc tăng (hằng, tuyến tính, bậc hai, logarit) mà chưa cần chứng minh hình thức.
  • Thiết kế được các thuật toán nền: hoán đổi, tìm max, đếm, Euclid, kiểm tra nguyên tố, tìm kiếm tuyến tính và ý tưởng tìm kiếm nhị phân.
  • Ở mức cao thủ: nói được bất biến vòng lặp là gì, và vì sao một thuật toán “chạy ra kết quả đúng vài lần” chưa phải là thuật toán đúng.

Cú pháp if, while, mảng sẽ được chuẩn hóa ở các bài sau. Mã C trong bài này là hiện thực để quan sát thuật toán, kèm chú thích. Khi đọc, hãy nhìn lưu đồ trước, nhìn code sau.

1. Thuật toán là gì​

Thuật toán là một dãy bước xử lý hữu hạn, được mô tả rõ đến mức một người hoặc một máy có thể thực hiện mà không phải đoán, để đưa dữ liệu vào hợp lệ thành dữ liệu ra đúng yêu cầu.

Donald Knuth nêu các tính chất dùng được trong thực hành:

Tính chấtÝ nghĩaPhản ví dụ
Đầu vàoCó tập dữ liệu đưa vào, có thể rỗng“Giải phương trình” nhưng không nói hệ số nào
Đầu raCó kết quả xác định với mỗi đầu vào hợp lệLàm một hồi rồi không nói đáp án
Xác địnhMỗi bước có một nghĩa duy nhất“Chọn một số cho đẹp”
Hữu hạnDừng sau một số bước hữu hạn“Cứ thử mãi đến khi nào đúng thì thôi” nếu không chứng minh được sẽ tới
Hiệu quảMỗi bước đủ sơ cấp để thực hiện được“Hãy tìm nghiệm” mà không có bước tìm

Tính xác định không có nghĩa là cấm lựa chọn. Nó có nghĩa là luật lựa chọn phải rõ. “Nếu delta âm thì vô nghiệm” là xác định. “Nếu thấy khó thì làm cách khác” là không xác định.

Thuật toán khác chương trình. Thuật toán đứng trước ngôn ngữ. Chương trình là thuật toán viết bằng C, đã chọn kiểu dữ liệu, đã chấp nhận giới hạn của máy (số nguyên không vô hạn, số thực không chính xác tuyệt đối). Một thuật toán đúng vẫn có thể thành chương trình sai nếu hiện thực làm méo dữ liệu. Ngược lại, chương trình dịch được vẫn có thể hiện thực một thuật toán sai.

2. Ba cách biểu diễn​

2.1. Ngôn ngữ tự nhiên​

Dùng khi trao đổi với người chưa đọc code. Nguy cơ là nhập nhằng. Mỗi câu phải có chủ ngữ là một thao tác.

2.2. Mã giả (pseudo-code)​

Trộn tiếng Việt có cấu trúc với phép gán và các khối NẾU, LẶP. Không cần dấu chấm phẩy. Không cần đúng một ngôn ngữ. Mục đích là hết mơ hồ trước khi đụng cú pháp.

Quy ước mã giả của khóa học:

THUẬT TOÁN Tên(đầu vào)
    tiền điều kiện: ...
    Bước xử lý
    TRẢ VỀ kết quả
    hậu điều kiện: ...

2.3. Lưu đồ (flowchart)​

Ký hiệu dùng thống nhất trong toàn bộ 8 bài:

Ký hiệuÝ nghĩa
Hình tròn / stadiumBắt đầu, kết thúc
Hình chữ nhậtXử lý, gán
Hình thoiĐiều kiện, đúng một câu hỏi có/không
Hình bình hànhNhập hoặc xuất
Mũi tênThứ tự thực hiện, không nhảy tùy tiện
Hình tròn nhỏ có chữ hoặc sốBộ nối: chỗ lưu đồ sang trang khác hoặc nhập lại một nhánh ở xa. Hai vòng tròn cùng nhãn là một đường nối

Quy tắc vẽ dùng trong cả khóa:

  • Đúng một điểm bắt đầu và một điểm kết thúc cho một thuật toán.
  • Luồng đi từ trên xuống, trái sang phải khi có nhánh.
  • Mỗi hình thoi có đủ lối Có và lối Không.
  • Không để mũi tên đâm vào giữa một hình mà không vào đỉnh.

Mã giả của môn dùng các từ này, viết hoa để khỏi lẫn với câu tiếng Việt:

TừNghĩa
BEGIN / ENDBắt đầu và kết thúc thuật toán
INPUT / READNhận dữ liệu
DISPLAY / WRITEĐưa dữ liệu ra
← hoặc =Gán
NẾU / NGƯỢC LẠIRẽ nhánh
LẶP KHILặp

Một hình thoi chỉ chứa một điều kiện. “a = 0 và b = 0” phải được tách hoặc viết thành một vị từ rõ, không nhét cả bài giải vào trong hình thoi.

Ba cấu trúc đủ để diễn mọi thuật toán (định lý Böhm–Jacopini), nên lưu đồ không cần mũi tên rối:

  1. Tuần tự. Bước sau bắt đầu khi bước trước xong.
  2. Rẽ nhánh. Chọn một nhánh theo điều kiện. Các nhánh hội tụ lại nếu còn việc chung.
  3. Lặp. Lặp một khối khi điều kiện còn đúng, hoặc lặp đến khi điều kiện dừng. Phải chỉ ra thứ thay đổi để vòng lặp tiến tới điểm dừng.

3. Tính đúng, bất biến, kiểm thử​

Tiền điều kiện là những gì phải đúng trước khi thuật toán chạy. Hậu điều kiện là những gì đúng sau khi nó dừng, nếu tiền điều kiện được thỏa.

Ví dụ thuật toán trị tuyệt đối của số nguyên x:

  • Tiền điều kiện: x là số nguyên trong phạm vi biểu diễn.
  • Hậu điều kiện: kết quả không âm và bằng x nếu x >= 0, bằng -x nếu x < 0.

Bất biến vòng lặp là mệnh đề đúng trước mỗi lần lặp và vẫn đúng sau mỗi lần lặp. Khi vòng kết thúc, bất biến cộng với điều kiện dừng suy ra hậu điều kiện. Đây là công cụ của người viết thuật toán, không phải bình luận trang trí.

Kiểm thử không chứng minh cho mọi đầu vào, nhưng nó giết các thuật toán sai rất nhanh nếu chọn đúng ca:

  • Ca điển hình: dữ liệu “đẹp”.
  • Ca biên: 0, 1, rỗng, giá trị sát ngưỡng.
  • Ca đối xứng hoặc đảo: thứ tự ngược, hai phần tử bằng nhau.
  • Ca không hợp lệ: vi phạm tiền điều kiện, chương trình phải từ chối chứ không được bịa kết quả.

4. Chi phí: nhìn quy mô, đừng nhìn một lần chạy​

Độ phức tạp thời gian ước lượng số bước sơ cấp khi kích thước đầu vào là n. Độ phức tạp bộ nhớ ước lượng số ô nhớ phụ.

Các bậc gặp trong khóa này:

BậcTên gọi thân mậtVí dụ ở các bài sau
O(1)HằngHoán đổi ba dòng gán
O(log n)Lô-ga-rítTìm kiếm nhị phân, Euclid
O(n)Tuyến tínhTìm max trong n phần tử
O(n log n)Tuyến tính-logaritSắp xếp tốt, Bài 7
O(n²)Bậc haiHai vòng lặp lồng nhau trên n phần tử

Quy tắc thực hành: một vòng lặp chạy n lần, mỗi lần một việc hằng, là O(n). Hai vòng lồng nhau mỗi vòng n lần là O(n²). Chia đôi miền tìm ở mỗi bước là O(log n).

Bậc không thay thế đo thời gian thật. Nó nói cách thời gian tăng khi dữ liệu lớn lên. Một thuật toán O(n²) có thể nhanh hơn O(n) khi n = 3. Nó sẽ thua khi n là một triệu.

5. Ví dụ​

Ví dụ 2.1 — Hoán đổi hai giá trị​

Phân tích. Cho a và b. Sau thuật toán, a giữ giá trị cũ của b và ngược lại. Không được “hoán đổi trên giấy” bằng cách chỉ đổi chỗ in. Phải đổi dữ liệu.

Gán thẳng a = b sẽ làm mất giá trị cũ của a. Cần một chỗ nhớ phụ t.

  • Tiền điều kiện: a, b đã có giá trị.
  • Hậu điều kiện: a' = b và b' = a với a, b là giá trị ban đầu.
  • Chi phí: O(1) thời gian, O(1) bộ nhớ phụ.

Mã giả.

THUẬT TOÁN HoánĐổi(a, b)
    t ← a
    a ← b
    b ← t

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int a;
    int b;
    int t;

    printf("a = ");
    if (scanf("%d", &a) != 1) {
        return 1;
    }
    printf("b = ");
    if (scanf("%d", &b) != 1) {
        return 1;
    }

    t = a;
    a = b;
    b = t;

    printf("Sau hoan doi: a = %d, b = %d\n", a, b);
    return 0;
}

Kết quả với a = 7, b = 4.

a = 7
b = 4
Sau hoan doi: a = 4, b = 7

Phân tích chi tiết. Thứ tự ba phép gán là một phần của thuật toán. Đổi thành b = t trước khi t kịp nhận a thì mất dữ liệu. Hãy giả lập trên giấy với 7 và 4 trước khi tin code. Đây là thuật toán tuần tự thuần: không rẽ nhánh, không lặp.

Ví dụ 2.2 — Tìm số lớn hơn trong hai số​

Phân tích. Đầu ra là số không nhỏ hơn số còn lại. Khi hai số bằng nhau, số nào in ra cũng thỏa “lớn hơn hoặc bằng”. Cần nói rõ trong đặc tả để khỏi cãi kết quả.

Mã giả.

THUẬT TOÁN Max2(a, b)
    NẾU a >= b THÌ
        TRẢ VỀ a
    NGƯỢC LẠI
        TRẢ VỀ b

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int a;
    int b;

    printf("a b: ");
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }

    if (a >= b) {
        printf("So lon hon hoac bang: %d\n", a);
    } else {
        printf("So lon hon hoac bang: %d\n", b);
    }
    return 0;
}

Kết quả.

a b: 3 9
So lon hon hoac bang: 9
a b: 5 5
So lon hon hoac bang: 5

Phân tích chi tiết. Hình thoi có hai lối ra và cả hai đều tới kết thúc. Không có nhánh “treo”. Ca 5 5 kiểm tra dấu >=. Nếu viết > thì nhánh bằng rơi xuống else và vẫn in 5, kết quả tình cờ đúng. Ca biên bằng nhau không đủ để phân biệt > và >= ở bài này vì cả hai cùng in một giá trị. Muốn phân biệt, bài toán phải yêu cầu chỉ số của số được chọn. Ghi nhớ: bộ kiểm thử phải có khả năng làm lộ chỗ sai, không chỉ “ra số đẹp”.

Ví dụ 2.3 — Cộng dồn 1 + 2 + … + n​

Phân tích. Với n >= 0, tính tổng các số nguyên từ 1 đến n. Khi n = 0, tổng là 0 theo quy ước tổng rỗng.

Có hai thuật toán:

  • Duyệt: khởi tạo s = 0, lần lượt cộng 1, 2, …, n. Chi phí O(n).
  • Công thức Gauss: s = n * (n + 1) / 2. Chi phí O(1).

Cả hai cùng hậu điều kiện nếu số học không tràn. Bài này hiện thực thuật toán duyệt vì mục tiêu là vòng lặp. Công thức là đối chứng kiểm thử.

Bất biến: trước mỗi lần xét số k, s bằng tổng các số nguyên từ 1 đến k - 1. Khi k vượt n, s là tổng cần tìm.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int n;
    int k;
    int s;

    printf("n = ");
    if (scanf("%d", &n) != 1 || n < 0) {
        printf("n phai la so nguyen khong am.\n");
        return 1;
    }

    s = 0;
    k = 1;
    while (k <= n) {
        s = s + k;
        k = k + 1;
    }

    printf("Tong = %d\n", s);
    return 0;
}

Kết quả.

n = 4
Tong = 10
n = 0
Tong = 0

Phân tích chi tiết. Với n = 4, bảng bất biến:

Trước lần lặpksÝ nghĩa
110chưa cộng số nào
221đã cộng 1
333đã cộng 1+2
446đã cộng 1+2+3
Dừng510k > 4, s = 1+2+3+4

Nếu quên k = k + 1, điều kiện k <= n không bao giờ đổi: vi phạm tính hữu hạn. Nếu đặt k = 0 và cộng k trước khi tăng, tổng dính số 0, vẫn đúng về giá trị nhưng thuật toán lệch so với đặc tả “từ 1 đến n”. Đối chứng: 4 * 5 / 2 = 10.

Ví dụ 2.4 — Thuật toán Euclid tìm ước chung lớn nhất​

Phân tích. Ước chung lớn nhất của hai số nguyên không âm, không đồng thời bằng 0. Euclid: gcd(a, b) = gcd(b, a mod b) cho đến khi số dư bằng 0. Khi số dư bằng 0, số chia chính là ước chung lớn nhất.

  • Tiền điều kiện: a >= 0, b >= 0, (a, b) != (0, 0).
  • Hậu điều kiện: kết quả dương và là ước chung lớn nhất.
  • Chi phí: O(log min(a, b)) bước, rất nhanh so với việc thử mọi ước.

Bất biến: gcd(a, b) không đổi sau mỗi lần thay (a, b) bằng (b, a % b).

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int a;
    int b;
    int r;

    printf("a b: ");
    if (scanf("%d %d", &a, &b) != 2 || a < 0 || b < 0 || (a == 0 && b == 0)) {
        printf("Du lieu khong hop le.\n");
        return 1;
    }

    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }

    printf("UCLN = %d\n", a);
    return 0;
}

Kết quả.

a b: 48 18
UCLN = 6

Các bước: (48, 18) → (18, 12) → (12, 6) → (6, 0). Dừng, kết quả 6.

Phân tích chi tiết. Bộ ước của 48 là 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Bộ ước của 18 là 1, 2, 3, 6, 9, 18. Ước chung lớn nhất đúng là 6. Ca (0, 5) cho kết quả 5: mọi ước của 5 đều ước của 0, nên UCLN là 5. Ca (0, 0) bị loại vì mọi số khác 0 đều là ước của 0, không có số lớn nhất. Đây là chỗ đặc tả quan trọng hơn code.

Ví dụ 2.5 — Kiểm tra số nguyên tố​

Phân tích. Số nguyên tố là số nguyên lớn hơn 1, chỉ có hai ước dương là 1 và chính nó. 0 và 1 không nguyên tố. Số âm không xét trong bài này.

Thuật toán thử ước từ 2 đến căn bậc hai của n. Nếu có ước thì không nguyên tố. Không cần thử quá căn, vì nếu n = p * q với p <= q thì p <= sqrt(n).

Chi phí O(sqrt(n)) phép chia, tốt hơn O(n) của việc thử đến n - 1.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int n;
    int d;
    int la_nguyen_to;

    printf("n = ");
    if (scanf("%d", &n) != 1) {
        return 1;
    }

    if (n < 2) {
        la_nguyen_to = 0;
    } else {
        la_nguyen_to = 1;
        d = 2;
        while (d * d <= n) {
            if (n % d == 0) {
                la_nguyen_to = 0;
                break;
            }
            d = d + 1;
        }
    }

    if (la_nguyen_to) {
        printf("%d la nguyen to\n", n);
    } else {
        printf("%d khong phai nguyen to\n", n);
    }
    return 0;
}

Kết quả.

n = 1
1 khong phai nguyen to
n = 29
29 la nguyen to
n = 49
49 khong phai nguyen to

Phân tích chi tiết. 49 = 7 × 7. Vòng lặp dừng đúng khi d = 7 vì 7 * 7 <= 49 và 49 % 7 == 0. Nếu điều kiện là d < n thì vẫn đúng nhưng làm khoảng sqrt(n) lần nhiều hơn cần thiết khi n lớn. break ở đây là tối ưu có chủ đích: đã có một ước thì hậu điều kiện “không nguyên tố” đã đạt, tiếp tục thử là thừa. Với n nguyên tố, không có ước nào, vòng chạy đến khi d * d > n.

Cảnh báo cao thủ: với n gần giới hạn int, biểu thức d * d có thể tràn trước khi so sánh. Bản làm chủ sẽ đổi điều kiện thành d <= n / d. Đó là chỗ thuật toán trên giấy (số nguyên toán học) khác thuật toán trên máy (số nguyên modulo giới hạn kiểu).

Ví dụ 2.6 — Tìm kiếm tuyến tính và ý tưởng tìm kiếm nhị phân​

Phân tích. Cho dãy đã đọc lần lượt và một giá trị x. Tìm vị trí đầu tiên của x, hoặc báo không có. Ở bài này dãy được nhập từng phần tử, chưa cần khai báo mảng (mảng là Bài 7). Ta vẫn nói được thuật toán trên một dãy logic.

Tìm tuyến tính: xét từ trái sang phải. Chi phí O(n). Không đòi hỏi dãy đã sắp.

Tìm nhị phân chỉ đúng khi dãy đã sắp tăng. Mỗi bước so x với phần tử giữa, bỏ một nửa. Chi phí O(log n). Dùng nhị phân trên dãy chưa sắp là thuật toán sai, dù code không báo lỗi.

Lưu đồ tìm tuyến tính trên n số nhập tuần tự.

Mã nguồn tìm tuyến tính.

#include <stdio.h>

int main(void)
{
    int n;
    int x;
    int i;
    int gia_tri;
    int vi_tri;

    printf("n x: ");
    if (scanf("%d %d", &n, &x) != 2 || n <= 0) {
        return 1;
    }

    vi_tri = 0;
    i = 1;
    while (i <= n && vi_tri == 0) {
        if (scanf("%d", &gia_tri) != 1) {
            return 1;
        }
        if (gia_tri == x) {
            vi_tri = i;
        }
        i = i + 1;
    }

    if (vi_tri == 0) {
        printf("Khong tim thay\n");
    } else {
        printf("Vi tri dau tien (tinh tu 1): %d\n", vi_tri);
    }
    return 0;
}

Kết quả với dãy 4 1 7 1 tìm 1.

n x: 4 1
4 1 7 1
Vi tri dau tien (tinh tu 1): 2

Phân tích chi tiết. Bất biến: mọi phần tử ở vị trí nhỏ hơn i đều khác x, và vi_tri vẫn 0. Khi gặp phần tử bằng x, ghi vị trí và điều kiện dừng. Phần tử 1 ở vị trí 4 không được chọn vì đề bài hỏi vị trí đầu tiên.

Tìm nhị phân, mã giả, để dành hiện thực mảng ở Bài 7:

THUẬT TOÁN TìmNhịPhân(a[1..n] đã sắp tăng, x)
    trai ← 1
    phai ← n
    LẶP KHI trai <= phai
        giua ← (trai + phai) / 2
        NẾU a[giua] = x THÌ TRẢ VỀ giua
        NẾU a[giua] < x THÌ trai ← giua + 1
        NGƯỢC LẠI phai ← giua - 1
    TRẢ VỀ không thấy

Bất biến: nếu x có trong dãy thì nó nằm trong đoạn trai..phai. Mỗi vòng đoạn co lại ít nhất một phần tử, nên hữu hạn. Khi trai > phai, đoạn rỗng, x không có.

6. Bài tập có gợi ý​

Bài 2.G1 — Trị tuyệt đối​

Viết mã giả, lưu đồ, rồi chương trình in trị tuyệt đối của một số nguyên.

Gợi ý. Một hình thoi x >= 0. Nhánh không thì giá trị cần in là -x. Ca bắt buộc: âm, dương, 0.

Bài 2.G2 — Phương trình bậc nhất bx + c = 0​

Gợi ý. Tách ba trường hợp: b != 0 thì một nghiệm x = -c / b; b == 0 và c == 0 thì vô số nghiệm; b == 0 và c != 0 thì vô nghiệm. Đừng chia khi b bằng 0. Vẽ lưu đồ trước.

Bài 2.G3 — Liệt kê số chẵn từ 0 đến n​

Gợi ý. Tiền điều kiện n >= 0. Có thể bước k = 0, 2, 4, ... chừng nào k <= n, đỡ phải kiểm tra chẵn từng số. Hữu hạn vì k tăng.

Bài 2.G4 — Tìm m lớn nhất sao cho 1 + 2 + … + m <= n​

Gợi ý. Cộng dồn đến khi thêm m + 1 sẽ vượt n thì dừng. Bất biến: s = 1 + … + m và s <= n. Đối chứng bằng công thức Gauss. Ca n = 0 và n = 1.

Bài 2.G5 — Giai thừa kép​

n!! = 1 * 3 * 5 * … * n nếu n lẻ, và 2 * 4 * 6 * … * n nếu n chẵn. Quy ước 0!! = 1.

Gợi ý. Bước giảm 2, không phải bước 1. Chứng minh hữu hạn bằng cách chỉ ra n giảm và dừng tại 0 hoặc số âm thì không nhân nữa. Viết lưu đồ có nhánh chẵn/lẻ để chọn điểm bắt đầu.

Bài 2.G6 — Vì sao nhị phân cần dãy đã sắp​

Lấy dãy 1 3 2 và x = 2. Giả lập tìm nhị phân “như thể đã sắp” và chỉ ra bước bỏ mất nghiệm. Sau đó giả lập trên dãy đã sắp 1 2 3.

Gợi ý. Viết từng vòng: trai, phai, giua. Không cần code.

7. Bài tập tự làm​

Cơ bản​

  1. Viết ngôn ngữ tự nhiên, mã giả và lưu đồ cho thuật toán tính trung bình cộng ba số thực.
  2. Thiết kế thuật toán xác định một năm dương lịch có phải năm nhuận không: chia hết cho 400, hoặc chia hết cho 4 nhưng không chia hết cho 100. Vẽ lưu đồ, hiện thực, kiểm thử các năm 1900, 2000, 2024, 2023.
  3. In các số nguyên tố từ 2 đến n (n > 1). Nêu chi phí nếu mỗi số đều thử ước đến căn bậc hai.

Vững​

  1. Giải phương trình bậc hai ax^2 + bx + c = 0 bằng lưu đồ đầy đủ, gồm trường hợp a = 0 thì quay về bậc nhất. Hiện thực và lập bảng kiểm thử tối thiểu 8 ca: vô nghiệm, một nghiệm, hai nghiệm, nghiệm kép, suy biến thành bậc nhất, vô số nghiệm, vô nghiệm bậc nhất, hệ số không đọc được.
  2. Tính n!! theo đề mục G5, có từ chối n âm.
  3. Nhập n rồi tìm m lớn nhất với 1 + … + m <= n. In cả m và tổng. Đối chiếu công thức.

Nâng cao​

  1. Đếm chữ số và tổng chữ số của một số nguyên không âm. Thuật toán lặp: chia 10 lấy dư để lấy chữ số hàng đơn vị, chia nguyên cho 10 để bỏ hàng đó. Bất biến phải được viết ra. Ca 0 phải cho 1 chữ số, tổng 0. Nêu vì sao n = 0 là ca biên dễ sai.
  2. Phân tích thừa số nguyên tố. Với n > 1, in các thừa số nguyên tố theo thứ tự tăng, lặp lại nếu có mũ. Ví dụ 84 in 2 2 3 7. Chứng minh thuật toán dừng. Ước lượng số phép chia trong trường hợp xấu.
  3. Sàng Eratosthenes bằng lời cho các số đến n, chưa cần mảng: mô tả ý tưởng gạch bội số, độ phức tạp O(n log log n), và vì sao nó tốt hơn việc kiểm tra từng số. Việc hiện thực để Bài 7. Bài này nộp mã giả và một bảng giả lập với n = 30.

Siêu khó, có ứng dụng​

  1. Lịch sử dụng pin. Một thiết bị mỗi ngày tiêu thụ một số nguyên dương đơn vị pin, pin ban đầu là p, cần hoạt động d ngày. Thuật toán quyết định pin có đủ không. Nếu không, tính ngày đầu tiên bị cạn. Viết tiền điều kiện, hậu điều kiện, bất biến, lưu đồ, chương trình, và 6 ca kiểm thử. Đây là dạng bài “mô phỏng tiến tới sự kiện” rất hay gặp trong lập trình nhúng.
  2. Đối chiếu hai thuật toán UCLN. Hiện thực Euclid và hiện thực thử từ min(a, b) đi xuống. Với cặp (1, 1), (48, 18), (1000000, 2), đếm số vòng mỗi thuật toán chạy. Giải thích bậc. Không cần đo mili-giây; số vòng là số liệu đủ.
  3. Thuật toán gần đúng có điều kiện dừng. Tính căn bậc hai của s > 0 bằng Newton: bắt đầu x = s, lặp x = (x + s / x) / 2 cho đến khi hai lần lặp liên tiếp chênh nhau dưới 0.000001. Viết bất biến không hình thức (“x dương và đang tiến tới căn”), lưu đồ, chương trình. Đối chiếu s = 2 với giá trị bạn tính bằng máy tính cầm tay. Phân tích vì sao điều kiện dừng kiểu “sai số nhỏ” khác điều kiện dừng kiểu “đếm đủ n lần”, và ca nào có thể lặp rất lâu nếu ngưỡng quá nhỏ so với độ chính xác số thực của máy.

8. Câu hỏi tự kiểm​

  1. Một vòng lặp while (1) có thể là thuật toán hợp lệ không? Điều kiện nào cứu tính hữu hạn?
  2. Vì sao “thử mọi khả năng đến khi đúng” chưa đủ để gọi là thuật toán?
  3. O(n²) và O(n) cái nào nhanh hơn khi n = 10? Câu này có một bẫy.
  4. Tìm nhị phân trên dãy chưa sắp vi phạm tính chất nào: xác định, hữu hạn, hay tính đúng so với hậu điều kiện?
  5. Viết bất biến của Euclid sau mỗi lần thay bộ số.

9. Tóm tắt và cầu nối​

Thuật toán là dãy bước xác định, hữu hạn, làm được, có đầu vào và đầu ra. Biểu diễn bằng lời, mã giả, lưu đồ trước khi viết C. Ba cấu trúc tuần tự, rẽ nhánh, lặp là đủ về mặt thiết kế. Tính đúng được nói bằng tiền điều kiện, hậu điều kiện, bất biến. Chi phí được nói bằng bậc tăng.

Bài 3 trang bị vật liệu của ngôn ngữ C: từ khóa, tên, kiểu, biến, hằng, biểu thức, toán tử, printf và scanf. Từ bài đó, lưu đồ mới được dịch sang cú pháp một cách hệ thống.

10. Đào sâu: tính đúng không nằm ở một lần chạy​

Một thuật toán đúng là một khẳng định về mọi đầu vào thỏa tiền điều kiện, không phải về ví dụ trong đầu người viết. Ba công cụ kiểm khẳng định đó, từ yếu đến mạnh:

  1. Ca kiểm thử. Giết thuật toán sai nhanh. Không chứng minh thuật toán đúng.
  2. Bất biến. Một câu luôn đúng tại một điểm trong vòng lặp. Khi vòng dừng, bất biến cộng điều kiện dừng suy ra hậu điều kiện.
  3. Phản ví dụ. Một đầu vào hợp lệ mà kết quả sai. Một phản ví dụ đủ giết cả thuật toán. Không cần mười phản ví dụ.

Mẫu viết bất biến cho vòng while:

Trước mỗi lần kiểm tra điều kiện:
    bất biến đúng
Nếu điều kiện đúng:
    thân vòng biến trạng thái nhưng khôi phục bất biến
Khi điều kiện sai:
    bất biến và phủ định điều kiện cho ra kết quả

Ví dụ tổng 1..n, bất biến là "s bằng tổng các số nguyên dương nhỏ hơn k". Khi k thành n+1, s là tổng cần tìm.

Chi phí phải nói kèm mô hình. "Nhanh" không phải bậc. O(n) là cách số bước tăng. Với n nhỏ, hệ số đứng trước có thể đảo thứ tự thực tế. Với n lớn, bậc thắng hệ số.

Ví dụ 2.7 — Đếm số lần Euclid chạy​

Phân tích. Cùng thuật toán Euclid, nhưng đầu ra không chỉ là ước, mà còn là số vòng. Mục tiêu là thấy O(log n) bằng số liệu, không bằng cảm giác. Cặp xấu của Euclid là hai số Fibonacci liên tiếp: số vòng lớn so với độ lớn của số.

Lưu đồ.

Mã nguồn.

#include <stdio.h>

int main(void)
{
    int a, b, r, vong = 0;
    if (scanf("%d %d", &a, &b) != 2 || a < 0 || b < 0 || (a == 0 && b == 0)) {
        return 1;
    }
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
        vong++;
    }
    printf("UCLN = %d, so vong = %d\n", a, vong);
    return 0;
}

Kết quả. Đầu vào 48 18 in UCLN = 6, so vong = 3. Ba bước là (48,18) → (18,12) → (12,6) → (6,0).

Phân tích chi tiết. Ba vòng cho hai số hàng chục. Thuật toán thử mọi ước từ min(a,b) đi xuống có thể mất 18 vòng trên cùng cặp này. Đó là bằng chứng bậc, không cần đồng hồ. Hãy tự chạy cặp Fibonacci 89 55 và đếm vòng.

11. Bài tập mở rộng​

Dễ​

  1. Viết mã giả và lưu đồ cho "in hiệu của hai số, hiệu luôn không âm".
  2. Chỉ ra tiền điều kiện và hậu điều kiện của phép chia nguyên a / b.
  3. Cho vòng k = 0; while (k < 3) k = k + 1. Liệt kê giá trị k trước mỗi lần kiểm tra.

Vừa​

  1. Thiết kế thuật toán đổi một số giây thành giờ, phút, giây. Vẽ lưu đồ có nhánh từ chối số âm.
  2. Viết bất biến cho vòng tính giai thừa: kq bằng tích các số từ 1 đến i-1.
  3. Tìm phản ví dụ cho phát biểu sai: "một số là nguyên tố nếu nó lẻ".

Khó​

  1. So sánh số vòng của Euclid và của thuật toán trừ dần (thay số lớn bằng hiệu hai số) trên cặp (100, 1).
  2. Viết lưu đồ đầy đủ giải phương trình bậc hai, gồm mọi nhánh suy biến. Chấm lưu đồ trước khi code: mỗi hình thoi chỉ một câu hỏi.

Siêu khó​

  1. Thuật toán gần đúng tính căn bằng cách thử x = 0, 1, 2, ... cho đến khi x * x vượt s, rồi trả x - 1 nếu s không chính phương. Viết bất biến, chứng minh dừng khi s >= 0, và chỉ ra vì sao nó kém Newton về số bước.
  2. Một máy bán hàng trả tiền thối bằng các mệnh giá 10, 5, 1. Thuật toán tham: lấy càng nhiều tờ lớn càng tốt. Vẽ lưu đồ. Chứng minh với bộ mệnh giá này thuật toán đúng. Nêu một bộ mệnh giá giả (3 và 4, cần trả 6) mà tham lam sai.

Dự án thật​

  1. Quy trình nhận yêu cầu. Chọn một việc thật trong nhà bạn: tính tiền điện cả nhà trong một tháng, hoặc chia tiền đi chợ. Viết đặc tả một trang, lưu đồ một trang, bộ 8 ca gồm ca biên. Chưa cần chương trình đẹp. Bài nộp là đặc tả và lưu đồ. Người khác trong nhóm phải chạy lưu đồ bằng tay trên 2 ca mà không cần hỏi lại bạn.

Bộ 25 bài tập​

  1. Viết bằng lời thường các bước tính tổng hai số. Gợi ý: Mỗi bước một câu, có thứ tự.
  2. Viết mã giả BEGIN/END cho bài in Hello. Gợi ý: BEGIN, DISPLAY, END. Chuỗi nằm trong nháy.
  3. Vẽ lưu đồ một đường thẳng: nhập một số, in gấp đôi. Gợi ý: Một hình bắt đầu, một hình nhập, một hình xử lý, một hình xuất, một hình kết thúc.
  4. Chỉ ra đầu vào và đầu ra của bài tìm số lớn hơn trong hai số. Gợi ý: Đầu vào hai số. Đầu ra một số không nhỏ hơn số kia.
  5. Cho vòng tăng k từ 1 đến 3. Liệt kê giá trị k trước mỗi lần kiểm tra. Gợi ý: Viết bảng k trước mỗi lần hỏi k < 3.
  6. Tìm một phản ví dụ cho câu "số lẻ là số nguyên tố". Gợi ý: 9 là lẻ nhưng không nguyên tố.
  7. Viết tiền điều kiện và hậu điều kiện của trị tuyệt đối. Gợi ý: Nếu x >= 0 thì kết quả là x, ngược lại là -x.
  8. Vẽ hình thoi cho câu hỏi "n có âm không" với hai lối ra. Gợi ý: Lối Có và lối Không đều phải có mũi tên.
  9. Mã giả và lưu đồ đổi giây thành giờ, phút, giây. Có nhánh từ chối số âm. Gợi ý: Chia nguyên cho 3600 và 60. Hình thoi chặn số âm đứng trước phép chia.
  10. Lưu đồ năm nhuận. Kiểm thử trên giấy các năm 1900, 2000, 2024, 2023. Gợi ý: Nhuận khi chia hết 400, hoặc chia hết 4 nhưng không chia hết 100.
  11. Viết bất biến của tổng 1 + 2 + … + k. Gợi ý: Trước khi cộng k, s đã là tổng các số nhỏ hơn k.
  12. Giả lập Euclid với cặp (48, 18) và đếm số vòng. Gợi ý: Ba lần dư: 12, 6, rồi 0.
  13. Giả lập tìm nhị phân trên dãy chưa sắp 1 3 2 để tìm 2, chỉ ra bước bỏ mất nghiệm. Gợi ý: Ghi trai, phai, giua từng vòng. Chỉ ra vòng đã bỏ mất số 2.
  14. Mã giả tìm m lớn nhất sao cho 1+…+m <= n. Gợi ý: Cộng dần đến khi thêm số sau sẽ vượt n thì dừng.
  15. So sánh số bước của Euclid và của việc trừ dần trên cặp (100, 1). Gợi ý: Trừ dần với (100,1) mất khoảng 100 bước. Euclid rất ít bước.
  16. Vẽ lưu đồ giải phương trình bậc hai, gồm trường hợp a = 0. Mỗi hình thoi một câu hỏi. Gợi ý: Nhánh a = 0 đi xuống bậc nhất. Không chia khi a và b cùng bằng 0.
  17. Thuật toán đếm chữ số của một số không âm. Ca 0 phải ra 1 chữ số. Viết bất biến. Gợi ý: Chia 10 lấy dư để lấy một chữ số. Số 0 cần một nhánh riêng.
  18. Mã giả phân tích thừa số nguyên tố của 84. Chứng minh thuật toán dừng. Gợi ý: Chia hết cho 2 thì in 2 và chia đôi, rồi tới 3, 7.
  19. Mô tả sàng Eratosthenes đến 30 bằng bảng gạch bội, chưa cần mảng trong code. Gợi ý: Gạch bội của 2, 3, 5. Số chưa gạch và lớn hơn 1 là nguyên tố.
  20. Hai thuật toán UCLN trên các cặp (1,1), (48,18), (1000000,2). Bảng số vòng. Nêu bậc. Gợi ý: Đếm vòng, đừng đo mili-giây. Fibonacci liên tiếp làm Euclid chạy nhiều vòng hơn.
  21. Căn gần đúng bằng cách tăng x đến khi x*x vượt s. Viết bất biến và nói vì sao kém Newton về số bước. Gợi ý: Dừng khi x*x > s. Số bước tỷ lệ với căn của s.
  22. Pin thiết bị. Pin ban đầu p, mỗi ngày tốn một đơn vị, cần chạy d ngày. Lưu đồ quyết định đủ pin hay cạn vào ngày nào. Sáu ca. Gợi ý: Mỗi ngày trừ 1. Ngày cạn là ngày bộ đếm chạm 0 trước khi đủ d.
  23. Tiền thối. Mệnh giá 10, 5, 1. Tham lam lấy tờ lớn trước. Vẽ lưu đồ. Nêu một bộ mệnh giá khác làm tham lam sai. Gợi ý: Với 6 và mệnh giá 4, 3, lấy tờ 4 trước sẽ kẹt.
  24. Quy trình một việc nhà. Chọn tính tiền điện hoặc chia tiền đi chợ. Nộp đặc tả một trang, lưu đồ một trang, 8 ca. Người khác phải đi được lưu đồ mà không hỏi lại. Gợi ý: Người khác cầm lưu đồ phải ra cùng một số với bạn trên hai ca.
  25. Đối soát thuật toán. Với bài tổng 1..n, viết cả thuật toán duyệt và công thức. Bảng 5 giá trị n gồm 0 và 1. Cột nào lệch thì thuật toán nào sai. Gợi ý: Cột công thức dùng n*(n+1)/2. Lệch ở n = 0 là lệch quy ước tổng rỗng.