ข้ามไปยังเนื้อหา

การออกแบบอัลกอริทึมและการแก้ปัญหา

Computer Science A-Level · หัวข้อ 9

ดูสไลด์ ฝึกฝน
บทเรียนวิดีโอสำหรับหัวข้อนี้ เปิดหน้าวิดีโอ
14:30

การคิดเชิงคำนวณ

นี่คืองาน: สร้างระบบเพื่อจัดการสต็อกของร้านทั้งหมด — สินค้าทุกชิ้น การขายทุกครั้ง การจัดส่งทุกครั้ง รายงานทุกฉบับ ในฐานะปัญหาใหญ่เดียว มัน…**

บรรยายภาษาอังกฤษ · สลับคำบรรยายภาษาอังกฤษและภาษาจีนได้

9.1

การคิดเชิงคำนวณ

หลักสูตร
ผู้เข้าสอบควรสามารถ: หมายเหตุและคำแนะนำ
แสดงความเข้าใจใน การ abstraction ความจำเป็นและประโยชน์ของการใช้ abstraction อธิบายวัตถุประสงค์ของ abstraction สร้างโมเดล abstractions ของระบบโดยรวมเฉพาะรายละเอียดที่สำคัญเท่านั้น
อธิบายและใช้ decomposition แยกปัญหาออกเป็นปัญหาย่อย นำไปสู่แนวคิดของโมดูลโปรแกรม (procedure / function)

แหล่งที่มา: หลักสูตร Cambridge International

Computational thinking คือชุดเครื่องมือทางความคิดสำหรับ วิเคราะห์ปัญหาและออกแบบโซลูชันที่คอมพิวเตอร์สามารถรันได้ สองอย่างที่สำคัญคือ abstraction และ decomposition

A part-finished jigsaw puzzle
Computational thinking แตกปัญหาใหญ่ออกเป็นส่วนย่อยๆ ที่ง่ายขึ้น — เหมือนการต่อจิ๊กซอว์

Abstraction

Abstraction หมายถึง รักษาคุณสมบัติที่สำคัญ ของปัญหาและ ละเว้นรายละเอียดที่ไม่เกี่ยวข้อง เพื่อสร้างโมเดลที่เรียบง่ายกว่า

ตัวอย่าง:

  • แผนที่ระบบรถไฟ เก็บสถานีและเส้นทางแต่ทิ้งภูมิศาสตร์
  • class ในการเขียนโปรแกรมแบบ object-oriented เก็บเฉพาะ attributes และ methods ที่ระบบต้องการ
  • function ซ่อนงานบางส่วนไว้หลังชื่อ

โมเดลเต็มรูปแบบของปัญหาจริงจะใหญ่เกินไปที่จะพิจารณาได้ ดังนั้น abstraction จึงจำเป็น

ผู้ประเมินถามถึง วัตถุประสงค์ ของการ abstraction และถึง ประโยชน์ ที่ได้รับ วัตถุประสงค์: เพื่อสร้างโมเดลที่เรียบง่ายขึ้นของปัญหา โดยรวมเฉพาะรายละเอียดที่จำเป็นในการแก้ปัญหานั้นเท่านั้น ประโยชน์: ปัญหามีความเข้าใจง่ายและเขียนโปรแกรมได้ง่ายขึ้น; โปรแกรมมีขนาดเล็กกว่าและเขียนหรือทดสอบได้เร็วขึ้น; โมเดลเดียวกันนี้สามารถนำไปใช้ซ้ำกับปัญหาที่มีลักษณะคล้ายกันได้ เมื่อถูกให้ สร้างโมเดลแบบ abstract ของระบบ ให้ระบุเพียงข้อมูลและการกระทำที่งานนั้นต้องการ สำหรับตารางเวลาเรียนของโรงเรียน หมายความว่าชั้นเรียน ห้องเรียน ครู และช่วงเวลา; ไม่รวมถึงสีของห้องหรืออายุของครู

Abstraction เปลี่ยนภูมิศาสตร์จริงที่รกชักรว (เส้นทางคดเคี้ยวพร้อมอาคารกระจายตัว) ให้เป็นแผนที่รถไฟฟ้าที่สะอาดตา — จุดวงกลมสถานีวางเว้นระยะเท่ากันบนเส้นตรง รักษาตำแหน่งสถานีและเส้นทางไว้แต่ทิ้งภูมิศาสตร์ไป
Abstraction รักษาสินค้าหลัก (สถานีและเส้นทาง) ทิ้งรายละเอียดที่ไม่เกี่ยวข้อง (ภูมิศาสตร์)

การแยกส่วน (Decomposition)

