Bỏ qua nội dung

Thiết kế thuật toán và giải quyết vấn đề

Khoa học máy tính A-Level · Chủ đề 9

Bài học video cho chủ đề này Mở trang video
14:30

Tư duy tính toán

Đây là một nhiệm vụ: xây dựng hệ thống quản lý tồn kho của cả một cửa hàng — mọi sản phẩm, mọi lần bán, mọi lô hàng, mọi báo cáo. Xét như một vấn đề lớn, nó quá to để…

Thuyết minh tiếng Anh · Có thể chuyển đổi phụ đề tiếng Anh và tiếng Trung

9.1

Tư duy tính toán

Chương trình
Thí sinh cần có thể: Ghi chú và hướng dẫn
Thể hiện sự hiểu biết về trừu tượng hóa Nhu cầu và lợi ích của việc sử dụng trừu tượng hóa Mô tả mục đích của trừu tượng hóa Xây dựng một mô hình trừu tượng của hệ thống chỉ bằng cách bao gồm các chi tiết thiết yếu
Mô tả và sử dụng phân rã Chia nhỏ các vấn đề thành các vấn đề con dẫn đến khái niệm về một mô-đun chương trình (hàm / thủ tục)

Nguồn: Chương trình Cambridge International

Tư duy tính toán là tập hợp các công cụ tư duy để phân tích một vấn đề và thiết kế một giải pháp mà máy tính có thể thực thi. Hai yếu tố cốt lõi là trừu tượng hóa và phân rã.

Một phần puzzle chưa hoàn chỉnh
Tư duy tính toán chia nhỏ một vấn đề lớn thành các phần nhỏ hơn, dễ giải quyết hơn — giống như việc giải một bài puzzle

Trừu tượng hóa

Trừu tượng hóa có nghĩa là giữ lại các đặc điểm thiết yếu của một vấn đề và bỏ qua các chi tiết không liên quan, tạo ra một mô hình đơn giản hơn.

Ví dụ:

  • bản đồ mạng lưới tàu hỏa giữ lại các ga và tuyến đường nhưng bỏ qua địa lý.
  • một class trong lập trình hướng đối tượng chỉ giữ lại các thuộc tính và phương thức mà hệ thống cần.
  • một hàm ẩn đi một phần công việc dưới một cái tên.

Một mô hình đầy đủ của bất kỳ vấn đề thực tế nào sẽ quá lớn để suy luận, nên trừu tượng hóa là cần thiết.

Người ra đề yêu cầu giải thích mục đích của sự trừu tượng và các lợi ích của nó. Mục đích: tạo ra một mô hình đơn giản hơn cho vấn đề, chỉ chứa những chi tiết cần thiết để giải quyết nó. Lợi ích: vấn đề dễ hiểu và dễ lập trình hơn; chương trình nhỏ gọn hơn, nhanh chóng viết và kiểm thử hơn; cùng một mô hình có thể tái sử dụng cho các vấn đề tương tự. Khi được yêu cầu tạo mô hình trừu tượng cho một hệ thống, chỉ liệt kê dữ liệu và hành động mà tác vụ cần. Ví dụ với bảng thời khóa biểu trường học, điều đó có nghĩa là các lớp học, phòng học, giáo viên và tiết học; không phải màu sắc phòng học hay độ tuổi của giáo viên.

Trừu tượng biến bản đồ địa lý thực tế lộn xộn (một tuyến đường ngoằn ngoèo với các tòa nhà rải rác) thành một bản đồ tàu điện ngầm sạch sẽ — các vòng tròn ga đều đặn trên một đường thẳng, giữ lại các ga và tuyến, nhưng loại bỏ địa lý thực tế
Trừu tượng giữ lại những yếu tố cốt lõi (các ga và tuyến) và loại bỏ chi tiết không liên quan (bản đồ địa lý)

Phân rã (Decomposition)

