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 IGCSE · Chủ đề 7

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

Vòng đời phát triển phần mềm

Mỗi ứng dụng trên điện thoại của bạn đều do một người giống như thế viết ra. Nhưng họ không bắt đầu bằng cách gõ code. Trước dòng đầu tiên, vấn đề đã được nghiên cứu, giải pháp đã được…

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

Chương trình
Thí sinh cần có thể: Ghi chú và hướng dẫn
1 Hiểu vòng đời phát triển phần mềm, giới hạn ở: phân tích, thiết kế, lập trình và kiểm thử • Bao gồm xác định từng giai đoạn và thực hiện các nhiệm vụ cho mỗi giai đoạn: – phân tích: trừu tượng hóa, phân rã vấn đề, xác định vấn đề và yêu cầu – thiết kế: phân rã, sơ đồ cấu trúc, lưu đồ, mã giả – lập trình: viết mã chương trình và kiểm thử lặp – kiểm thử: kiểm thử mã chương trình bằng cách sử dụng dữ liệu kiểm thử
2 (a) Hiểu rằng mọi hệ thống máy tính đều được cấu thành từ các hệ con, và các hệ con lại được cấu thành từ các hệ con nhỏ hơn (b) Hiểu cách một vấn đề có thể được phân rã thành các phần thành phần • Bao gồm: – đầu vào – quá trình xử lý – đầu ra – lưu trữ
(c) Sử dụng các phương pháp khác nhau để thiết kế và xây dựng giải pháp cho một vấn đề • Bao gồm: – sơ đồ cấu trúc – lưu đồ – mã giả
3 Giải thích mục đích của một thuật toán đã cho • Bao gồm: – nêu mục đích của thuật toán – mô tả các quy trình liên quan đến thuật toán
4 Hiểu các phương pháp giải chuẩn • Giới hạn ở: – tìm kiếm tuyến tính – sắp xếp nổi bọt – cộng tổng – đếm số – tìm giá trị lớn nhất, nhỏ nhất và trung bình
5 (a) Hiểu nhu cầu về kiểm tra hợp lệ đối với dữ liệu đầu vào và các loại kiểm tra hợp lệ khác nhau • Bao gồm: – kiểm tra phạm vi – kiểm tra độ dài – kiểm tra kiểu – kiểm tra sự tồn tại – kiểm tra định dạng – chữ số kiểm tra
(b) Hiểu nhu cầu về kiểm tra xác nhận đối với dữ liệu đầu vào và các loại kiểm tra xác nhận khác nhau • Bao gồm: – kiểm tra trực quan – kiểm tra nhập hai lần
6 Đề xuất và áp dụng dữ liệu kiểm thử phù hợp • Giới hạn ở: – bình thường – bất thường – cực đoan – biên • Dữ liệu cực đoan là giá trị lớn nhất/nhỏ nhất được chấp nhận • Dữ liệu biên là giá trị lớn nhất/nhỏ nhất được chấp nhận và giá trị tương ứng nhỏ nhất/lớn nhất bị từ chối
7 Hoàn thành bảng theo dõi để ghi lại chạy khô của một thuật toán • Bao gồm, tại mỗi bước trong thuật toán: – biến – đầu ra – câu hỏi người dùng
8 Xác định lỗi trong các thuật toán đã cho và đề xuất cách khắc phục những lỗi này
9 Viết và sửa đổi thuật toán cho các vấn đề hoặc tình huống đã cho, sử dụng: mã giả, mã chương trình và lưu đồ • Cần sự chính xác khi viết thuật toán, ví dụ: x > y là chấp nhận được nhưng x is greater than y thì không chấp nhận được • Xem phần 4 để biết ký hiệu lưu đồ • Xem phần 4 để biết mã giả

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

7.1

Vòng đời phát triển chương trình

Vòng đời phát triển chương trình là tập hợp các giai đoạn được sử dụng để tạo ra một chương trình. Có bốn giai đoạn.