การแยกส่วน (Decomposition) หมายถึง การแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยๆ ที่มีขนาดเล็กลง ซึ่งแต่ละส่วนจะแก้ได้ง่ายกว่าและดำเนินการทีละส่วน

  1. หาองค์ประกอบหลักของงาน
  2. แบ่งแต่ละส่วนออกเป็นงานย่อยที่มีขนาดเล็กกว่า
  3. ทำต่อไปจนกว่าแต่ละส่วนจะมีขนาดเล็กพอที่จะออกแบบได้โดยตรง
  4. แก้ไขงานย่อยแล้วนำมารวมกัน

สำหรับการควบคุมสต็อก: "จัดการสต็อก" → "บันทึกการขาย", "รับสินค้าเข้า", "ทำรายงาน" → ("บันทึกการขาย") "ค้นหาผลิตภัณฑ์", "ลดจำนวนสต็อก", "บันทึกธุรกรรม" การแยกส่วนทำให้ปัญหาใหญ่จัดการได้ ทำให้ทีมแบ่งงานออกได้ และให้โค้ดที่เป็นโมดูลาร์ — แต่ละโมดูลกลายเป็น procedure หรือฟังก์ชัน

"Explain why decomposition is used" is a three-mark question with a fixed shape. Give three separate benefits: each sub-problem is small enough to design, code and test on its own; different programmers can work on different modules at the same time; a module that already exists (or a library routine) can be reused, and a fault is easier to find because it lies inside one module. A structure chart (topic 12) is the diagram of a decomposition: the program at the top, its modules beneath, and the data passed between them.

ต้นไม้ที่มี "จัดการสต็อก" ด้านบน แยกย่อยเป็นโมดูล "บันทึกการขาย", "รับสินค้า", "สร้างรายงาน" และ "บันทึกการขาย" แยกย่อยเป็นงานย่อย "ค้นหาสินค้า", "ลดจำนวนสต็อก" และ "บันทึกธุรกรรม"
การแยกโปรแกรมออกเป็นส่วนย่อย (modules) และส่วนย่อยย่อย (sub-modules)
สำรวจ

แก้ปัญหาด้วยวิธีการทางคอมพิวเตอร์

ผ่านขั้นตอนหลักสี่ประการตามลำดับการใช้งาน — แยกปัญหาออกเป็นส่วนย่อย ระบุสิ่งที่ซ้ำซ้อน ลดทอนเหลือแก่นแท้ แล้วเขียนขั้นตอน

คำศัพท์ ฝึกฝน
English ไทย
computational thinking/ˌkɒmpjuːˈteɪʃənl ˈθɪŋkɪŋ/ การคิดเชิงคำนวณ
abstraction/əbˈstrækʃn/ การ abstraction
decomposition/ˌdiːkɒmpəˈzɪʃn/ การแยกย่อย
sub-problem/sʌb ˈprɒbləm/ ปัญหาย่อย
procedure/prəˈsiːdʒə/ ขั้นตอน
modules/ˈmɒdjuːlz/ โมดูล
9.2

อัลกอริทึม

หลักสูตร
ผู้เข้าสอบควรสามารถ: หมายเหตุและคำแนะนำ
แสดงความเข้าใจว่า algorithm คือวิธีแก้ปัญหาที่แสดงออกในรูปแบบลำดับขั้นตอนที่กำหนดไว้
ใช้ชื่อตัวแปรที่เหมาะสมสำหรับการแทนค่าข้อมูลที่ใช้ในปัญหาและแสดงผลลัพธ์โดยใช้ identifier table
เขียน pseudocode ที่มีการป้อนข้อมูล ประมวลผล และแสดงผล
เขียน pseudocode โดยใช้โครงสร้างพื้นฐานสามอย่างคือ sequence, selection และ iteration (repetition)
บันทึก อัลกอริทึม แบบง่ายโดยใช้คำอธิบายภาษาอังกฤษที่มีโครงสร้าง, flowchart หรือ pseudocode
เขียน pseudocode จาก: • การบรรยาย structured English • flowchart
วาด flowchart จาก: • การบรรยาย structured English • pseudocode
อธิบายและใช้กระบวนการ stepwise refinement เพื่อแสดงอัลกอริทึมในระดับรายละเอียดเพียงพอสำหรับการเขียนโปรแกรมงานนั้น
ใช้ประโยคตรรกะเพื่อกำหนดส่วนหนึ่งของวิธีแก้ algorithm

แหล่งที่มา: หลักสูตร Cambridge International

Bubble sort, pas-by-pass

