Notation, sự tinh luyện từng bước và logic
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| notation/nəʊˈteɪʃn/ | ký hiệu |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | tiếng Anh có cấu trúc |
| pseudocode/ˈsuːdəʊkəʊd/ | Giả mã |
| flowchart/ˈfləʊtʃɑːt/ | sơ đồ khối |
| 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 |
| Boolean/ˈbuːlɪən/ | Boolean |
| precedence/ˈpresɪdəns/ | độ ưu tiên |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | định luật De Morgan |
Thuật toán đầu tiên không có ngôn ngữ để viết
- Năm 1843, Ada Lovelace đã xuất bản các bước để tính toán các số Bernoulli trên Máy phân tích Babbage, một cỗ máy chưa từng được chế tạo.
- Không có ngôn ngữ lập trình nào, vì vậy bà đã viết thuật toán dưới dạng bảng các phép toán được đánh số: một ký hiệu riêng của bà.
- Mọi thuật toán vẫn bắt đầu theo cách đó. Bạn viết nó xuống dưới một ký hiệu nào đó, kiểm tra nó, và chỉ sau đó mới chuyển nó thành mã nguồn.
- Bài học này nói về ba ký hiệu mà đề thi sử dụng, cách di chuyển giữa chúng, và cách viết các điều kiện bên trong chúng.
Ba ký hiệu
- Tiếng Anh có cấu trúc: các câu thông thường, thụt vào, với một vài từ cố định như
IF,FOR EACH,REPEAT. Phù hợp cho bản nháp ban đầu. - Giả mã: ký hiệu từ khóa (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), gần giống với mã nguồn thực tế và được chấm điểm dựa trên hướng dẫn của Cambridge. - Sơ đồ khối: biểu đồ các hình dạng tiêu chuẩn. Hình chữ nhật bo tròn cho
START/STOP, hình bình hành cho đầu vào và đầu ra, hình chữ nhật cho quy trình, hình thoi cho quyết định, mũi tên cho luồng lưu thông.
Sơ đồ khối để trung bình hóa một danh sách các số, được vẽ bằng các hình dạng tiêu chuẩn
Trong sơ đồ khối, hình dạng nào đại diện cho một quyết định?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hình thoi là một quyết định; hình chữ nhật bo tròn = bắt đầu/dừng, hình bình hành = đầu vào/đầu ra, hình chữ nhật = quá trình.
Gắn mỗi hình dạng sơ đồ khối với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Hình bình hành = I/O, hình chữ nhật = quá trình, hình chữ nhật bo tròn = start/stop, hình thoi = quyết định.
Gắn mỗi notation với mô tả của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Cả ba mô tả cùng một thuật toán ở các khoảng cách khác nhau từ mã.
Ví dụ giải chi tiết: từ tiếng Anh có cấu trúc sang giả mã
- Tiếng Anh có cấu trúc: Đặt tổng bằng không. Với mỗi trong N số, cộng nó vào tổng. Chia tổng cho N và xuất kết quả.
- Mỗi câu trở thành một cấu trúc: một phép gán, một vòng lặp
FORvới một phép gán bên trong, sau đó là một phép gán và một phép xuất.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- Thứ tự của các câu là thứ tự của các câu lệnh. Không có gì được thêm vào và không có gì bị bỏ sót.
Trong thuật toán trung bình, vòng lặp FOR thêm mỗi số vào tổng là ví dụ về cấu trúc ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Lặp lại một khối cho mỗi số là lặp lại. Việc gán bên trong nó lưu trữ tổng đang tích lũy.
Ví dụ minh họa: mã giả sang sơ đồ khối
- Lấy cùng một thuật toán.
STARTđi vào hình chữ nhật bo tròn,Total ← 0vàIndex ← 1đi vào các hình chữ nhật. - Vòng lặp
FORtrở thành hình thoi hỏi vềIndex <= N?. Lối đi Có dẫn đến hình chữ nhậtTotal ← Total + Number[Index], sau đó làIndex ← Index + 1, và một mũi tên quay lại lên hình thoi. - Lối ra Không tiếp tục đến
Average ← Total / N, một hình bình hành xuất, vàSTOP. - Gán nhãn cho cả hai đầu ra của mỗi hình thoi. Một hình thoi có một đầu ra chưa được gán nhãn không phải là quyết định.
Tinh luyện từng bước (Stepwise refinement)
- Tinh chỉnh từng bước có nghĩa là viết thuật toán dưới dạng dàn ý ngắn gọn, sau đó mở rộng từng bước thành các bước con chi tiết hơn, và lặp lại cho đến khi mọi bước đều có thể mã hóa trực tiếp.
- Mỗi cấp độ giữ nguyên cấu trúc của cấp độ phía trên và bổ sung thêm chi tiết. Dàn ý không bị loại bỏ: nó trở thành cấu trúc của chương trình.
- Thiết kế dừng lại khi một bước chỉ còn một dòng giả mã hoặc một mô-đun mà bạn đã có sẵn.
Tinh chỉnh từng bước mở rộng từng bước cho đến khi có thể mã hóa
Tinh chỉnh từng bước là kỹ thuật:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Bạn tinh chỉnh bản phác thảo cấp cao từng mức, thêm chi tiết trong khi giữ nguyên cấu trúc.
Ví dụ minh họa: ba cấp độ
- Cấp độ 1: Xử lý kết quả kỳ thi.
- Cấp độ 2: Nhập điểm. Tính điểm trung bình. Đếm số người đạt. Xuất báo cáo.
- Cấp độ 3, tinh chỉnh "đếm số người đạt":
Passes ← 0, sau đóFORmỗi điểm,IF Mark >= 40 THEN Passes ← Passes + 1. - Khi được yêu cầu "mô tả tinh chỉnh từng bước", hãy đưa ra ba ý tưởng: bắt đầu từ dàn ý, mở rộng từng bước thành các bước nhỏ hơn, dừng lại khi mỗi bước có thể lập trình được.
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.
Trong tinh chỉnh từng bước, mỗi mức mới thay thế mức phía trên, vì vậy bản phác thảo gốc bị loại bỏ.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi mức giữ nguyên cấu trúc của mức phía trên và thêm chi tiết. Bản phác thảo trở thành hình dáng của chương trình hoàn thiện.
Câu lệnh logic
- Một câu logic là một điều kiện Boolean: nó có giá trị
TRUEhoặcFALSE, và nó điều khiển mộtIF, mộtWHILEhoặc mộtUNTIL. - Nó được xây dựng từ các phép so sánh (
=,<>,<,>,<=,>=) được nối với nhau bởiAND,ORvàNOT. Mark >= 0 AND Mark <= 100chỉ đúng đối với điểm trong khoảng xác định.Age < 12 OR Age >= 65đúng đối với trẻ em và người nhận lương hưu.
Các phép so sánh nối với nhau bởi AND, OR và NOT tạo thành một điều kiện
Thứ tự ưu tiên và ngoặc
- Các toán tử được áp dụng theo thứ tự ưu tiên cố định:
NOTtrước, sau đóAND, rồiOR. - Vì vậy
A OR B AND Ccó nghĩa làA OR (B AND C), không phải(A OR B) AND C. VớiA = TRUE,B = FALSE,C = FALSE, cái đầu tiên làTRUEvà cái thứ hai làFALSE. - Sử dụng ngoặc.annotations một điều kiện kết hợp
ANDvàOR. Chúng không tốn kém gì và loại bỏ sự mơ hồ.
Sắp xếp các toán tử logic theo thứ tự ưu tiên, từ cao (được đánh giá trước) đến thấp.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
NOT có độ ưu tiên chặt nhất, sau đó là AND, rồi đến OR — hãy dùng ngoặc đơn nếu không chắc chắn.
Không có ngoặc đơn, A OR B AND C có nghĩa là gì?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
AND có độ ưu tiên cao hơn OR, nên nó được đánh giá trước. Hãy đặt điều kiện trong ngoặc đơn dù sao đi nữa, để không ai phải nhớ.
Định luật De Morgan
- Định luật De Morgan:
NOT (A AND B)tương đương với(NOT A) OR (NOT B), vàNOT (A OR B)tương đương với(NOT A) AND (NOT B). - Bằng lời: "không (đã đăng ký và đã trả tiền)" có nghĩa là "không đăng ký, hoặc không trả tiền".
- Sử dụng nó để đơn giản hóa một điều kiện, hoặc để kiểm tra một điều kiện: chọn các giá trị cho
AvàB, tính toán cả hai vế, và chúng phải khớp nhau trong mọi trường hợp.
Theo định lý De Morgan, NOT (A AND B) giống như (NOT A) OR (NOT B).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
NOT phân phối qua ngoặc đơn và đảo ngược AND↔OR; tương tự NOT (A OR B) = (NOT A) AND (NOT B).
Ví dụ minh họa: một điều kiện từ văn bản
- Quy tắc: một học sinh được dự thi nếu họ đã đăng ký và đã trả tiền hoặc có học bổng, nhưng không nếu họ bị đình chỉ.
- Đặt tên cho các biến Boolean:
Registered,Paid,Bursary,Suspended. - Câu điều kiện:
Registered AND (Paid OR Bursary) AND NOT Suspended. - Các ngoặc xung quanh
Paid OR Bursarylà thiết yếu. Nếu không có chúng,ANDsẽ liên kết trước và một học sinh có học bổng nhưng không đăng ký vẫn có thể vào.
Điều kiện nào tương đương với NOT (Registered AND Paid)? Chọn tất cả các đáp án áp dụng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
De Morgan biến NOT của một AND thành OR của các NOT. Phiên bản AND quá khắt khe: một học sinh đã đăng ký nhưng chưa thanh toán nên khiến điều kiện ban đầu TRUE, và nó khiến phiên bản AND FALSE.
Điểm số dễ mất
a = 1 OR 2không phải là một điều kiện. Hãy viếta = 1 OR a = 2: mỗi bên củaORphải là một phép so sánh hoàn chỉnh.NOTchỉ áp dụng cho những gì theo sau nó.NOT A AND Bcó nghĩa là(NOT A) AND B.- Một hình thoi cần hai đầu ra được gán nhãn, và một vòng lặp cần mũi tên quay ngược lên trên. Một lưu đồ thị không có mũi tên quay lại không phải là vòng lặp.
- Tiếng Anh có cấu trúc vẫn rất chính xác. "Xử lý các điểm" không phải là một bước; "cộng điểm vào tổng" thì có.
Để kiểm tra xem a có bằng 1 hay 2, điều kiện đúng là:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi bên của OR phải là một phép so sánh đầy đủ: a = 1 OR a = 2. Viết a = 1 OR 2 là một lỗi phổ biến.
Bạn đã nắm vững
- Ba cách biểu diễn cho một thuật toán: tiếng Anh có cấu trúc, giả mã, lưu đồ thị (hình thoi = quyết định, mũi tên ngược = vòng lặp)
- tinh chỉnh từng bước: dàn ý → mở rộng từng bước → dừng lại khi một bước có thể mã hóa
- một câu logic là một điều kiện Boolean; thứ tự ưu tiên NOT → AND → OR, vì vậy hãy đặt ngoặc bất cứ điều gì kết hợp chúng
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B