Một lập trình viên đang gõ mã trên máy tính
Phần mềm được viết bởi các lập trình viên, những người tuân theo vòng đời phát triển
Giai đoạn Những gì bạn làm
phân tích nghiên cứu vấn đề và xác định những gì cần thiết
thiết kế lên kế hoạch chương trình sẽ hoạt động như thế nào
lập trình viết mã chương trình và kiểm tra khi đi qua từng bước
kiểm thử chạy chương trình hoàn chỉnh với dữ liệu kiểm thử để tìm lỗi
Bốn giai đoạn nối tiếp nhau — phân tích, thiết kế, lập trình, kiểm thử — với mũi tên phản hồi từ kiểm thử đến thiết kế
Bốn giai đoạn của phát triển chương trình; kiểm thử phản hồi để sửa chữa và tinh chỉnh thiết kế
Sơ đồ luồng của một chương trình với các hộp quy trình và kim cương quyết định
Sơ đồ luồng của một chương trình trình bày các bước và quyết định của chương trình trong giai đoạn thiết kế

Phân tích

Trong phân tích, bạn hiểu vấn đề. Hai kỹ năng then chốt hỗ trợ:

  • trừu tượng hóa — giữ lại chỉ những chi tiết quan trọng và bỏ qua những phần còn lại;
  • phân rã — chia nhỏ một vấn đề lớn thành các phần nhỏ hơn, dễ giải quyết hơn.

Thiết kế

Trong thiết kế, bạn lên kế hoạch cho giải pháp, thường sử dụng phân rã. Bạn có thể hiển thị các phần dưới dạng hệ thống con trong sơ đồ cấu trúc (biểu đồ chia một hệ thống thành các ô nhỏ hơn).

Ví dụ minh họa. Một bãi đỗ xe có máy thanh toán. Người lái nhập biển số xe, máy tính thời gian xe đã đỗ và số tiền phải trả, người lái thanh toán bằng tiền mặt hoặc thẻ, rồi máy in biên lai. Hãy vẽ sơ đồ cấu trúc.

Sơ đồ cấu trúc: Máy thanh toán ở trên cùng, chia thành Nhập, Tính phí, Nhận thanh toán và Xuất; Nhập chia thành biển số xe và thời gian đến, Nhận thanh toán chia thành tiền mặt và thẻ
Sơ đồ cấu trúc của máy thanh toán bãi đỗ xe: mỗi ô là một hệ thống con, và mỗi cấp thấp hơn chia phần tử cấp trên thành các phần nhỏ hơn

Toàn bộ hệ thống nằm trong ô trên cùng. Mỗi ô ở cấp tiếp theo là một công việc của hệ thống, và một ô có thể được chia tiếp (thanh toán được chia thành tiền mặt và thẻ). Đọc ngang mỗi cấp từ trái sang phải theo thứ tự thực hiện công việc. Sơ đồ cấu trúc thể hiện các bộ phận, không thể hiện thứ tự của các quyết định hay vòng lặp: lưu đồ hoặc mã giả dùng để thể hiện điều đó.

Lập trình và kiểm thử

Trong lập trình, bạn viết mã chương trình. Bạn sử dụng kiểm thử lặp — kiểm tra các phần nhỏ đi kiểm tra lại nhiều lần khi xây dựng chúng. Trong kiểm thử, bạn chạy toàn bộ chương trình với dữ liệu kiểm thử để kiểm tra xem nó có hoạt động hay không.

Từ vựng Luyện tập
English Tiếng Việt
program development life cycle/ˈprəʊɡræm dɪˈveləpmənt laɪf ˈsaɪkl/ chu kỳ phát triển chương trình
analysis/əˈnæləsɪs/ phân tích
design/dɪˈzaɪn/ thiết kế
coding/ˈkəʊdɪŋ/ lập trình
testing/ˈtestɪŋ/ kiểm thử
abstraction/əbˈstrækʃn/ trừu tượng
decomposition/ˌdiːkɒmpəˈzɪʃn/ phân rã
sub-systems/sʌb ˈsɪstəmz/ hệ con
structure diagram/ˈstrʌktʃə ˈdaɪəɡræm/ sơ đồ cấu trúc
iterative testing/ˈɪtərətɪv ˈtestɪŋ/ kiểm thử lặp lại
test data/test ˈdeɪtə/ dữ liệu thử nghiệm
flowchart/ˈfləʊtʃɑːt/ sơ đồ khối
7.2