อัลกอริทึม (Algorithm) คือ วิธีแก้ปัญหาที่แสดงออกมาเป็นลำดับขั้นตอนที่กำหนดไว้อย่างชัดเจน ขั้นตอนแต่ละขั้นต้อง ไม่มีความกำกวม (Unambiguous) (มีความหมายเดียว), เป็นแบบกำหนดเอง (Deterministic) (อินพุตเท่าเดิม → เอาต์พุตเท่าเดิม), มีขอบเขตจำกัด (Finite) (ขั้นตอนจบลง), และ มีประสิทธิภาพ (Effective) (แต่ละขั้นทำได้จริง) อัลกอริทึมบอก สิ่งที่ต้องทำ โดยไม่ขึ้นอยู่กับภาษาโปรแกรมมิ่งที่ใช้ในการนำไปปฏิบัติ

สำรวจ

การเลือก: ตามเส้นทาง IF / ELSE

ลากคะแนนและดูว่าเส้นทางไหนทำงาน การเลือกจะทดสอบเงื่อนไขทีละข้อและเลือกเส้นทางที่ TRUE เป็นข้อแรก — นั่นคือวิธีการทำงานของ IF … ELSE IF … ELSE

คำศัพท์ ฝึกฝน
English ไทย
algorithm/ˈælɡərɪθəm/ อัลกอริทึม
unambiguous/ʌnæmˈbɪɡjuːəs/ ไม่กำกวม
deterministic/dɪˌtɜːmɪˈnɪstɪk/ แบบกำหนดได้
ดูบทเรียน
9.2

ตารางตัวชี้จำ (Identifier table)

เมื่อเริ่มอัลกอริทึม ให้ระบุงานข้อมูลทั้งหมดไว้ใน ตารางตัวชี้จำ — ชื่อตัวชี้จำ (variable name), ชนิดของข้อมูล, และคำอธิบาย ตารางสอบจะมีสามคอลัมน์เหล่านี้เท่านั้น:

ตัวชี้จำ ชนิดของข้อมูล คำอธิบาย
Category STRING ประเภทสินค้า
SaleDate DATE เวลาที่สินค้าถูกขาย
ItemCost REAL ราคาต้นทุนของสินค้า
InStock BOOLEAN TRUE หากมีสินค้าคงเหลือ
Sales ARRAY[1:30] OF REAL ยอดรวมยอดขายรายวัน 30 วันล่าสุด

ใช้ชื่อที่ สื่อความหมาย (ItemCost ไม่ใช่ x):.Identifier เริ่มด้วยตัวอักษร ไม่มีช่องว่าง และเขียนรูปแบบเดียวกันทุกครั้งที่มีปรากฏ ชนิดทั่วไปคือ INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE รวมถึงอาร์เรย์ ตารางบังคับให้คุณตั้งชื่อข้อมูลทุกชิ้นก่อนเขียนโค้ด และข้อสอบแบบ "เติมตาราง identifier" ให้คะแนนหนึ่งข้อต่อชนิดข้อมูลหรือคำอธิบายที่ถูกต้อง ดังนั้นจงเขียนชนิดข้อมูลให้ตรงกับคู่มือ伪代码 exactly

An identifier table listing each variable with its name, data type and description, for example ItemCost as a REAL for the cost of the item
ตารางตัวแปรระบุชื่อข้อมูลทุกชิ้นก่อนเริ่มเขียนโค้ด
คำศัพท์ ฝึกฝน
English ไทย
identifier table/aɪˈdentɪfaɪə ˈteɪbl/ ตารางตัวระบุ
identifier/aɪˈdentɪfaɪə/ ตัวระบุ
variable/ˈveərɪəbl/ ตัวแปร
data type/ˈdeɪtə taɪp/ ชนิดข้อมูล
Boolean/ˈbuːlɪən/ บูลีน
9.2

Pseudocode — โครงสร้างพื้นฐานทั้งสาม

Pseudocode คือวิธีการอธิบายอัลกอริทึมที่มีโครงสร้างและเป็นกลางต่อภาษา

The three basic constructs as mini-flowcharts: sequence runs step A then B then C; selection tests a condition and does X or Y; iteration repeats a body while a condition holds, looping back
Block สร้างสร้างของอัลกอริทึมทั้งสาม: Sequence, Selection และ Iteration

1. ลำดับ (Sequence)

ขั้นตอนทำงานตามลำดับ (sequence):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. การเลือก (Selection)

การตัดสินใจว่าขั้นตอนไหนจะทำงาน โดยอ้างอิงจากเงื่อนไข (selection):

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

สำหรับตัวเลือกเพิ่มเติม ให้ใช้ CASE OF ... ENDCASE.

3. การวนซ้ำ (Iteration)

การทำซ้ำบล็อก (iteration, loop):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

