อัลกอริทึมและ伪代码 (Pseudocode)

รอยขีดข่วนที่แพงที่สุดในประวัติศาสตร์

• ในวันที่ 22 กรกฎาคม ค.ศ. 1962 จรวด Mariner 1 ที่มุ่งหน้าไปดาวศุกร์ ถูก引爆หลังจากบินได้ 293 วินาที
• สาเหตุมาจากการขาดเส้นขีดทับเหนือสัญลักษณ์หนึ่งในสมการนำทาง คอมพิวเตอร์ปฏิบัติตามขั้นตอนที่เขียนไว้อย่างเคร่งครัด และขั้นตอนที่เขียนไว้นั้นผิด
• คอมพิวเตอร์ไม่เคยเติมสิ่งที่คุณตั้งใจไว้ ทุกขั้นตอนที่คุณให้มันต้องมีความหมายเพียงอย่างเดียวเท่านั้น
• นั่นคือเหตุผลที่บทเรียนนี้เกี่ยวกับการเขียนขั้นตอนที่เครื่องสามารถทำตามได้: อัลกอริทึม (Algorithms)

อัลกอริทึมคืออะไร

• อัลกอริทึม คือวิธีแก้ปัญหาที่แสดงออกมาเป็น ลำดับขั้นตอนที่กำหนดไว้ชัดเจน
• แต่ละขั้นตอนต้อง ไม่ambiguous (มีความหมายเดียว) determinis tic (อินพุตเท่าเดิม → เอาต์พุตเท่าเดิม)有限 (ขั้นตอนสิ้นสุดลง) และEffective (แต่ละขั้นตอนสามารถทำได้จริง)
• มันบอก ต้องทำอะไร โดยไม่ขึ้นอยู่กับภาษาโปรแกรมใด และทุกตัว遵循 Input → Process → Output

อัลกอริทึมทุกตัวมีรูปทรงเดียวกัน: Input, Process, Output

ตัวอย่างทำโจทย์: ตารางตัวแปร

ตารางตัวแปรระบุชื่อข้อมูลทุกชิ้นก่อนเริ่มเขียนโค้ด

โครงสร้างสามชนิด

IF … THEN … ELSE … ENDIF

• การกำหนดค่า (Assignment) เก็บค่าด้วยลูกศร, Total ← Total + Value; = ใช้สำหรับการเปรียบเทียบ. DIV เป็นการหารจำนวนเต็ม และ MOD เป็นเศษเหลือ ดังนั้น 17 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

บล็อกสร้างอัลกอริทึมทั้งสาม

เลือกวงลูปแบบไหน?

• FOR … NEXT เมื่อคุณทราบจำนวนครั้ง: Count-controlled loop
• WHILE … ENDWHILE ตรวจสอบเงื่อนไข ก่อน การวนแต่ละรอบ ดังนั้น Body อาจรัน ศูนย์ ครั้ง: Pre-condition loop
• REPEAT … UNTIL ตรวจสอบ หลัง การวนแต่ละรอบ ดังนั้น Body จะรันอย่างน้อย หนึ่ง ครั้งเสมอ: Post-condition loop. การตรวจสอบ Input เป็นกรณีคลาสสิก
• คำตอบแบบ "อธิบายโครงสร้างการทำซ้ำ" ต้องระบุชื่อนวงลูป บอก จุดที่ตรวจสอบเงื่อนไข และบอกผลลัพธ์

ลูป WHILE จะทดสอบก่อนรันตัวลูป; ลูป REPEAT … UNTIL จะทดสอบหลังจากรันตัวลูป

ตัวอย่างทำโจทย์: จากข้อความสู่ Pseudocode

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

ระบุโครงสร้างจากส่วนคัดลอก