Công cụ thiết kế

Bạn có thể lên kế hoạch cho giải pháp theo ba cách chính.

  • một sơ đồ cấu trúc — hiển thị các phần của hệ thống và cách chúng gắn kết với nhau;
  • một sơ đồ luồng — sơ đồ sử dụng các hộp và mũi tên để hiển thị các bước theo thứ tự;
  • giả mã — các bước được viết bằng tiếng Anh đơn giản, giống như mã (không phải là ngôn ngữ thật).
Sơ đồ luồng để cộng các số từ 1 đến n, với biểu tượng bắt đầu/kết thúc, nhập/xuất, quy trình và quyết định, cùng bảng chú giải tên mỗi hình dạng
Sơ đồ luồng cho thuật toán tổng, sử dụng các ký hiệu tiêu chuẩn (bắt đầu/kết thúc, nhập/xuất, quy trình, quyết định)
7.3

Thuật toán

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 tập hợp các bước, theo đúng thứ tự, giải quyết một vấn đề. Mọi thuật toán đều có thể chia thành ba phần:

  • đầu vào — dữ liệu đi vào;
  • xử lý — công việc thực hiện trên dữ liệu;
  • đầu ra — kết quả đầu ra.

Đây được gọi là phân rã thành đầu vào, xử lý và đầu ra. Ví dụ, với bài toán “tìm điểm trung bình của ba điểm số”: đầu vào là ba điểm số; xử lý là cộng chúng lại và chia cho 3; đầu ra là điểm trung bình.

Ba ô — ĐẦU VÀO (3 điểm số), XỬ LÝ (cộng lại, chia cho 3), ĐẦU RA (điểm trung bình) — nối với nhau bằng mũi tên
Mọi thuật toán đều phân rã thành đầu vào, xử lý và đầu ra — ở đây, tìm điểm trung bình của ba điểm số
Từ vựng Luyện tập
English Tiếng Việt
bubble sort/ˈbʌbl sɔːt/ sắp xếp nổi bọt
totalling/ˈtəʊtəlɪŋ/ tổng hợp
counting/ˈkaʊntɪŋ/ đếm
7.4

Xác thực và kiểm chứng

Khi dữ liệu được nhập, bạn kiểm tra nó để giảm thiểu sai sót.

Validation kiểm tra xem dữ liệu có hợp lý và tuân theo các quy tắc hay không. Nó không thể xác minh tính đúng đắn của dữ liệu, mà chỉ đảm bảo dữ liệu đó được phép.

Kiểm tra hợp lệ Điều nó kiểm tra
kiểm tra phạm vi giá trị nằm giữa một giá trị tối thiểu và tối đa được phép
kiểm tra độ dài số lượng ký tự là hợp lệ (ví dụ: mật khẩu ≥ 8)
kiểm tra kiểu dữ liệu thuộc đúng kiểu (ví dụ: số, không phải chữ cái)
kiểm tra sự hiện diện thông tin đã được nhập thực sự (không để trống)
kiểm tra định dạng dữ liệu ở đúng mẫu (ví dụ: ngày tháng dd/mm/yyyy)
chữ số kiểm tra một chữ số tính toán thêm giúp phát hiện lỗi khi nhập một con số

Verification kiểm tra xem dữ liệu có được nhập hoặc sao chép chính xác hay không (không có sai sót khi gõ). Hai phương pháp:

  • kiểm tra trực quan — người so sánh dữ liệu vừa gõ với bản gốc;
  • nhập hai lần — dữ liệu được nhập hai lần và hai bản sao được đối chiếu.
Hai phần: kiểm tra tính hợp lệ xem dữ liệu có được phép hay không bằng cách kiểm tra phạm vi, độ dài, kiểu, sự hiện diện, định dạng và chữ số kiểm tra, nên tuổi 250 bị từ chối; kiểm chứng xem dữ liệu có được sao chép chính xác hay không bằng cách kiểm tra bằng mắt hoặc nhập hai lần, nên phát hiện việc nhập 34 thay cho 43
Kiểm tra tính hợp lệ ngăn dữ liệu không được phép; kiểm chứng phát hiện dữ liệu được phép nhưng bị nhập sai