ลูป WHILE ตรวจสอบเงื่อนไข ก่อน การวนแต่ละรอบ (อาจไม่ทำงานเลย); ลูป REPEAT...UNTIL ตรวจสอบ หลัง การวนแต่ละรอบ (ทำงานอย่างน้อยครั้งเสมอ)

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

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100
Two flowcharts side by side. WHILE tests the condition first, so the body may never run: the diamond sits above the body and the No branch leaves the loop. REPEAT UNTIL runs the body first and tests after it, so the body always runs at least once: the body sits above the diamond and the No branch returns to it
ลูป WHILE ตรวจสอบก่อนเนื้อหาทำงาน; ลูป REPEAT ... UNTIL ตรวจสอบหลังจากนั้น ดังนั้นเนื้อหาจึงทำงานอย่างน้อยครั้งเสมอ

การเลือกชนิดลูปก็เป็นคะแนนเอง: FOR เมื่อทราบจำนวนรอบ (ลูปควบคุมโดยนับ); WHILE เมื่อลูปอาจไม่ทำงานเลย (ลูปก่อนเงื่อนไข); REPEAT ... UNTIL เมื่อต้องทำงานอย่างน้อยครั้งเดียว เช่น ในการตรวจสอบอินพุต (ลูปหลังเงื่อนไข) คำตอบ "อธิบายโครงสร้างการวนซ้ำ" ต้องระบุชื่อโครงสร้าง บอกว่าเงื่อนไขถูกทดสอบที่ไหน และบอกผลกระทบ (ศูนย์ครั้งหรืออย่างน้อยครั้งเดียว)

การดำเนินการทั่วไป

  • การกำหนดค่า: x ← 5 (ลูกศร; = ใช้สำหรับการเปรียบเทียบ)
  • อินพุต/เอาต์พุต: INPUT variable, OUTPUT expression.
  • การเปรียบเทียบ =, <>, <, >, <=, >=; Logic AND, OR, NOT.
  • การคำนวณ + - * /, บวก DIV (การหารจำนวนเต็ม) และ MOD (เศษเหลือ).
  • สตรีง: LENGTH, LEFT, RIGHT, MID, และ & สำหรับ การต่อ (joining).

伪代码 ที่ข้อสอบคาดหวัง

ทุกคำตอบแบบ伪代码 จะถูกตรวจตามคู่มือ伪代码 ของ Cambridge ที่เผยแพร่แล้ว เขียนรูปแบบเหล่านี้ให้ตรงไปตรงมา:

โครงสร้าง 伪代码
ตัวแปร DECLARE Total : INTEGER
อาร์เรย์ DECLARE Marks : ARRAY[1:30] OF REAL
ค่าคงที่ CONSTANT MaxTries = 3
การกำหนดค่า Total ← Total + Value
การรับ/ส่งข้อมูล INPUT Name
OUTPUT "Hello ", Name
การเลือกเงื่อนไข CASE OF Choice
1 : OUTPUT "Add"
OTHERWISE OUTPUT "Error"
ENDCASE
ลูป FOR FOR i ← 1 TO 10 STEP 2 ... NEXT i
ลูป WHILE WHILE Total < 100 DO ... ENDWHILE
ลูป REPEAT REPEAT ... UNTIL Mark >= 0
การคำนวณจำนวนเต็ม 17 DIV 5 = 3
17 MOD 5 = 2
สตรีง LENGTH(S), LEFT(S, 3), RIGHT(S, 2)
MID(S, 2, 4), TO_UPPER(S), TO_LOWER(S)
การแปลงชนิดข้อมูล INT(3.7) = 3, NUM_TO_STR(12)
STR_TO_NUM("4.5"), ASC('A') = 65, CHR(66) = 'B'
สุ่ม RAND(100)
INT(RAND(100)) + 1

RAND(100) ให้ค่าจริงตั้งแต่ 0 ขึ้นไปจนถึง (แต่ไม่รวม) 100. INT(RAND(100)) + 1 ให้ค่าจำนวนเต็มตั้งแต่ 1 ถึง 100.

สองนิสัยที่ทำให้ได้คะแนนในทุกข้อคือ: ประกาศตัวแปรทุกตัวที่คุณใช้ พร้อมระบุชนิดจากตารางไถ่ชื่อ, และ เริ่มต้นค่าตัวนับและผลรวมทั้งหมด (Count ← 0, Total ← 0) ก่อนลูปที่จะทำการเปลี่ยนแปลงค่าเหล่านั้น.

ข้อมูลเข้า → กระบวนการ → ข้อมูลออก

โปรแกรมทุกตัวมีโครงสร้างดังนี้:

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

การระบุข้อมูลเข้าและข้อมูลออกก่อนจะช่วยให้อัลกอริทึมเป็นระเบียบมากขึ้น