Phân rã có nghĩa là chia một vấn đề lớn thành các vấn đề con nhỏ hơn, mỗi vấn đề con dễ giải quyết hơn và được giải quyết từng bước một.

  1. xác định các phần chính của tác vụ.
  2. chia mỗi phần thành các tác vụ con nhỏ hơn.
  3. tiếp tục cho đến khi mỗi phần đủ nhỏ để thiết kế trực tiếp.
  4. giải quyết các tác vụ nhỏ và kết hợp chúng lại.

Đối với quản lý tồn kho: "quản lý tồn kho" → "ghi nhận bán hàng", "ghi nhận giao hàng", "tạo báo cáo" → ("ghi nhận bán hàng") "tra cứu sản phẩm", "giảm số lượng tồn kho", "lưu giao dịch". Phân rã giúp các vấn đề lớn trở nên khả thi, cho phép nhóm chia sẻ công việc và tạo ra mã code theo mô-đun — mỗi mô-đun trở thành một thủ tục hoặc hàm.

Câu hỏi "Giải thích tại sao phân rã được sử dụng" là câu hỏi 3 điểm với cấu trúc cố định. Hãy đưa ra ba lợi ích riêng biệt: mỗi vấn đề con đủ nhỏ để thiết kế, viết code và kiểm thử độc lập; các lập trình viên khác nhau có thể làm việc trên các mô-đun khác nhau cùng lúc; một mô-đun đã tồn tại (hoặc thủ tục thư viện) có thể tái sử dụng, và lỗi dễ tìm thấy hơn vì nó nằm bên trong một mô-đun cụ thể. Biểu đồ cấu trúc (chủ đề 12) là sơ đồ của sự phân rã: chương trình ở trên cùng, các mô-đun của nó bên dưới, và dữ liệu truyền giữa chúng.

Một cây với "Manage stock" ở phía trên nhánh ra các module "Record sales", "Record deliveries" và "Produce reports", và "Record sales" tách ra các tác vụ con "Look up product", "Decrease stock count" và "Save the transaction"
Phân rã một chương trình thành các module và sub-modules
Khám phá

Giải quyết một vấn đề theo cách tính toán

Tiến hành qua bốn trụ cột theo thứ tự bạn sẽ sử dụng chúng — phân rã vấn đề, nhận diện sự lặp lại, loại bỏ chi tiết không cần thiết, sau đó viết các bước.

Từ vựng Luyện tập
English Tiếng Việt
computational thinking/ˌkɒmpjuːˈteɪʃənl ˈθɪŋkɪŋ/ Tư duy tính toán
abstraction/əbˈstrækʃn/ Trừu tượng hóa
decomposition/ˌdiːkɒmpəˈzɪʃn/ Phân rã
sub-problem/sʌb ˈprɒbləm/ Vấn đề con
procedure/prəˈsiːdʒə/ Thủ tục
modules/ˈmɒdjuːlz/ mô-đun
algorithm/ˈælɡərɪθəm/ Thuật toán
sequence/ˈsiːkwəns/ Thứ tự
unambiguous/ʌnæmˈbɪɡjuːəs/ không mơ hồ
deterministic/dɪˌtɜːmɪˈnɪstɪk/ Xác định được
9.2

Thuật toán

Chương trình
Thí sinh cần có thể: Ghi chú và hướng dẫn
Thể hiện sự hiểu biết rằng một thuật toán là lời giải cho một vấn đề được biểu diễn dưới dạng một chuỗi các bước xác định
Sử dụng tên định danh phù hợp để biểu diễn dữ liệu được sử dụng bởi một vấn đề và biểu diễn chúng bằng một bảng định danh
Viết giả mã chứa đầu vào, xử lý và đầu ra
Viết giả mã sử dụng ba kiến trúc cơ bản của trình tự, lựa chọn và lặp lại (vùng lặp)
Tài liệu hóa một thuật toán đơn giản bằng mô tả tiếng Anh có cấu trúc, sơ đồ khối hoặc giả mã
Viết giả mã từ: • mô tả tiếng Anh có cấu trúc • sơ đồ khối
Vẽ sơ đồ khối từ: • mô tả tiếng Anh có cấu trúc • giả mã
Mô tả và sử dụng quá trình tinh chỉnh từng bước để biểu diễn một thuật toán ở mức độ chi tiết mà từ đó có thể lập trình được nhiệm vụ
Sử dụng các mệnh đề logic để xác định các phần của lời giải thuật toán