Viết quy trình kiểm tra tính hợp lệ

Bài thi thường yêu cầu bạn viết mã cho một phép kiểm tra. Hãy dùng vòng lặp yêu cầu nhập lại cho đến khi dữ liệu đầu vào được chấp nhận, và đưa ra thông báo cho người dùng khi dữ liệu không hợp lệ.

Ví dụ minh họa. Viết mã giả để nhập điểm bài kiểm tra, là số nguyên từ 0 đến 100 (kiểm tra phạm vi), và tiếp tục yêu cầu nhập cho đến khi nhận được điểm hợp lệ.

DECLARE Mark : INTEGER
REPEAT
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
    IF Mark < 0 OR Mark > 100
      THEN
        OUTPUT "Invalid: the mark must be from 0 to 100"
    ENDIF
UNTIL Mark >= 0 AND Mark <= 100

Điều kiện UNTIL là phạm vi được chấp nhận, còn điều kiện IF là điều kiện ngược lại. Chú ý OR trong IF: một điểm số không thể đồng thời nhỏ hơn 0 và lớn hơn 100, nên AND ở đó sẽ không bao giờ đúng.

Các phép kiểm tra khác theo cùng một mẫu, với điều kiện khác:

Phép kiểm tra Điều kiện để giá trị hợp lệ
kiểm tra độ dài (mật khẩu có ít nhất 8 ký tự) LENGTH(Password) >= 8
kiểm tra sự hiện diện (phải nhập tên) Name <> ""
kiểm tra phạm vi (tuổi từ 16 đến 65) Age >= 16 AND Age <= 65

Kiểm tra kiểu thường do chính ngôn ngữ lập trình thực hiện, ví dụ khi dữ liệu đầu vào được lưu trong một biến kiểu INTEGER.

Từ vựng Luyện tập
English Tiếng Việt
pseudocode/ˈsuːdəʊkəʊd/ giả mã
algorithm/ˈælɡərɪθəm/ thuật toán
input/ˈɪnpʊt/ dữ liệu đầu vào
processing/ˈprəʊsesɪŋ/ xử lý dữ liệu
output/ˈaʊtpʊt/ dữ liệu đầu ra
validation/ˌvælɪˈdeɪʃn/ kiểm chứng
range check/reɪndʒ tʃek/ kiểm tra phạm vi
length check/leŋθ tʃek/ kiểm tra độ dài
type check/taɪp tʃek/ kiểm tra kiểu
presence check/ˈprezəns tʃek/ kiểm tra sự tồn tại
format check/ˈfɔːmæt tʃek/ kiểm tra định dạng
check digit/tʃek ˈdɪdʒɪt/ chữ số kiểm tra
verification/ˌverɪfɪˈkeɪʃn/ xác minh
visual check/ˈvɪʒuːəl tʃek/ kiểm tra trực quan
double entry/ˈdʌbl ˈentri/ nhập liệu kép
7.5

Bảng truy vết

Một bảng truy vết ghi lại giá trị của từng biến khi thuật toán chạy, từng bước một. Nó giúp bạn:

Bảng truy vết với các cột count, total, output
Một bảng theo dõi ghi lại giá trị của mỗi biến khi chương trình chạy.
  • kiểm tra xem thuật toán có hoạt động chính xác hay không;
  • xác định thuật toán làm gì bằng cách theo dõi nó với dữ liệu đầu vào cho trước.

Ví dụ: truy vết thuật toán này với đầu vào 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total
i total OUTPUT
1 1
2 3
3 6
4 10
5 15 15

Bảng truy vết cho thấy thuật toán cộng dồn từ 1 đến n. Với đầu vào 5, kết quả là 15.

Ví dụ giải. Truy vết thuật toán này và đưa ra kết quả.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV chỉ trả về phần nguyên của phép chia. Take one row per pass: x becomes 10 (count 1), then 5 (count 2), then 2 (count 3), then 1 (count 4). Now x > 1 is false, so the loop stops and the output is 4. Two habits protect these marks: test the condition before each pass rather than after, and write a new row for every pass - trying to hold the values in your head is what makes traces go wrong.