Worked example. Write pseudocode that inputs 100 integers and outputs how many of them, and the total of those, that lie between 10 and 20 inclusive.

ตารางไถ่ชื่อ: Count : INTEGER (ตัวนับรอบลูป), Value : INTEGER (จำนวนเต็มที่เพิ่งรับเข้ามา), InRange : INTEGER (จำนวนที่มีอยู่ในช่วง), Total : INTEGER (ผลรวมของจำนวนเหล่านั้น).

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

หากโจทย์ขอให้ "ระบุโครงสร้าง 2 แบบและอธิบายการใช้งานของแต่ละแบบ" ตอบในรูปแบบเดียวกัน: การซ้ำซ้อน, ลูป FOR, ทำการรับข้อมูลซ้ำ 100 ครั้ง; การเลือกเงื่อนไข, คำสั่ง IF, เพิ่มค่าก็ต่อเมื่ออยู่ในช่วงเท่านั้น

ตัวอย่างคำอธิบาย. โปรแกรมสุ่มเลขลับจำนวนเต็มจาก 1 ถึง 100 ผู้ใช้ทายจนถูก; หลังจากรายแต่ละครั้งโปรแกรมจะแสดง "ต่ำเกินไป" หรือ "สูงเกินไป" และท้ายที่สุดจะแสดงว่าทายไปทั้งหมดกี่ครั้ง

ตารางไถ่ชื่อ: Secret : INTEGER (เลขที่ต้องทาย), Guess : INTEGER (สิ่งที่ผู้ใช้พิมพ์), Tries : INTEGER (จำนวนครั้งที่ทายมาจนถึงตอนนี้).

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"

การใช้ REPEAT ... UNTIL loop เป็นทางเลือกที่เหมาะสมเพราะผู้ใช้อาจต้องทายอย่างน้อยหนึ่งครั้ง คะแนนจะอยู่ที่: การสุ่มเลขในช่วงที่ถูกต้อง, ลูปที่จบลงเมื่อทายถูก, ตัวนับที่เริ่มที่ศูนย์และเพิ่มขึ้นภายในลูป, ข้อความสองประเภทภายใต้เงื่อนไขที่ถูกต้อง, และการแสดงผลสุดท้าย

แผนภาพไหลของเกมทายเลข: เริ่มต้น, จากนั้นกำหนด Secret เป็นเลขสุ่มจาก 1 ถึง 100 และ Tries เป็น 0, จากนั้นรับค่าทาย, เพิ่ม 1 เข้ากับ Tries, ตรวจสอบว่าค่าทายเท่ากับ Secret หรือไม่ (Yes นำไปสู่การแสดงผล Tries และหยุด), มิฉะนั้นตรวจสอบว่าค่าทายน้อยกว่า (Yes แสดง Too low, No แสดง Too high), และการแสดงผลทั้งสองวนกลับไปที่การรับค่า
เกมทายเลขเดิมในรูปแผนภาพไหล: สี่เหลี่ยมขนมเปียกปูนตัดสินใจทั้งสองคือคำสั่ง IF ทั้งสอง, และลูกศรย้อนกลับคือลูป REPEAT ... UNTIL

ตัวอย่างคำอธิบาย. แสดงตัวเลขสุ่มจำนวนเต็มที่แตกต่างกันสองตัว แต่ละตัวอยู่ระหว่าง $-10$ ถึง $10$ (รวมขอบเขต)

มีค่าที่เป็นไปได้ 21 ค่า ดังนั้น INT(RAND(21)) จึงให้ค่าตั้งแต่ 0 ถึง 20 และการลบ 10 จะย้ายช่วงให้เป็น $-10$ ถึง $10$. ตัวที่สองต้องถูกสุ่มใหม่จนกว่าจะต่างจากตัวแรก:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second
โปรแกรมทุกตัวมีโครงสร้าง ข้อมูลเข้า, กระบวนการ, ข้อมูลออก, แสดงด้วยตัวอย่างพื้นที่: รับความยาวและความกว้าง, ประมวลผลด้วยการคูณ, แสดงพื้นที่
โปรแกรมทุกตัวมีโครงสร้าง ข้อมูลเข้า, กระบวนการ, ข้อมูลออก
สำรวจ

การเลือกแบบ IF … ELSE

เปลี่ยนค่าแล้วดูว่า สาขา ใดทำงาน — โปรแกรมตัดสินใจอย่างไร