Nguồn: Chương trình Cambridge International

Thuật toán sắp xếp nổi bọt, qua từng lượt

Một thuật toán là một phương pháp giải quyết được diễn đạt dưới dạng chuỗi các bước xác định. Mỗi bước không mơ hồ (có một ý nghĩa), xác định (cùng đầu vào → cùng đầu ra), hữu hạn (các bước kết thúc), và hiệu quả (mỗi bước đều có thể thực hiện). Một thuật toán nói cần làm gì, độc lập với ngôn ngữ lập trình được dùng để triển khai nó.

Khám phá

Lựa chọn: đi theo các nhánh IF / ELSE

Kéo điểm số và xem nhánh nào được thực thi. Sự lựa chọn kiểm tra từng điều kiện một và chọn NHÁNH ĐẦU TIÊN đúng — đó là cách hoạt động của IF … ELSE IF … ELSE.

Xem bài học
9.2

Bảng ký hiệu

Khi bắt đầu một thuật toán, hãy liệt kê mọi piece dữ liệu vào một bảng ký hiệu — bao gồm ký hiệu (tên biến), kiểu dữ liệu, và mô tả. Bảng kiểm tra sẽ có đúng ba cột này:

Ký hiệu Kiểu dữ liệu Mô tả
Category STRING danh mục sản phẩm
SaleDate DATE thời điểm mặt hàng được bán
ItemCost REAL giá thành của mặt hàng
InStock BOOLEAN TRUE nếu còn trong kho
Sales ARRAY[1:30] OF REAL tổng doanh số hàng ngày trong 30 lần gần nhất

Sử dụng tên mô tả (ItemCost, không phải x): một ký hiệu bắt đầu bằng chữ cái, không chứa khoảng trắng, và được viết giống hệt nhau mỗi lần xuất hiện. Các kiểu phổ biến là INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, cộng thêm mảng. Bảng buộc bạn phải đặt tên cho mọi piece dữ liệu trước khi viết code, và câu hỏi "hoàn thành bảng ký hiệu" sẽ cho 1 điểm cho mỗi kiểu dữ liệu hoặc mô tả đúng, vì vậy hãy viết kiểu chính xác như hướng dẫn pseudocode yêu cầu.

Bảng định danh liệt kê từng biến với tên, kiểu dữ liệu và mô tả, ví dụ ItemCost là REAL cho chi phí của mặt hàng
Bảng ký danh đặt tên cho mọi mảnh dữ liệu trước khi bạn viết code
Từ vựng Luyện tập
English Tiếng Việt
identifier table/aɪˈdentɪfaɪə ˈteɪbl/ Bảng danh định
identifier/aɪˈdentɪfaɪə/ định danh
Boolean/ˈbuːlɪən/ Boolean
pseudocode/ˈsuːdəʊkəʊd/ Giả mã
9.2

Pseudocode — Ba kiến trúc cơ bản

Pseudocode là cách mô tả thuật toán mang tính cấu trúc, trung lập với ngôn ngữ.

Ba cấu trúc cơ bản dưới dạng sơ đồ luồng nhỏ: trình tự chạy bước A rồi B rồi C; lựa chọn kiểm tra điều kiện và thực hiện X hoặc Y; lặp lại thực thi thân vòng lặp khi điều kiện còn đúng, quay trở lại
Ba khối xây dựng cơ bản của bất kỳ thuật toán nào: tuần tự, chọn lọc và lặp

1. Tuần tự

Các bước chạy lần lượt theo thứ tự (tuần tự):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. Chọn lọc

Lựa chọn các bước nào sẽ chạy, dựa trên một điều kiện (chọn lọc):

IF Age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

Để có nhiều tùy chọn hơn, hãy dùng CASE OF ... ENDCASE.

3. Lặp