Tìm và sửa lỗi

Một dạng câu hỏi phổ biến đưa ra thuật toán có lỗi và yêu cầu bạn tìm rồi sửa lỗi. Đọc từng dòng và tự hỏi: mọi biến đã được gán giá trị ban đầu chưa? Mỗi vòng lặp có độ dài phù hợp không? Mỗi phép so sánh có đúng chiều không? Đầu ra có ở đúng vị trí không?

Ví dụ minh họa. Thuật toán này phải nhập 10 số và xuất số lớn nhất. Hãy tìm ba lỗi và sửa chúng.

Largest ← 1000
FOR Count ← 1 TO 9
    INPUT Number
    IF Number < Largest
      THEN
        Largest ← Number
    ENDIF
    OUTPUT Largest
NEXT Count
  • Dòng 1: Largest ← 1000 có giá trị ban đầu quá cao, nên không số nào thay thế được nó. Sửa: Largest ← -1000 (hoặc nhập số đầu tiên và dùng nó làm giá trị ban đầu).
  • Dòng 2: vòng lặp chỉ chạy 9 lần. Sửa: FOR Count ← 1 TO 10.
  • Dòng 4: < tìm số nhỏ nhất. Sửa: IF Number > Largest.

Ngoài ra còn có vấn đề với OUTPUT: khi nằm trong vòng lặp, nó in số lớn nhất tính đến thời điểm đó sau mỗi lần nhập. Chuyển nó xuống sau NEXT Count sẽ chỉ in đáp án cuối cùng. Với mỗi lỗi, hãy nêu dòng, giải thích lỗi và viết đầy đủ dòng đã sửa.

Khám phá

Bảng theo dõi

Lặp qua vòng lặp và điền vào bảng theo dõi, mỗi hàng tương ứng với một lần chạy.

Từ vựng Luyện tập
English Tiếng Việt
trace table/treɪs ˈteɪbl/ bảng truy vết
normal/ˈnɔːml/ dữ liệu bình thường
abnormal/əbˈnɔːml/ dữ liệu bất thường
extreme/ekˈstriːm/ dữ liệu cực trị
boundary/ˈbaʊndəri/ dữ liệu biên
7.6

Dữ liệu thử nghiệm

Dữ liệu thử nghiệm là dữ liệu bạn sử dụng để kiểm tra chương trình. Có bốn loại bạn cần biết.

Loại Ý nghĩa Ví dụ (tuổi 0–120 được phép)
bình thường dữ liệu hợp lý nên được chấp nhận 25
bất thường dữ liệu sai cần bị từ chối -4 hoặc “mèo”
cực trị giá trị lớn nhất và nhỏ nhất vẫn còn được phép 0 và 120
biên các giá trị ở hai bên giới hạn (một bên được phép, một bên không) 120 và 121

Ví dụ minh họa. Một chương trình chấp nhận số người đặt bàn từ 1 đến 12. Hãy đưa ra dữ liệu kiểm thử của từng loại cùng kết quả dự kiến.

Loại Dữ liệu kiểm thử Kết quả dự kiến
bình thường 5 được chấp nhận
bất thường 20 (hoặc “sáu”) bị từ chối, kèm thông báo lỗi
cực trị 1 và 12 được chấp nhận
biên 12 và 13 (hoặc 0 và 1) 12 được chấp nhận, 13 bị từ chối

Luôn đưa ra kết quả dự kiến cùng với dữ liệu: một phép kiểm thử chỉ hữu ích khi bạn biết điều gì phải xảy ra. Dữ liệu cực trị chính là giá trị ở giới hạn; dữ liệu biên là một cặp gồm một giá trị ở mỗi phía của giới hạn.

Trục số cho lượt đặt bàn từ 1 đến 12 người: bình thường 5, cực trị 1 và 12, các cặp biên 0 và 1, 12 và 13, bất thường 20
Dữ liệu kiểm thử trên một trục số: các giá trị cực trị nằm tại giới hạn, các cặp biên nằm ở hai phía của giới hạn
7.7

Phương pháp giải chuẩn

Bạn cần biết các thuật toán phổ biến này.

Tìm kiếm tuyến tính