คำศัพท์ ฝึกฝน
English ไทย
sequence/ˈsiːkwəns/ ลำดับ
pseudocode/ˈsuːdəʊkəʊd/ รหัสจำลอง
flowchart/ˈfləʊtʃɑːt/ แผนภาพไหล
selection/sɪˈlekʃn/ การเลือก
iteration/ˌɪtəˈreɪʃn/ รอบการทำงาน
loop/luːp/ ลูป
count-controlled loop/kaʊnt kənˈtrəʊld luːp/ ลูปควบคุมด้วยนับ
pre-condition loop/priː kənˈdɪʃn luːp/ ลูปก่อนเงื่อนไข
post-condition loop/pəʊst kənˈdɪʃn luːp/ ลูปหลังเงื่อนไข
9.2

สามรูปแบบการเขียน

อัลกอริทึมเดียวสามารถเขียนได้ด้วยสามวิธี

  • ภาษาอังกฤษเชิงโครงสร้าง — ภาษาธรรมชาติพร้อมการเยื้องและคำสำคัญที่กำหนด; เหมาะสำหรับการอธิบายระดับสูง
  • แผนภาพไหล — แผนภูมิที่มีรูปร่างมาตรฐาน:
รูปร่าง ความหมาย
สี่เหลี่ยมมุมโค้งมน เริ่มต้น / หยุด
สี่เหลี่ยมขนาน รับ/ส่งข้อมูล
สี่เหลี่ยมผืนผ้า กระบวนการ
สี่เหลี่ยมขนมเปียกเปียก การตัดสินใจ
ลูกศร การไหลของการควบคุม
  • 伪代码 — เครื่องหมายคำศัพท์ข้างต้น; ใกล้เคียงกับโค้ดมากที่สุด

คุณควรสามารถแปลงระหว่างคู่ใดๆ ได้: แต่ละ IF คือสี่เหลี่ยมขนมเปียกเปียกการตัดสินใจ, แต่ละลูปคือลูกศรย้อนกลับ, และลำดับคือการซ้อนสี่เหลี่ยม

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

แผนภาพไหลสำหรับการหาค่าเฉลี่ย: จุดเริ่มต้นและจุดสิ้นสุดสี่เหลี่ยมมุมโค้งมน, สี่เหลี่ยมขนานสำหรับรับ/ส่งข้อมูล, สี่เหลี่ยมผืนผ้าสำหรับกระบวนการ, และสี่เหลี่ยมขนมเปียกเปียก "count < n?" ที่สาขา Yes ย้อนกลับไปอ่านค่าถัดไป
แผนภาพไหลสำหรับการหาค่าเฉลี่ยของรายการตัวเลข โดยใช้รูปร่างมาตรฐาน
9.2

การปรับปรุงทีละขั้น

การปรับปรุงทีละขั้น เริ่มจากโครงร่างระดับสูงแล้ว ขยายแต่ละขั้นตอน จนมีขนาดเล็กพอที่จะเขียนโค้ดได้. สำหรับการหาค่าเฉลี่ยของ $n$ จำนวน:

ระดับ 1:

Read in the numbers
Compute the average
Output the average

ระดับ 2:

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

การปรับปรุงแต่ละขั้นจะรักษาโครงสร้างเดิมไว้และเพิ่มรายละเอียดเข้าไป

A six-mark "apply stepwise refinement" question gives you a high-level outline and wants each step expanded into the concrete statements a programmer could code. Keep the steps in the same order, name the data each step reads or produces, and stop when every line is a single input, assignment, output, loop or condition. For example, "validate the password" becomes: input the password; check its length is at least 8; check it contains at least one digit; output "accepted" if both checks pass, otherwise output "rejected".

Stepwise refinement: Level 1 outline (อ่านจำนวน, คำนวณค่าเฉลี่ย, แสดงค่าเฉลี่ย) ขยายเป็น Level 2 伪代码 รายละเอียดพร้อมลูปอ่านและการหาร
การปรับระดับทีละขั้น: ขยายแต่ละขั้นตอนระดับสูงให้เป็น伪โค้ดที่ละเอียด
สำรวจ

การปรับปรุงแบบขั้นตอน: จากแผนภาพไปจนถึงโค้ด

ลดระดับลงทีละขั้น คุณเริ่มจากโจทย์ทั้งหมดในบรรทัดเดียว และขยายแต่ละขั้นตอนให้อยู่ในระดับย่อยลงไปเรื่อยๆ — จนกว่าแต่ละขั้นตอนจะเล็กและเรียบง่ายพอที่จะเขียนโค้ดได้โดยตรง

คำศัพท์ ฝึกฝน
English ไทย
assignment/əˈsaɪnmənt/ การกำหนดค่า
concatenation/kənˌkætəˈneɪʃn/ การต่อเชื่อม
stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ การปรับแต่งทีละขั้น
logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ ประโยคตรรกะ
precedence/ˈpresɪdəns/ ลำดับความสำคัญ
De Morgan's law/də ˈmɔːɡənz lɔː/ กฎของเด摩根
9.2