• คำถามยอดนิยมแสดงตัวอย่าง Pseudocode ห้าส่วนและขอให้ติ๊กว่าแต่ละส่วนใช้ การกำหนดค่า, การเลือก, หรือการทำซ้ำ อย่างใด
• Result ← CalculateTotal() เป็นการกำหนดค่า. WHILE IsClosed เป็นการทำซ้ำ. REPEAT … INPUT Value … UNTIL Sales[4] > Value เป็นการทำซ้ำ และ การกำหนดค่า (INPUT เก็บค่า) IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF
• ดูทุกบรรทัดของส่วนคัดลอก ไม่ใช่แค่บรรทัดแรก บรรทัดหนึ่งอาจต้องการติ๊กสองจุด

Flowchart

• แผนผังการทำงาน (flowchart) แสดงอัลกอริทึมเดียวกันในรูปภาพ วงรีคือ START และ END,สี่เหลี่ยมผืนผ้าคือกระบวนการ, สี่เหลี่ยมขนมเปียกปูนคือ INPUT/OUTPUT,และ รูปเพชร คือการตัดสินใจ
• รูปเพชรคือจุดที่มีการเลือก,และเส้นนำทางที่วิ่งกลับ ขึ้น บนแผนผังคือลูป
• การสอบถามทั้งสองแบบ: พ MESSAGECODE จาก แผนผังการทำงาน,และแผนผังการทำงาน จาก พ MESSAGECODE หรือภาษาอังกฤษแบบโครงสร้าง ทุกสัญลักษณ์ที่คุณวาดควรจับคู่กับหนึ่งบรรทัดของพ MESSAGECODE

แต่ละสัญลักษณ์ในแผนผังการทำงานจับคู่กับชนิดหนึ่งของคำสั่งพ MESSAGECODE

ตัวอย่างทำพร้อมวิธี: เกมทายตัวเลข

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"

เกมทายตัวเลขในรูปแบบแผนผังการทำงาน: ลูปจะย้อนกลับไปที่การรับค่าจนกว่าการทายจะตรงกับคำตอบ

การปรับปรุงทีละขั้น (Stepwise refinement)

• การปรับปรุงทีละขั้น หมายถึงเริ่มจากโครงร่างและขยายแต่ละขั้นตอนให้เป็นขั้นตอนรายละเอียดมากขึ้น ซ้ำแล้วซ้ำเล่า จนกว่าทุกขั้นตอนสามารถเขียนเป็นพ MESSAGECODE ได้โดยตรง
• "ประมวลผลคำสั่งซื้อ" → "รับรายการ", "คำนวณยอดรวม", "รับชำระเงิน" → "คำนวณยอดรวม" กลายเป็น "สำหรับแต่ละรายการ, บวกราคา × จำนวน; ใช้ส่วนลดหากมี"
• แต่ละระดับเป็นการปรับปรุงของระดับด้านบน,และระดับที่สมบูรณ์รวมกันคือแบบแผน "อธิบายการปรับปรุงทีละขั้น" ต้องการโครงร่าง,การขยาย,และกฎการหยุด

*ปรับปรุงแต่ละขั้นตอนจนสามารถเขียนโค้ดได้โดยตรง

คำสั่งตรรกะ

• ส่วนหนึ่งของโซลูชันถูกกำหนดโดย คำสั่งตรรกะ: เงื่อนไขที่สร้างจากการเปรียบเทียบ (=, <>, <, >, <=, >=) ที่เชื่อมต่อกันด้วย AND, OR และ NOT
• คะแนนที่ถูกต้อง: Mark >= 0 AND Mark <= 100. ส่วนลดใช้ได้หากลูกค้าเป็นสมาชิก หรือใช้จ่ายเกิน 50: IsMember OR Total > 50
• NOT (Mark < 40) มีความหมายเหมือน Mark >= 40. เขียนคำสั่ง แล้วทดสอบด้วยค่าแต่ละด้านของขอบเขต

*การเปรียบเทียบที่เชื่อมต่อกันด้วย AND, OR และ NOT สร้างเงื่อนไขที่อัลกอริทึมต้องการ

คะแนนที่หลุดหายไป

คุณเข้าใจแล้ว