สัญลักษณ์, การปรับปรุงทีละขั้น และตรรกะ
แนะนำใหม่| English | ความหมาย |
|---|---|
| notation/nəʊˈteɪʃn/ | สัญลักษณ์วิธี |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | ภาษาอังกฤษที่มีโครงสร้าง |
| pseudocode/ˈsuːdəʊkəʊd/ | รหัสจำลอง |
| flowchart/ˈfləʊtʃɑːt/ | แผนภาพไหล |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | การปรับแต่งทีละขั้น |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | ประโยคตรรกะ |
| Boolean/ˈbuːlɪən/ | บูลีน |
| precedence/ˈpresɪdəns/ | ลำดับความสำคัญ |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | กฎเดมอร์گان |
อัลกอริทึมแรกไม่มีภาษาที่จะเขียนใน
- ในปี 1843 Ada Lovelace เผยแพร่ขั้นตอนสำหรับการคำนวณเลข Bernoulli บนเครื่อง Babbage's Analytical Engine,ซึ่งเป็นเครื่องที่ไม่เคยถูกสร้าง
- ไม่ภาษาคอมพิวเตอร์ มี所以她เขียนอัลกอริทึมเป็นตารางที่มีหมายเลขของดำเนินการ: ระบบสัญลักษณ์ ของเธอเอง
- อัลกอริทึมทุกตัวเริ่มต้นด้วยวิธีนี้ คุณเขียนมันลงในรูปแบบใดรูปแบบหนึ่ง ตรวจสอบให้แน่ใจ แล้วจึงแปลงเป็นโค้ด
- บทเรียนนี้เกี่ยวกับรูปทรงสามอย่างที่ข้อสอบใช้以及如何เปลี่ยนระหว่างกัน以及如何เขียนเงื่อนไขภายในรูปทรงเหล่านั้น
สามระบบสัญลักษณ์
- ภาษาอังกฤษแบบโครงสร้าง (Structured English): ประโยคปกติ,จัดย่อหน้า,พร้อมคำคงที่ไม่กี่คำเช่น
IF,FOR EACH,REPEAT. ดีสำหรับโครงร่างแรก - พ MESSAGECODE: ระบบสัญลักษณ์คำสำคัญ (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT),ใกล้กับโค้ดจริงที่สุดและประเมินตามคู่มือ Cambridge - แผนผังการทำงาน: แผนภูมิของรูปร่างมาตรฐาน สี่เหลี่ยมมุมมนสำหรับ
START/STOP, สี่เหลี่ยมขนมเปียกปูนสำหรับอินพุตและเอาต์พุต,สี่เหลี่ยมผืนผ้าสำหรับกระบวนการ,รูปเพชรสำหรับการตัดสินใจ,ลูกศรสำหรับการไหล
*แผนผังการทำงานสำหรับการหาค่าเฉลี่ยของรายการตัวเลข,วาดด้วยรูปร่างมาตรฐาน
ในแผนภาพไหล (flowchart) รูปทรงใดใช้แทนการตัดสินใจ?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
รูปสี่เหลี่ยมขนมเปียกปูนใช้สำหรับการตัดสินใจ; สี่เหลี่ยมผืนผ้าทรงแหลม = เริ่มต้น/สิ้นสุด, สี่เหลี่ยมขนาน = การรับ/ส่งข้อมูล, สี่เหลี่ยมผืนผ้า = กระบวนการ
จับคู่รูปทรงของแผนภาพไหลกับความหมายของแต่ละรูป
Difficulty 2/5 · 140 coins + a small bonus on first completion today
สี่เหลี่ยมขนมเปียกปูน = การป้อน/แสดงข้อมูล, สี่เหลี่ยมผืนผ้า = กระบวนการ, สี่เหลี่ยมมุมโค้งมน = เริ่มต้น/หยุด, รombus = การตัดสินใจ
จับคู่สัญลักษณ์แต่ละชนิดกับคำอธิบายให้ถูกต้อง
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ทั้งสามรูปแบบนี้บรรยายอัลกอริทึมเดียวกันในระดับความห่างจากโค้ดที่แตกต่างกัน
ตัวอย่างทำพร้อมวิธี: ภาษาอังกฤษแบบโครงสร้างไปเป็นพ MESSAGECODE
- ภาษาอังกฤษแบบโครงสร้าง: ตั้งยอดรวมเป็นศูนย์ สำหรับแต่ละของ N ตัวเลข,บวกมันเข้าไปในยอดรวม หารยอดรวมด้วย N และแสดงผล.
- แต่ละประโยคจะกลายเป็นโครงสร้างหนึ่ง: การกำหนดค่า, ลูป
FORที่มีการกำหนดค่าอยู่ภายใน, แล้วตามด้วยการกำหนดค่าและการแสดงผล
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- ลำดับของประโยคคือลำดับของคำสั่ง ไม่มีการเพิ่มหรือลบสิ่งใดออก
ในอัลกอริทึมการหาค่าเฉลี่ย ลูป FOR ที่เพิ่มตัวเลขแต่ละตัวลงรวมเป็นตัวอย่างของโครงสร้าง ____
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การทำซ้ำบล็อกสำหรับตัวเลขแต่ละตัวคือการวนซ้ำ (iteration) ส่วนคำสั่งกำหนดค่าภายในนั้นใช้เก็บผลรวมสะสม
ตัวอย่างทำพร้อมวิธี: พ MESSAGECODE ไปเป็นแผนผังการทำงาน
- ใช้อัลกอริทึมเดียวกัน
STARTเข้าไปในสี่เหลี่ยมมุมโค้ง,Total ← 0และIndex ← 1เข้าไปในสี่เหลี่ยมผืนผ้า - ลูป
FORกลายเป็นรูปเพชรที่ถามIndex <= N?. ทางออก ใช่ นำไปสู่สี่เหลี่ยมมุมฉากTotal ← Total + Number[Index], แล้วIndex ← Index + 1, และมีลูกศรย้อนกลับ ขึ้น ไปหารูปเพชร - The No exit continues to
Average ← Total / N, an output parallelogram, andSTOP. - ป้ายชื่อทางออกทั้งสองของรูปสี่เหลี่ยมขนมเปียกปูนทุกตัว รูปสี่เหลี่ยมขนมเปียกปูนที่มีทางออกเพียงทางเดียวที่ไม่มีป้ายชื่อไม่ถือเป็นจุดตัดสินใจ
การปรับปรุงทีละขั้น (Stepwise refinement)
- การปรับแต่งแบบขั้นบันได หมายถึงการเขียนอัลกอริทึมเป็นร่างสั้นๆ ก่อน แล้วขยายแต่ละขั้นตอนออกเป็นขั้นตอนย่อยที่ละเอียดขึ้น และทำซ้ำจนกว่าทุกขั้นตอนจะสามารถเขียนโค้ดได้โดยตรง
- แต่ละระดับจะคงโครงสร้างของระดับด้านบนไว้และเพิ่มรายละเอียดเข้าไป ร่างต้นฉบับจะไม่ถูกทิ้งไป: มันกลายเป็นโครงสร้างของโปรแกรม
- การออกแบบจะหยุดลงเมื่อขั้นตอนหนึ่งเป็นบรรทัดเดียวของ伪代码 (pseudocode) หรือโมดูลที่คุณมีอยู่แล้ว
การปรับแต่งแบบขั้นบันไดขยายแต่ละขั้นตอนจนสามารถเขียนโค้ดได้
การปรับปรุงแบบขั้นบันไดคือเทคนิคการ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
คุณปรับปรุงแผนภาพระดับสูงทีละระดับ โดยเพิ่มรายละเอียดขณะรักษาโครงสร้างไว้
ตัวอย่างทำพร้อมกัน: สามระดับ
- ระดับ 1: จัดการผลการสอบ
- ระดับ 2: รับคะแนนแต่ละตัว คำนวณค่าเฉลี่ย นับจำนวนคนที่ผ่าน ทบทวนรายงาน
- ระดับ 3, ปรับปรุง "นับจำนวนคนที่ผ่าน":
Passes ← 0, จากนั้นFORสำหรับคะแนนแต่ละตัว,IF Mark >= 40 THEN Passes ← Passes + 1. - เมื่อถูกถามให้ "อธิบายการปรับแต่งแบบขั้นบันได" ให้ตอบสามแนวคิดหลัก: เริ่มจากร่าง, ขยายแต่ละขั้นตอนออกเป็นขั้นตอนย่อย, หยุดเมื่อแต่ละขั้นตอนสามารถเขียนโปรแกรมได้
การปรับปรุงแบบขั้นตอน: จากแผนภาพไปจนถึงโค้ด
ลดระดับลงทีละขั้น คุณเริ่มจากโจทย์ทั้งหมดในบรรทัดเดียว และขยายแต่ละขั้นตอนให้อยู่ในระดับย่อยลงไปเรื่อยๆ — จนกว่าแต่ละขั้นตอนจะเล็กและเรียบง่ายพอที่จะเขียนโค้ดได้โดยตรง
ในการปรับปรุงแบบขั้นบันได ระดับใหม่แต่ละระดับจะแทนที่ระดับด้านบน ดังนั้นแผนภาพดั้งเดิมจะถูกทิ้งไป
Difficulty 1/5 · 100 coins + a small bonus on first completion today
แต่ละระดับรักษารูปแบบของระดับด้านบนไว้และเพิ่มรายละเอียด แผนภาพจึงกลายเป็นรูปร่างของโปรแกรมสำเร็จรูป
คำสั่งตรรกะ
- เงื่อนไขตรรกะ คือ เงื่อนไข Boolean: มันจะเป็น
TRUEหรือFALSEเท่านั้น, และมันควบคุมIF,WHILEหรือUNTIL - สร้างจากการเปรียบเทียบ (
=,<>,<,>,<=,>=) ที่เชื่อมต่อกันด้วยAND,ORและNOT Mark >= 0 AND Mark <= 100เป็นจริงเฉพาะสำหรับคะแนนในช่วงที่กำหนดAge < 12 OR Age >= 65เป็นจริงสำหรับเด็กและผู้รับเงินบำนาญ
การเปรียบเทียบที่เชื่อมต่อกันด้วย AND, OR และ NOT ทำให้เกิดเงื่อนไขเดียว
ลำดับความสำคัญและวงเล็บ
- ตัวดำเนินการจะถูกนำไปใช้ตามลำดับความสำคัญที่แน่นอน:
NOTก่อน, ตามด้วยAND, แล้วOR - ดังนั้น
A OR B AND CจึงหมายถึงA OR (B AND C), ไม่ใช่(A OR B) AND C. กับA = TRUE,B = FALSE,C = FALSEสิ่งแรกคือTRUEและสิ่งที่สองคือFALSE - ใช้วงเล็บเสมอเมื่อเงื่อนไขผสมกันระหว่าง
ANDและOR. มันไม่มีค่าใช้จ่ายและขจัดความกำกวม
เรียงลำดับตัวดำเนินการตรรกะตามลำดับความสำคัญ จากสูง (ประเมินก่อน) ไปต่ำ
Difficulty 3/5 · 200 coins + a small bonus on first completion today
NOT มีความสำคัญสูงสุด ตามด้วย AND แล้วจึง OR — ใช้วงเล็บเมื่อไม่แน่ใจ
หากไม่มีวงเล็บ A OR B AND C จะหมายถึงอะไร?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
AND มีลำดับความสำคัญสูงกว่า OR ดังนั้นจึงถูกประเมินก่อน ควรใส่วงเล็บเงื่อนไขไว้เสมอเพื่อไม่ให้ใครต้องจดจำ
กฎของเดอ มอร์แกน
- กฎของเดอ มอร์แกน:
NOT (A AND B)มีค่าเท่ากับ(NOT A) OR (NOT B), และNOT (A OR B)มีค่าเท่ากับ(NOT A) AND (NOT B) - ในคำพูด: "not (registered and paid)" หมายความว่า "not registered, or not paid"
- ใช้เพื่อลดรูปเงื่อนไข, หรือเพื่อตรวจสอบอย่างหนึ่ง: เลือกค่าสำหรับ
AและB, คำนวณทั้งสองฝั่ง, และพวกมันต้องตรงกันในทุกกรณี
ตามกฎของเด摩根 NOT (A AND B) มีค่าเท่ากับ (NOT A) OR (NOT B)
Difficulty 1/5 · 100 coins + a small bonus on first completion today
NOT กระจายผ่านวงเล็บและสลับ AND↔OR; เช่นเดียวกัน NOT (A OR B) = (NOT A) AND (NOT B)
ตัวอย่างวิธีทำ: เงื่อนไขจากข้อความ
- กฎ: นักเรียนสามารถเข้าสอบได้หาก they are registered and have either paid or hold a bursary, แต่ not if they are suspended
- ตั้งชื่อตัวแปร Boolean:
Registered,Paid,Bursary,Suspended - ข้อความ:
Registered AND (Paid OR Bursary) AND NOT Suspended - วงเล็บรอบ
Paid OR Bursaryนั้นจำเป็น หากไม่มีวงเล็บ,ANDจะจับก่อนและนักเรียนที่มีทุนการศึกษาแต่ไม่ลงทะเบียนจะได้เข้า
เงื่อนไขใดมีค่าเท่ากับ NOT (Registered AND Paid)? เลือก ทุก ข้อที่ถูกต้อง
Difficulty 2/5 · 140 coins + a small bonus on first completion today
เด摩根เปลี่ยน NOT ของ AND ให้เป็น OR ของ NOTs รูปแบบ AND นั้นเข้มงวดเกินไป: นักเรียนที่ลงทะเบียนแต่ยังไม่ได้ชำระควรทำให้เงื่อนไขต้นฉบับเป็น TRUE และทำให้รูปแบบ AND เป็น FALSE
คะแนนที่หลุดหายไป
a = 1 OR 2ไม่ใช่เงื่อนไข เขียนa = 1 OR a = 2: แต่ละด้านของORต้องเป็นการเปรียบเทียบที่สมบูรณ์NOTใช้กับสิ่งที่ตามหลังมันเท่านั้นNOT A AND Bหมายความว่า(NOT A) AND B- รูปสี่เหลี่ยมขนมเปียกปูนต้องการทางออกสองทางที่มีป้ายชื่อ, และลูปต้องการลูกศรที่กลับขึ้นไปข้างบน Flowchart ที่ไม่มีลูกศรกลับคืนมาไม่ถือเป็นลูป
- Structured English ยังคงมีความชัดเจน "จัดการกับคะแนน" ไม่ถือเป็นขั้นตอน; "เพิ่มคะแนนลงในยอดรวม" ถือเป็นขั้นตอน
เพื่อทดสอบว่า a มีค่าเป็น 1 หรือ 2 เงื่อนไขที่ถูกต้องคือ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
แต่ละด้านของ OR ต้องเป็นการเปรียบเทียบเต็มรูปแบบ: a = 1 OR a = 2. การเขียน a = 1 OR 2 เป็นข้อผิดพลาดที่พบบ่อย
คุณเข้าใจแล้ว
- สามรูปแบบสำหรับการเขียนอัลกอริทึมเดียวกัน: structured English, pseudocode, flowchart (รูปสี่เหลี่ยมขนมเปียกปูน = จุดตัดสินใจ, ลูกศรย้อนกลับ = ลูป)
- stepwise refinement: ร่าง → ขยายแต่ละขั้นตอน → หยุดเมื่อขั้นตอนหนึ่งสามารถเขียนโค้ดได้
- logic statement คือเงื่อนไข Boolean; ลำดับความสำคัญ NOT → AND → OR, ดังนั้นให้ใส่วงเล็บในสิ่งที่ผสมกัน将它们
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B