คำสั่งตรรกะ

คำสั่งตรรกะ คือ เงื่อนไข布尔 ที่ควบคุมการแยกทาง สร้างจากการเปรียบเทียบ (x > 10), ตัวเชื่อม (AND, OR, NOT) และวงเล็บ ใช้เป็นเงื่อนไขของ IF, WHILE หรือ REPEAT...UNTIL:

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

ลำดับความสำคัญ (จากสูงสุดไปต่ำสุด): NOT, แล้ว AND, แล้ว OR. ใช้วงเล็บเมื่อไม่แน่ใจ ข้อผิดพลาดพบบ่อย:

  • a = 1 OR 2 ผิด — ต้องเขียน a = 1 OR a = 2.
  • NOT a > 5 หมายความว่า NOT (a > 5), นั่นคือ a <= 5.
  • NOT (A AND B) เหมือนกับ (NOT A) OR (NOT B) (กฎเดมอร์แกน) — มีประโยชน์ในการลดทอนเงื่อนไขให้สั้นลง

การแปลงประโยคให้เป็นนิพจน์ตรรกะเป็นทักษะที่ข้อสอบทดสอบโดยตรง "บัตรเข้าฟรีสำหรับใครก็ตามที่มีอายุต่ำกว่า 5 หรือมากกว่า 65" กลายเป็น Age < 5 OR Age > 65 "คะแนนมีความถูกต้องหากเป็นจำนวนเต็มจาก 0 ถึง 100" กลายเป็น Mark >= 0 AND Mark <= 100 "ลูปหยุดเมื่อไฟล์สิ้นสุดหรืออ่านบันทึกครบสิบบรรทัด" กลายเป็น UNTIL EOF(File) OR Count = 10 เขียนการเปรียบเทียบแต่ละอย่างให้ครบถ้วน: Age > 65 และ Age < 5 อย่าใช้ Age > 65 OR < 5

A parse tree for "attempts < 3 AND NOT loggedIn": NOT applies to loggedIn first, then AND joins that with attempts < 3
ลำดับความสำคัญ: NOTจับคู่กับloggedInก่อน, แล้วANDรวมทั้งสองฝั่งเข้าด้วยกัน

ตัวอย่างทำแล้ว. เขียนตารางตัวระบุและ伪โค้ดเพื่ออ่านตัวเลข 10 ตัวและแสดงผลใหญ่ที่สุด ตารางตัวระบุ ชื่อบันไดตัวแปรพร้อมชนิดข้อมูลและวัตถุประสงค์: Count : INTEGER (ตัวนับลูป), Num : REAL (ตัวเลขที่เพิ่งอ่าน), Max : REAL (ค่าที่ใหญ่ที่สุดจนถึงตอนนี้).

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

The design decision carrying the marks is initialising Max: it must start lower than any possible input - or, safer still, be set to the first number read. Initialise it to 0 and the algorithm wrongly returns 0 for a list of negative numbers, a bug your trace only exposes if the test data include a negative.

ความรู้เบื้องต้นด้านการเขียนโปรแกรมสำหรับคำถามเกี่ยวกับอัลกอริทึม

ก่อนเขียนหรือติดตามอัลกอริทึม, ใช้-expression และ-method ของฟังก์ชันในตัวบนแผ่น 11.1.1–11.1.2. TO_UPPER และ TO_LOWER ยอมรับสตริงทั้งหมด; UCASE และ LCASE ในคู่มือกระทำต่อตัวเดียวตามลำดับ. Follow the question's insert.

เชื่อมสตริงด้วย &; แปลงตัวเลขด้วย NUM_TO_STR ก่อนเชื่อมมัน. เรียกกระบวนการด้วย CALL Name(arguments); ใช้ฟังก์ชันเป็น-expression. SETDATE(day, month, year) สร้างค่า DATE. ตรวจสอบประเภทก่อนประเมิน: Expression ที่ไม่ถูกต้องคือ ERROR, ไม่ใช่การแปลงที่เดาขึ้นมา

For a flowchart with several totals, initialise each accumulator before the loop. Update them on the correct branches, advance the count, then test termination. Put averages after the loop and use the number of values actually included.

คำศัพท์ ฝึกฝน
English ไทย
initialise/ɪˈnɪʃəlaɪz/ การเริ่มต้นค่า
counter/ˈkaʊntə/ ตัวนับ
structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ ภาษาอังกฤษที่มีโครงสร้าง
9.2

คำนิยามที่ผู้สอบยอมรับ