Tìm kiếm tuyến tính so sánh từng mục với mục tiêu, bắt đầu từ đầu danh sách. Dừng khi tìm thấy giá trị hoặc danh sách kết thúc. Danh sách không cần được sắp xếp. Ví dụ sau sử dụng các vị trí 1 đến 4.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

So sánh mẫu. Tìm kiếm 5 so sánh 8, 3 và sau đó 5: ba lần so sánh, với Found trở thành TRUE. Mục thứ tư không được kiểm tra. Tìm kiếm 9 so sánh tất cả bốn giá trị; Found vẫn giữ FALSE. Dừng lại trước khi cố đọc vị trí 5, nằm ngoài mảng này.

Danh sách tám số đang được quét từ trái sang phải, tìm kiếm số 5; bốn số đầu không khớp và số thứ năm được tìm thấy
Một ví dụ khác: tìm kiếm tuyến tính kiểm tra từng mục theo thứ tự từ đầu cho đến khi tìm thấy giá trị

Sắp xếp bọt

Sắp xếp nổi bọt sắp xếp một danh sách theo thứ tự. So sánh các giá trị liền kề và hoán đổi chúng nếu giá trị bên trái lớn hơn. Một lượt đơn lẻ thường không đủ. Phiên bản hoàn chỉnh này lặp lại các lượt cho đến khi một lượt hoàn chỉnh không thực hiện bất kỳ hoán đổi nào.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

Lượt mẫu. Bắt đầu với 8, 3, 5, 1. Trong lượt đầu tiên, danh sách trở thành 3, 8, 5, 1, sau đó 3, 5, 8, 1, rồi 3, 5, 1, 8. Điều này đưa giá trị lớn nhất lên cuối nhưng để lại phần còn lại chưa được sắp xếp. Lượt thứ hai kết thúc tại 3, 1, 5, 8; lượt thứ ba kết thúc tại 1, 3, 5, 8. Lượt thứ tư không thực hiện hoán đổi nào và xác nhận rằng phiên bản này có thể dừng. Đặt lại Swapped về FALSE ở đầu mỗi lượt; đặt nó thành TRUE trong bất kỳ_iteration_iter_hoán đổi_iter nào.

Danh sách nơi cặp đầu tiên 5 và 2 không đúng thứ tự, được hiển thị hoán đổi thành 2 và 5, với ghi chú lặp lại cho mỗi cặp
Một phép so sánh trong một ví dụ khác: sắp xếp nổi bọt hoán đổi các giá trị liền kề không đúng thứ tự, sau đó tiếp tục qua lượt

Tổng hợp và đếm

Tóm cộng thêm từng giá trị cần thiết vào tổng tích lũy: Total ← Total + Value. Đếm thêm 1 cho mỗi mục cần thiết: Count ← Count + 1. Khởi tạo cả hai bằng không trước khi xử lý các giá trị.

Ví dụ mẫu. Bốn lần thử nhập là −20, 4, 50 và 6. Chỉ chấp nhận giá trị nếu nó lớn hơn −20 và nhỏ hơn 50. Ví dụ này xử lý bốn lần thử, không phải bốn giá trị được chấp nhận.

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF
Giá trị thử Tổng sau lần thử Đếm sau lần thử
−20 0 0
4 4 1
50 4 1
6 10 2

Các giới hạn nghiêm ngặt loại bỏ −20 và 50. Cả hai cập nhật đều nằm bên trong bài kiểm tra chấp nhận, nên các lần thử bị loại bỏ không thay đổi tổng cũng như đếm. Trung bình cộng của các giá trị được chấp nhận là:

$$\text{Average}=\frac{\text{Total}}{\text{Count}}=\frac{10}{2}=5$$

Đừng chia cho bốn: chỉ có hai giá trị được thêm vào. Nếu không có giá trị nào được chấp nhận, số đếm là không và không thể tính trung bình; thay vì chia cho không, hãy xuất một thông báo.