Lặp lại một khối lệnh (lặp, một vòng lặp):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

Vòng lặp WHILE kiểm tra điều kiện trước mỗi lượt chạy (có thể chạy 0 lần); vòng lặp REPEAT...UNTIL kiểm tra sau mỗi lượt chạy (luôn chạy ít nhất một lần).

WHILE Total < 100 DO
    INPUT Value
    Total ← Total + Value
ENDWHILE

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100
Hai sơ đồ luồng đặt cạnh nhau. WHILE kiểm tra điều kiện trước, nên thân có thể không bao giờ chạy: hình thoi nằm trên thân và nhánh Không thoát khỏi vòng lặp. REPEAT UNTIL thực thi thân trước và kiểm tra sau đó, nên thân luôn chạy ít nhất một lần: thân nằm trên hình thoi và nhánh Không quay trở về thân
Vòng lặp WHILE kiểm tra trước khi thân lệnh chạy; vòng lặp REPEAT ... UNTIL kiểm tra sau khi thân lệnh chạy, nên thân lệnh luôn chạy ít nhất một lần

Việc chọn loại vòng lặp chính là điểm số: FOR khi bạn biết số lần lặp (một vòng lặp kiểm soát đếm; WHILE khi vòng lặp có thể không chạy chút nào (một vòng lặp tiền điều kiện); REPEAT ... UNTIL khi nó phải chạy ít nhất một lần, như trong việc xác thực đầu vào (một vòng lặp hậu điều kiện). Câu trả lời "mô tả cấu trúc lặp" cần nêu tên cấu trúc, chỉ ra nơi điều kiện được kiểm tra, và đưa ra hệ quả (không chạy lần nào hoặc chạy ít nhất một lần).

Các phép toán thường gặp

  • gán: x ← 5 (một mũi tên; = dùng để so sánh).
  • nhập/xuất: INPUT variable, OUTPUT expression.
  • so sánh =, <>, <, >, <=, >=; logic AND, OR, NOT.
  • phép toán số học + - * /, cộng DIV (phép chia lấy phần nguyên) và MOD (phần dư).
  • chuỗi: LENGTH, LEFT, RIGHT, MID, và & để nối (ghép nối).

Mã giả mà đề thi yêu cầu

Mọi câu trả lời mã giả đều được chấm theo hướng dẫn mã giả do Cambridge công bố. Hãy viết đúng các dạng sau:

Cấu trúc Mã giả
Biến DECLARE Total : INTEGER
Mảng DECLARE Marks : ARRAY[1:30] OF REAL
Hằng CONSTANT MaxTries = 3
Phép gán Total ← Total + Value
Nhập / xuất INPUT Name
OUTPUT "Hello ", Name
Rẽ nhánh CASE OF Choice
1 : OUTPUT "Add"
OTHERWISE OUTPUT "Error"
ENDCASE
Vòng lặp FOR FOR i ← 1 TO 10 STEP 2 ... NEXT i
Vòng lặp WHILE WHILE Total < 100 DO ... ENDWHILE
Vòng lặp REPEAT REPEAT ... UNTIL Mark >= 0
Số học số nguyên 17 DIV 5 = 3
17 MOD 5 = 2
Chuỗi ký tự LENGTH(S), LEFT(S, 3), RIGHT(S, 2)
MID(S, 2, 4), TO_UPPER(S), TO_LOWER(S)
Chuyển đổi INT(3.7) = 3, NUM_TO_STR(12)
STR_TO_NUM("4.5"), ASC('A') = 65, CHR(66) = 'B'
Số ngẫu nhiên RAND(100)
INT(RAND(100)) + 1

RAND(100) trả về một số thực từ 0 đến (nhưng không bao gồm) 100. INT(RAND(100)) + 1 trả về một số nguyên từ 1 đến 100.

Hai thói quen được điểm ở mọi câu hỏi: khai báo mọi biến bạn dùng, kèm kiểu dữ liệu lấy từ bảng định danh, và khởi tạo 初始化 mọi bộ đếm 计数器 và biến tổng (Count ← 0, Total ← 0) trước vòng lặp làm thay đổi chúng.

Nhập → Xử lý → Xuất

Mọi chương trình đều theo dạng này:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

Liệt kê đầu vào và đầu ra trước giúp thuật toán gọn gàng hơn.

Ví dụ giải. Viết mã giả nhập 100 số nguyên và xuất ra số lượng cũng như tổng của những số nằm giữa 10 và 20 bao gồm cả hai giá trị biên.

Bảng định danh: Count : INTEGER (bộ đếm vòng lặp), Value : INTEGER (số nguyên vừa nhập), InRange : INTEGER (số lượng nằm trong khoảng), Total : INTEGER (tổng của chúng).

DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
    INPUT Value
    IF Value >= 10 AND Value <= 20 THEN
        InRange ← InRange + 1
        Total ← Total + Value
    ENDIF
NEXT Count
OUTPUT InRange, Total

Nếu câu hỏi sau đó yêu cầu bạn "xác định hai cấu trúc và phát biểu cách mỗi cấu trúc được sử dụng", hãy trả lời theo cùng định dạng: lặp lại, vòng lặp FOR, lặp lại việc nhập liệu 100 lần; lựa chọn, câu lệnh IF, cộng giá trị chỉ khi nó nằm trong phạm vi.

Ví dụ giải. Một chương trình chọn một số nguyên bí mật từ 1 đến 100. Người dùng đoán cho đến khi đúng; sau mỗi lần đoán sai, chương trình báo "Too low" (quá thấp) hoặc "Too high" (quá cao), và cuối cùng xuất ra số lần đã đoán.

Bảng định danh: Secret : INTEGER (số cần đoán), Guess : INTEGER (dữ liệu người dùng nhập), Tries : INTEGER (số lần đoán đến lúc này).

DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
    INPUT Guess
    Tries ← Tries + 1
    IF Guess < Secret THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Secret THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"

Vòng lặp REPEAT ... UNTIL là lựa chọn đúng vì người dùng phải đoán ít nhất một lần. Điểm được cho cho: số ngẫu nhiên trong đúng khoảng, vòng lặp kết thúc khi đoán đúng, bộ đếm bắt đầu từ 0 và tăng bên trong vòng lặp, hai thông báo đúng điều kiện, và kết quả xuất cuối cùng.

Lưu đồ của trò chơi đoán số: Bắt đầu, gán Secret là một số nguyên ngẫu nhiên từ 1 đến 100 và Tries bằng 0, rồi nhập một lần đoán, cộng một vào Tries, kiểm tra lần đoán có bằng số bí mật không (Có thì xuất Tries và Dừng), nếu không thì kiểm tra lần đoán có nhỏ hơn không (Có thì xuất Too low, Không thì xuất Too high), và cả hai nhánh xuất đều quay lại bước nhập
Cùng trò chơi đoán số dưới dạng lưu đồ: hai hình thoi quyết định là hai câu lệnh IF, và mũi tên quay lại là vòng lặp REPEAT ... UNTIL

Ví dụ giải. Xuất ra hai số nguyên ngẫu nhiên khác nhau, mỗi số nằm trong khoảng từ $-10$ đến $10$ (tính cả hai đầu).

Có 21 giá trị có thể, nên INT(RAND(21)) cho 0 đến 20, và trừ đi 10 sẽ dịch nó về khoảng $-10$ đến $10$. Số thứ hai phải được tạo lại cho đến khi nó khác số thứ nhất:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second
Mọi chương trình theo dạng nhập, rồi xử lý, rồi xuất, minh họa bằng ví dụ diện tích: nhập chiều dài và chiều rộng, xử lý bằng phép nhân, xuất diện tích
Mọi chương trình đều theo dạng Nhập, Xử lý, Xuất
Khám phá

IF … ELSE chọn lọc

Thay đổi giá trị và quan sát nhánh nào chạy — cách chương trình đưa ra quyết định.

Từ vựng Luyện tập
English Tiếng Việt
variable/ˈveərɪəbl/ Biến
data type/ˈdeɪtə taɪp/ Kiểu dữ liệu
flowchart/ˈfləʊtʃɑːt/ sơ đồ khối
selection/sɪˈlekʃn/ chọn lọc
iteration/ˌɪtəˈreɪʃn/ lặp lại
loop/luːp/ Vòng lặp
count-controlled loop/kaʊnt kənˈtrəʊld luːp/ Vòng lặp điều khiển bằng bộ đếm
pre-condition loop/priː kənˈdɪʃn luːp/ Vòng lặp kiểm tra tiền điều kiện
post-condition loop/pəʊst kənˈdɪʃn luːp/ vòng lặp điều kiện sau
assignment/əˈsaɪnmənt/ Gán
concatenation/kənˌkætəˈneɪʃn/ nối chuỗi
initialise/ɪˈnɪʃəlaɪz/ khởi tạo
counter/ˈkaʊntə/ bộ đếm
structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ tiếng Anh có cấu trúc
stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ tinh chỉnh từng bước
logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ câu logic
precedence/ˈpresɪdəns/ độ ưu tiên
De Morgan's law/də ˈmɔːɡənz lɔː/ định luật De Morgan
9.2

Ba cách biểu diễn

Cùng một thuật toán có thể được viết theo ba cách.

  • tiếng Anh có cấu trúc 结构化英语 — ngôn ngữ tự nhiên có thụt lề và từ khóa cố định; phù hợp để mô tả ở mức cao.
  • lưu đồ 流程图 — sơ đồ dùng các hình chuẩn:
Hình Ý nghĩa
Hình chữ nhật bo góc Bắt đầu / Kết thúc
Hình bình hành Nhập / Xuất
Hình chữ nhật Xử lý
Hình thoi Quyết định
Mũi tên Luồng điều khiển
  • mã giả — cách viết bằng từ khóa ở trên; gần với mã nhất.

Bạn cần chuyển đổi được giữa bất kỳ hai cách nào: mỗi IF là một hình thoi quyết định, mỗi vòng lặp là một mũi tên quay ngược, và một dãy lệnh là các hình chữ nhật xếp chồng.

IF ... THEN ... ELSE ... ENDIF

Lưu đồ tính trung bình các số: các ô Bắt đầu và Kết thúc bo góc, các hình bình hành nhập/xuất, các hình chữ nhật xử lý, và một hình thoi quyết định "count < n?" có nhánh Có quay lại để đọc giá trị tiếp theo
Lưu đồ tính trung bình một danh sách số, dùng các hình chuẩn
9.2

Tinh chỉnh từng bước

Tinh chỉnh từng bước 逐步求精 bắt đầu từ một dàn ý mức cao và mở rộng từng bước cho đến khi đủ nhỏ để viết mã. Với trung bình của $n$ số:

Mức 1:

Read in the numbers
Compute the average
Output the average

Mức 2:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

Mỗi lần tinh chỉnh giữ nguyên cấu trúc trước đó và thêm chi tiết.

Câu hỏi sáu điểm "áp dụng tinh chỉnh từng bước" cho bạn một dàn ý mức cao và yêu cầu mở rộng từng bước thành các câu lệnh cụ thể mà lập trình viên có thể viết mã. Giữ nguyên thứ tự các bước, nêu tên dữ liệu mà mỗi bước đọc hoặc tạo ra, và dừng lại khi mỗi dòng là một lệnh nhập, gán, xuất, vòng lặp hoặc điều kiện duy nhất. Ví dụ, "kiểm tra mật khẩu" trở thành: nhập mật khẩu; kiểm tra độ dài ít nhất là 8; kiểm tra có ít nhất một chữ số; xuất "accepted" (chấp nhận) nếu cả hai kiểm tra đều đạt, ngược lại xuất "rejected" (từ chối).

Tinh chỉnh từng bước: dàn ý Mức 1 (đọc các số, tính trung bình, xuất trung bình) được mở rộng thành mã giả chi tiết Mức 2 có vòng lặp nhập và phép chia
Tinh chỉnh từng bước: mở rộng mỗi bước cấp cao thành giả mã chi tiết
Khám phá

Sự tinh luyện từng bước: dàn ý sang mã

Đi xuống các cấp độ. Bạn bắt đầu với toàn bộ nhiệm vụ trong một dòng và tiếp tục mở rộng từng bước thành những bước nhỏ hơn — cho đến khi mỗi bước đơn giản enough để mã hóa trực tiếp.

9.2

Câu lệnh logic

Một câu lệnh logic là một điều kiện Boolean điều khiển nhánh, được xây dựng từ phép so sánh (x > 10), toán tử kết hợp (AND, OR, NOT) và ngoặc. Sử dụng nó như điều kiện của IF, WHILE hoặc REPEAT...UNTIL:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

Độ ưu tiên (cao nhất đến thấp nhất): NOT, sau đó AND, rồi OR. Sử dụng ngoặc khi không chắc chắn. Lỗi thường gặp:

  • a = 1 OR 2 là sai — hãy viết a = 1 OR a = 2.
  • NOT a > 5 có nghĩa là NOT (a > 5), tức là a <= 5.
  • NOT (A AND B) giống hệt với (NOT A) OR (NOT B) (Định luật De Morgan) — hữu ích để rút gọn điều kiện.

Biến câu văn thành câu lệnh logic là kỹ năng mà đề thi kiểm tra trực tiếp. "Vé miễn phí cho bất kỳ ai dưới 5 tuổi hoặc trên 65 tuổi" trở thành Age < 5 OR Age > 65. "Điểm số hợp lệ nếu nó là số nguyên từ 0 đến 100" trở thành Mark >= 0 AND Mark <= 100. "Vòng lặp dừng lại khi file đã đọc xong hoặc đã đọc mười bản ghi" trở thành UNTIL EOF(File) OR Count = 10. Viết đầy đủ mỗi phép so sánh: Age > 65 và Age < 5, tuyệt đối không viết Age > 65 OR < 5.

Cây phân tích cho "attempts < 3 AND NOT loggedIn": NOT áp dụng vào loggedIn trước, sau đó AND gộp nó với attempts < 3
Độ ưu tiên: NOT gắn vào loggedIn trước, sau đó AND kết hợp hai vế

Ví dụ minh họa. Viết bảng định danh và giả mã để đọc 10 số và xuất ra số lớn nhất. Bảng định danh đặt tên cho từng biến kèm kiểu dữ liệu và mục đích: Count : INTEGER (bộ đếm vòng lặp), Num : REAL (số vừa được đọc), Max : REAL (số lớn nhất tính đến thời điểm đó).

Max ← -999999
FOR Count ← 1 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

Quyết định thiết kế mang điểm số chính là khởi tạo Max: nó phải bắt đầu thấp hơn bất kỳ giá trị đầu vào nào có thể xảy ra - hoặc an toàn hơn, hãy gán cho nó số đầu tiên được đọc. Khởi tạo nó là 0 thì thuật toán sẽ trả về sai là 0 cho danh sách các số âm, một lỗi chỉ bị phát hiện qua việc theo dõi thuật toán nếu dữ liệu thử nghiệm bao gồm số âm.

Kiến thức lập trình cần có cho các câu hỏi thuật toán

Trước khi viết hoặc traced thuật toán, hãy sử dụng các phương trình và phương pháp hàm tích hợp trong tài liệu 11.1.1–11.1.2. TO_UPPER và TO_LOWER chấp nhận toàn bộ chuỗi; UCASE và LCASE trong hướng dẫn hoạt động trên một ký tự đơn lẻ. Làm theo yêu cầu chèn của đề bài.

Ghép chuỗi bằng &; chuyển đổi số bằng NUM_TO_STR trước khi ghép. Gọi thủ tục bằng CALL Name(arguments); sử dụng hàm như một biểu thức. SETDATE(day, month, year) tạo giá trị DATE. Kiểm tra kiểu dữ liệu trước khi đánh giá: một biểu thức không hợp lệ sẽ là ERROR, không phải phép chuyển đổi đoán mò.

Đối với lưu đồ có nhiều tổng, khởi tạo mỗi bộ tích lũy trước vòng lặp. Cập nhật chúng trên các nhánh đúng, tăng biến đếm, sau đó kiểm tra điều kiện kết thúc. Đặt tính trung bình sau vòng lặp và sử dụng số lượng giá trị thực tế đã bao gồm.

9.2

Các định nghĩa mà giám khảo chấp nhận

Câu hỏi định nghĩa được chấm dựa trên văn phong cố định. Hãy học thuộc những định nghĩa này và chỉ đưa ra một đáp án duy nhất.

Thuật ngữ Định nghĩa
trừu tượng hóa giữ lại các chi tiết cốt lõi của bài toán và bỏ qua các chi tiết không cần thiết
phân tách chia nhỏ bài toán thành các bài toán con nhỏ hơn, mỗi cái có thể giải quyết riêng biệt
thuật toán lời giải cho một bài toán được biểu diễn dưới dạng chuỗi các bước xác định
bảng định danh bảng liệt kê từng định danh được sử dụng trong thuật toán kèm kiểu dữ liệu và mô tả mục đích của nó
giả mã cách viết cấu trúc, độc lập với ngôn ngữ, các bước của thuật toán
sơ đồ khối biểu đồ hiển thị các bước và quyết định của thuật toán bằng các ký hiệu tiêu chuẩn nối với nhau bằng mũi tên
tuần tự các câu lệnh được thực thi lần lượt theo thứ tự đã viết
chọn lọc lựa chọn câu lệnh nào sẽ được thực thi dựa trên một điều kiện
lặp lại lặp đi lặp lại một nhóm câu lệnh trong khi hoặc cho đến khi một điều kiện còn đúng
tinh chỉnh từng bước chia nhỏ từng bước của phác thảo thành các bước nhỏ hơn, liên tục cho đến khi mỗi bước có thể viết code trực tiếp
câu lệnh logic điều kiện được xây dựng từ các phép so sánh và các toán tử AND, OR và NOT, đánh giá ra TRUE hoặc FALSE
9.2

Mẹo làm bài thi

  • Định nghĩa thuật toán là một chuỗi các bước rõ ràng, hữu hạn, xác định, độc lập với ngôn ngữ.
  • Sử dụng đúng ba cấu trúc — tuần tự, chọn lọc, lặp lại — và giữ bảng định danh có kiểu dữ liệu.
  • Chia nhỏ bài toán bằng phân tách và trừu tượng hóa, sau đó tinh chỉnh từng bước.
  • Viết giả mã có thể chạy được: khai báo biến và tuân theo phong cách giả mã của đề thi.

Lỗi thường gặp

  • Sử dụng = để gán giá trị. Gán giá trị là ←; = là phép so sánh.
  • Quên ENDIF, ENDWHILE, ENDCASE hoặc NEXT. Mỗi cấu trúc đều phải đóng, và từ đóng ở cuối chính là nơi chấm điểm cho cấu trúc đó được kiểm tra.
  • Không khởi tạo tổng hoặc bộ đếm trước vòng lặp, khiến thuật toán cộng vào một giá trị chưa bao giờ tồn tại.
  • Sử dụng vòng lặp FOR khi số lần lặp chưa biết. Đọc cho đến khi gặp giá trị dấu hiệu hoặc đoán đúng cần WHILE hoặc REPEAT ... UNTIL.
  • Viết Age > 65 OR < 5. Mỗi vế của OR và AND phải là một phép so sánh hoàn chỉnh.
  • Trả lời "giải thích vì sao sử dụng phân tách" bằng cách viết ba lợi ích theo ba cách khác nhau. Ba điểm số cần ba lợi ích khác nhau.

Bài học tương tác về chủ đề này

Làm theo từng bước, kèm theo bài tập kiểm tra ngay lập tức.

Đề thi cũ

Nhiều chủ đề hơn trong Khoa học máy tính A-Level

Đăng nhập hoặc tạo tài khoản

IGCSE, A-Level & AP