คำถามนิยามจะถูกตรวจด้วยคำศัพท์ตายตัว จงท่องจำเหล่านี้ให้ถูกต้อง และให้คำตอบเพียงข้อเดียว

พจน์ นิยาม
การลดทอน การรักษารายละเอียดหลักของปัญหาไว้และตัดรายละเอียดที่ไม่จำเป็นออก
การแบ่งย่อย การแตกปัญหาออกเป็นปัญหาย่อยเล็กๆ หลายส่วน โดยแต่ละส่วนสามารถแก้แยกกันได้
อัลกอริทึม วิธีแก้ปัญหาที่แสดงเป็นลำดับขั้นตอนที่กำหนดไว้อย่างชัดเจน
ตารางตัวระบุ ตารางที่ระบุตัวระบุที่ใช้ในอัลกอริทึมพร้อมชนิดข้อมูลและคำอธิบายวัตถุประสงค์
伪โค้ด วิธีการเขียนขั้นตอนของอัลกอริทึมแบบมีโครงสร้างและไม่ขึ้นอยู่กับภาษา
แผนภาพโฟว์ แผนภาพที่แสดงขั้นตอนและการตัดสินใจของอัลกอริทึมโดยใช้สัญลักษณ์มาตรฐานเชื่อมด้วยลูกศร
ลำดับ คำสั่งที่ถูกดำเนินการตามลำดับจากบนลงล่างตามลำดับที่เขียน
การเลือก การเลือกที่จะดำเนินการตามเงื่อนไข
การวนซ้ำ การทำซ้ำกลุ่มคำสั่งจนกว่าเงื่อนไขจะเป็นจริงหรือจนกว่าเงื่อนไขจะหมดสภาพ
การปรับระดับทีละขั้น การแตกแต่ละขั้นตอนของโครงร่างออกเป็นขั้นตอนย่อยๆ ซ้ำๆ จนกว่าแต่ละขั้นตอนจะสามารถเขียนโค้ดได้โดยตรง
คำสั่งตรรกะ เงื่อนไขที่สร้างจากการเปรียบเทียบและตัวดำเนินการ AND, OR และ NOT ที่ประเมินค่าได้เป็น TRUE หรือ FALSE
9.2

ข้อแนะนำสำหรับการสอบ

  • นิยาม อัลกอริทึม ว่าเป็นลำดับขั้นตอนที่ชัดเจน มีจำนวนจำกัด เป็นระบบ และไม่ขึ้นอยู่กับภาษา
  • ใช้โครงสร้างสามอย่างให้ถูกต้อง — ลำดับ, การเลือก, การวนซ้ำ — และรักษาตารางตัวระบุพร้อมชนิดข้อมูล
  • แตกปัญหาด้วยการ ลดทอนและการแบ่งย่อย จากนั้นจึงปรับระดับทีละขั้น
  • เขียน伪โค้ดที่รันได้จริง: ประกาศตัวแปรและปฏิบัติตามรูปแบบ伪โค้ดของข้อสอบ

ข้อผิดพลาดที่พบบ่อย

  • การใช้ = ในการกำหนดค่า การกำหนดค่าคือ ←; = คือการเปรียบเทียบ
  • ลืม ENDIF, ENDWHILE, ENDCASE หรือ NEXT. ทุกโครงสร้างต้องปิด, และคำปิดคือจุดที่ตรวจสอบคะแนนของโครงสร้างนั้น
  • ไม่ได้เริ่มต้นค่ารวมหรือตัวนับก่อนลูป, ทำให้อัลกอริทึมบวกเข้าไปยังค่าที่ไม่มีอยู่จริง
  • ใช้ FOR ลูปเมื่อจำนวนรอบไม่ทราบ การอ่านจนกว่าจะเจอค่า sentinel หรือทายถูกต้องการ WHILE หรือ REPEAT ... UNTIL
  • เขียน Age > 65 OR < 5. แต่ละฝั่งของ OR และ AND ต้องเป็นการเปรียบเทียบที่สมบูรณ์
  • ตอบ "อธิบายว่าทำไมต้องใช้การแบ่งย่อย" ด้วยประโยชน์หนึ่งเขียนสามวิธี. คะแนนสามข้อต้องการประโยชน์ที่แตกต่างกันสามอย่าง

บทเรียนเชิงโต้ตอบสำหรับหัวข้อนี้

ทำทีละขั้นตอน พร้อมแบบฝึกหัดตรวจสอบผลทันที

ข้อสอบย้อนหลัง

หัวข้อเพิ่มเติมใน Computer Science A-Level

เข้าสู่ระบบหรือสร้างบัญชี

IGCSE, A-Level & AP