Chuyển sang một số lượng cố định các giá trị được chấp nhận. Nếu yêu cầu 50 giá trị được chấp nhận thay vì bốn lần thử, hãy thay thế vòng lặp cố định FOR bằng WHILE Count < 50 và đóng nó lại bằng ENDWHILE. Giữ nguyên phần nhập liệu và kiểm tra chấp nhận bên trong. Các đầu vào bị từ chối giữ cho Count không đổi, do đó yêu cầu thêm một đầu vào. Khi hoàn tất, Count sẽ bằng 50, mặc dù số lần thử có thể nhiều hơn. Xuất tổng và tính trung bình theo Total / Count.

Giá trị lớn nhất, nhỏ nhất và trung bình

Giá trị lớn nhất là giá trị lớn nhất và giá trị nhỏ nhất là giá trị nhỏ nhất. Trung bình là tổng chia cho số lượng giá trị. Đối với danh sách không rỗng, khởi tạo cả hai từ mục đầu tiên của nó. Với mỗi mục còn lại, thay thế giá trị lớn nhất nếu giá trị mới lớn hơn, và thay thế giá trị nhỏ nhất nếu nó nhỏ hơn.

Ví dụ minh họa. Danh sách là −8, −3, −12, −5. Bắt đầu giá trị lớn nhất từ không sẽ thất bại: không có mục nào trong danh sách lớn hơn không, nên thuật toán sẽ xuất ra một số không nằm trong danh sách. Bắt đầu từ −8 hoạt động mà không cần giả sử dữ liệu là dương.

Giá trị vừa xét Giá trị lớn nhất đến giờ Giá trị nhỏ nhất đến giờ
−8 (khởi tạo) −8 −8
−3 −3 −8
−12 −3 −12
−5 −3 −12
DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

Giá trị lớn nhất là −3 và giá trị nhỏ nhất là −12. Trung bình sử dụng tất cả bốn giá trị:

$$\text{Total}=\sum \text{Value}=(-8)+(-3)+(-12)+(-5)=-28$$
$$\text{Average}=\frac{\text{Total}}{\text{Count}}=\frac{-28}{4}=-7$$

Giá trị trung bình nằm giữa giá trị nhỏ nhất và giá trị lớn nhất; đây là một phép kiểm tra hữu ích, chứ không phải bằng chứng để chứng minh việc tính toán chính xác. Khởi tạo từ mục đầu tiên đòi hỏi danh sách không rỗng. Xử lý riêng danh sách rỗng trước khi cố đọc mục đó.

Từ vựng Luyện tập
English Tiếng Việt
linear search/ˈlɪnɪə sɜːtʃ/ tìm kiếm tuyến tính
maximum/ˈmæksɪməm/ giá trị lớn nhất
minimum/ˈmɪnɪməm/ giá trị nhỏ nhất
average/ˈævrɪdʒ/ giá trị trung bình
7.8

Mẹo làm bài thi

  • Bốn giai đoạn chu kỳ sống: phân tích → thiết kế → lập trình → thử nghiệm. Trừu tượng hóa giữ lại những yếu tố quan trọng; phân rã chia nhỏ vấn đề thành các phần.
  • Validation kiểm tra dữ liệu hợp lý (kiểm tra phạm vi, độ dài, kiểu, sự hiện diện, định dạng); verification kiểm tra dữ liệu đã được sao chép chính xác (kiểm tra trực quan hoặc nhập hai lần).
  • Học bốn loại dữ liệu thử nghiệm: bình thường (chấp nhận), bất thường (từ chối), cực đoan (giá trị lớn nhất/nhỏ nhất vẫn được phép), biên (hai bên của giới hạn).
  • Bảng theo dõi (giá trị của mọi biến tại từng bước) cho thấy thuật toán hoạt động như thế nào.
  • Để viết quy trình kiểm tra tính hợp lệ, đặt thao tác nhập trong vòng lặp REPEAT … UNTIL có điều kiện UNTIL là dữ liệu hợp lệ.
  • Khi sửa lỗi, hãy trích dẫn dòng đó và viết đầy đủ dòng đã sửa.
  • Biết các thuật toán chuẩn: tìm kiếm tuyến tính (kiểm tra từng mục lần lượt) và sắp xếp bọt (hoán đổi các cặp liền kề cho đến khi không cần hoán đổi nữa).

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 IGCSE

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

IGCSE, A-Level & AP