Thuật toán và mã giả
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| algorithm/ˈælɡərɪθəm/ | Thuật toán |
| sequence/ˈsiːkwəns/ | Thứ tự |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | Xác định được |
| identifier table/aɪˈdentɪfaɪə ˈteɪbl/ | Bảng danh định |
| variable/ˈveərɪəbl/ | Biến |
| data type/ˈdeɪtə taɪp/ | Kiểu dữ liệu |
| pseudocode/ˈsuːdəʊkəʊd/ | Giả mã |
| assignment/əˈsaɪnmənt/ | Gán |
| 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 |
| iteration/ˌɪtəˈreɪʃn/ | lặp lại |
| selection/sɪˈlekʃn/ | chọn lọc |
| flowchart/ˈfləʊtʃɑːt/ | sơ đồ khối |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | tinh chỉnh từng bước |
Dấu gạch nối đắt đỏ nhất trong lịch sử
- Vào ngày 22 tháng 7 năm 1962, tên lửa Mariner 1, hướng tới Sao Kim, đã bị phóng nổ 293 giây sau khi phóng.
- Nguyên nhân là do thiếu một dấu gạch ngang trên một ký hiệu trong phương trình dẫn đường. Máy tính đã tuân theo đúng các bước được viết, và các bước được viết thì sai.
- Một máy tính không bao giờ điền vào những gì bạn có ý định. Mọi bước bạn đưa cho nó đều phải có đúng một ý nghĩa.
- Đó là lý do bài học này nói về việc viết các bước mà máy móc có thể thực thi: thuật toán.
Thuật toán là gì
- Một thuật toán là giải pháp cho một vấn đề được biểu diễn dưới dạng dãy các bước xác định.
- Mỗi bước không mơ hồ (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 thực sự có thể thực hiện được).
- Nó nói điều cần làm, độc lập với bất kỳ ngôn ngữ lập trình nào, và mọi thuật toán đều tuân theo đầu vào → xử lý → đầu ra.
Mọi thuật toán đều có cùng hình dáng: đầu vào, xử lý, đầu ra
Một thuật toán mang tính "xác định" (deterministic). Điều này có nghĩa là:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Xác định = cùng đầu vào → cùng đầu ra mỗi lần. (Hữu hạn = các bước kết thúc; rõ ràng = một ý nghĩa cho mỗi bước.)
Ví dụ minh họa: bảng ký danh
- Trước khi viết code, liệt kê tất cả các mảnh dữ liệu trong một bảng ký danh: tên biến, kiểu dữ liệu và mô tả của chúng.
- Chương trình kho hàng của cửa hàng lưu trữ
"Fruit",20/02/2025,12.67vàTRUE. Đề thi yêu cầu đặt tên và kiểu cho mỗi thứ. Category : STRING(một loại hàng tồn kho),DateSold : DATE(khi nào nó được bán),ItemCost : REAL(chi phí),InStock : BOOLEAN(có còn hàng không?).- Một điểm cho mỗi dòng cho cả tên và kiểu, vì vậy hãy viết kiểu chính xác như hướng dẫn pseudocode làm:
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
Bảng ký danh đặt tên cho mọi mảnh dữ liệu trước khi bạn viết code
Trong bảng danh định, kiểu dữ liệu cho giá trị như 12.67 (một chi phí) là ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Một số có phần thập phân là SỐ THỰC. NGUYÊN SỐ dùng cho số nguyên, CHUỖI KÝ TỰ dùng cho văn bản, BOOLEAN dùng cho ĐÚNG/SALSA và DATE dùng cho ngày tháng.
Ba cấu trúc cơ bản
IF … THEN … ELSE … ENDIF
- Gán lưu giá trị với mũi tên,
Total ← Total + Value;=dùng để so sánh.DIVlà phép chia nguyên vàMODlà phần dư, nên17 MOD 5 = 2.
INPUT Age # sequence
IF Age >= 18 THEN
# selection
ENDIF
OUTPUT "Adult"
ELSE
OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10 # iteration
OUTPUT Count
NEXT Count
Ba khối xây dựng của bất kỳ thuật toán nào
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.
Gắn mỗi cấu trúc lập trình với chức năng của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Mọi thuật toán đều được xây dựng từ chỉ ba cấu trúc — trình tự, sự lựa chọn và lặp lại.
Trong mã giả này, ký hiệu nào có nghĩa gán (lưu trữ một giá trị)?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Gán sử dụng ← (ví dụ: x ← 5); = dành riêng cho so sánh.
Giá trị của 17 MOD 5 là gì?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
MOD cho phần dư: $17 = 3 \times 5 + 2$, nên 17 MOD 5 = 2. (17 DIV 5 = 3.)
Chọn vòng lặp nào?
FOR … NEXTkhi bạn biết số lần lặp: một vòng lặp điều khiển bởi bộ đếm.WHILE … ENDWHILEkiểm tra điều kiện trước mỗi lần lặp, nên thân vòng lặp có thể chạy không lần: một vòng lặp tiền điều kiện.REPEAT … UNTILkiểm tra sau mỗi lần lặp, nên thân vòng lặp luôn chạy ít nhất một lần: một vòng lặp hậu điều kiện. Kiểm chứng đầu vào là trường hợp điển hình.- Một câu trả lời "mô tả cấu trúc lặp" phải nêu tên vòng lặp, nói điểm kiểm tra điều kiện và đưa ra hệ quả.
Vòng lặp WHILE kiểm tra trước khi thân chạy; vòng lặp REPEAT … UNTIL kiểm tra sau
Vòng lặp WHILE khác với vòng lặp REPEAT...UNTIL như thế nào?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
WHILE kiểm tra trước (có thể chạy 0 lần); REPEAT...UNTIL kiểm tra sau, vì vậy nó luôn chạy ít nhất một lần.
Vòng lặp FOR được kiểm soát bởi bộ đếm (nó lặp lại một số lượng cố định lần), trong khi vòng lặp WHILE được kiểm soát bởi điều kiện (nó lặp lại cho đến khi một điều kiện thay đổi).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Sử dụng FOR khi bạn biết số lần lặp; sử dụng WHILE/REPEAT khi bạn lặp cho đến khi điều gì đó trở thành đúng.
Ví dụ minh họa: từ văn bản sang pseudocode
- Nhiệm vụ: nhập 100 giá trị nguyên, chỉ cộng những giá trị dương, và xuất tổng.
- Lập kế hoạch dữ liệu trước:
Count,TotalvàNextNumber, tất cả đều làINTEGER. Sau đó ba cấu trúc làm phần còn lại.
DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
INPUT NextNumber
IF NextNumber > 0 THEN
Total <- Total + NextNumber
ENDIF
NEXT Count
OUTPUT Total
- Phần tiếp theo yêu cầu bạn xác định các cấu trúc: lặp lại (vòng lặp
FORlặp việc nhập 100 lần), lựa chọn (IFquyết định xem giá trị có được cộng hay không) và tuần tự (các câu lệnh chạy theo thứ tự).
Nhận diện cấu trúc trong đoạn trích
- Một câu hỏi yêu thích hiển thị năm đoạn trích pseudocode và yêu cầu bạn tích vào xem mỗi đoạn sử dụng gán, lựa chọn, lặp lại nào.
Result ← CalculateTotal()là gán.WHILE IsClosedlà lặp lại.REPEAT … INPUT Value … UNTIL Sales[4] > Valuelà lặp lại và gán (INPUTlưu giá trị). IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF- Hãy xem xét từng dòng của đoạn trích, không chỉ dòng đầu tiên. Một hàng có thể cần hai dấu tích.
Cấu trúc nào được trích xuất từ đoạn mã này? REPEAT … INPUT Value … UNTIL Total > 100. Chọn tất cả các đáp án phù hợp.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
REPEAT … UNTIL là lặp lại, và INPUT Value lưu trữ một giá trị, điều này được coi là gán. Không có IF hay CASE, vì vậy không có sự lựa chọn — điều kiện UNTIL điều khiển vòng lặp, chứ không chọn giữa các nhánh.
Sơ đồ luồng
- Một sơ đồ khối mô tả cùng một thuật toán dưới dạng hình ảnh. Các oval là
STARTvàEND, các hình chữ nhật là quy trình, các hình bình hành làINPUT/OUTPUT, và một hình thoi là điểm quyết định. - Một hình thoi là nơi xảy ra sự chọn lựa, và một đường lưu thông đi ngược lên sơ đồ là một vòng lặp.
- Đề thi hỏi theo cả hai cách: giả mã từ sơ đồ khối, và sơ đồ khối từ giả mã hoặc tiếng Anh có cấu trúc. Mỗi ký hiệu bạn vẽ phải ánh xạ với một dòng giả mã.
Mỗi ký hiệu trong sơ đồ khối ánh xạ với một loại câu lệnh giả mã
Trong sơ đồ khối, hình thoi đại diện cho cái gì?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hình thoi là nơi diễn ra sự lựa chọn, và hình thoman mà dòng chảy quay lên trên sơ đồ là một phép kiểm tra vòng lặp. Hình chữ nhật là quá trình, hình bình hành là đầu vào/đầu ra, hình oval là BẮT ĐẦU và KẾT THÚC.
Ví dụ giải chi tiết: trò chơi đoán số
- Chương trình chọn một số nguyên ngẫu nhiên từ 1 đến 100, sau đó yêu cầu người dùng đoán cho đến khi họ đoán đúng. Người dùng phải đoán ít nhất một lần, nên vòng lặp này là một
REPEAT … UNTIL.
DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
INPUT Guess
IF Guess < Target THEN
OUTPUT "Too low"
ELSE
IF Guess > Target THEN
OUTPUT "Too high"
ENDIF
ENDIF
UNTIL Guess = Target
OUTPUT "Correct"
- Theo dõi sơ đồ khối: một hình thoi quyết định cho phép kiểm tra vòng lặp, hai hình thoi khác cho gợi ý, và mọi đường lưu thông đều quay trở lại
INPUT GuesshoặcEND.
Trò chơi đoán số dưới dạng sơ đồ khối: vòng lặp quay lại phần nhập cho đến khi lần đoán khớp
Tại sao REPEAT … UNTIL là vòng lặp phù hợp cho trò chơi đoán số?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Vòng lặp điều kiện hậu luôn chạy thân vòng lặp một lần trước khi kiểm tra, điều này phù hợp với trò chơi cần ít nhất một lần đoán. Một vòng lặp WHILE sẽ cần một lần đoán trước vòng lặp chỉ để có thứ gì đó để kiểm tra.
Tinh luyện từng bước (Stepwise refinement)
- Tinh luyện từng bước nghĩa là bắt đầu từ bản nháp và mở rộng mỗi bước thành các bước chi tiết hơn, liên tục như vậy cho đến khi mỗi bước có thể được viết trực tiếp dưới dạng giả mã.
- "Xử lý đơn hàng" → "lấy sản phẩm", "tính tổng", "thanh toán" → "tính tổng" trở thành "với mỗi sản phẩm, cộng giá × số lượng; áp dụng giảm giá nếu có".
- Mỗi cấp độ là sự tinh luyện của cấp trên nó, và các cấp độ hoàn chỉnh cùng nhau tạo thành thiết kế. Câu hỏi "Mô tả tinh luyện từng bước" đòi hỏi bản nháp, sự mở rộng và quy tắc dừng.
Tinh luyện mỗi bước cho đến khi nó có thể được mã hóa trực tiếp
Sắp xếp các giai đoạn của sự tinh luyện từng bước theo thứ tự.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Dàn ý trước, sau đó tinh luyện từng cấp độ; bạn dừng lại khi một bước là một dòng mã giả.
Câu lệnh logic
- Các phần của giải pháp được xác định bởi câu lệnh logic: các điều kiện được xây dựng từ phép so sánh (
=,<>,<,>,<=,>=) được nối với nhau bằngAND,ORvàNOT. - Một đánh dấu hợp lệ:
Mark >= 0 AND Mark <= 100. Giảm giá được áp dụng nếu khách hàng là thành viên hoặc chi tiêu quá 50:IsMember OR Total > 50. NOT (Mark < 40)có nghĩa giống nhưMark >= 40. Viết câu lệnh, sau đó kiểm tra nó với một giá trị nằm ở mỗi bên của ranh giới.
Các phép so sánh được nối với nhau bằng AND, OR và NOT tạo nên các điều kiện mà thuật toán cần
NOT (Mark < 40) đúng đối với đúng các giá trị của Mark như Mark >= 40.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Phủ định "nhỏ hơn 40" cho ra "40 hoặc hơn". Kiểm tra biên: Mark = 40 làm cho Mark < 40 sai, vì vậy phủ định của nó là đúng, và 40 >= 40 cũng đúng.
Điểm số dễ mất
←gán và=so sánh.IF Total = 0là một phép kiểm tra;Total = 0nằm trên cùng một dòng sẽ không nhận điểm nào.- Mọi cấu trúc đều đóng:
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. Việc thiếu dấu đóng sẽ làm hỏng điểm về cấu trúc. - Khai báo trước khi sử dụng, và khởi tạo tổng chạy lên đến
0. WHILEcó thể chưa bao giờ chạy,REPEATluôn chạy đúng một lần. Chọn vòng lặp phù hợp với nhiệm vụ, và giải thích lý do nếu được yêu cầu.
Bạn đã nắm vững
- Các bước của một thuật toán phải không mơ hồ, xác định, hữu hạn, khả thi; lập kế hoạch dữ liệu trong một bảng định danh
- Ba cấu trúc: trình tự, chọn lọc (
IF/CASE), lặp lại (FOR/WHILE/REPEAT);WHILEkiểm tra trước,REPEATsau - Sơ đồ khối và giả mã mô tả cùng một thuật toán; tinh luyện từng bước mở rộng bản nháp cho đến khi có thể mã hóa được
- Điều kiện là câu lệnh logic: các phép so sánh được nối với nhau bằng
AND,OR,NOT