อะไรจะเป็นคำอธิบายสำหรับการสังเกตนี้?
อัลกอริทึมอาจทำงานได้สำหรับตัวอย่างหนึ่งแต่ล้มเหลวที่ขอบเขต การทดสอบควรออกแบบจากสเปก ไม่ใช่แค่ทางเดินที่เป็นสุข (happy path) เท่านั้น
เริ่มต้นด้วยการทำนาย ระบุปริมาณหรือลักษณะที่คุณจะเปรียบเทียบ แล้วตัดสินใจว่าหลักฐานอะไรที่จะแยกแยะคำอธิบายสองแบบได้
สร้างโมเดล
อัลกอริทึมคือขั้นตอนที่จำกัดและชัดเจนสำหรับงานหนึ่งๆ การติดตาม (trace) บันทึกการเปลี่ยนแปลงสถานะ ความคงสภาพของลูป (loop invariant) อธิบายคุณสมบัติที่ถูกรักษาไว้ในการวนซ้ำแต่ละรอบและช่วยในการพิสูจน์ความถูกต้อง
algorithm: กระบวนการจำกัดจำนวนขั้นตอนในการแก้ปัญหาที่กำหนด; boundary test : การทดสอบที่ขอบเขตของช่วงค่าเข้าที่ยอมรับได้
เลือกหลักฐานที่นำมาทดสอบได้
กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์
ติดตามการค้นหาในรายการเรียงลำดับสมมติขนาดเล็ก ระบุ().'มาตรฐานการอ้างอิงดัชนี' สำหรับการค้นหาแบบเบี่ยง二分 (binary search) อัปเดตขอบเขตเพื่อให้ช่วงที่เหลือเล็กลง Reject อินพุตที่ไม่เรียงลำดับเว้นแต่การจัดเรียงจะเป็นส่วนหนึ่งของงาน
เริ่มจากปริมาณที่ทราบแล้ว
ระบุค่าที่ทราบและหน่วยของมัน เลือกความสัมพันธ์โดยพิจารณาว่าข้อสมมติฐานสอดคล้องกับเคสนี้ แล้วจัดรูปสมการก่อนแทนค่า
ที่ทราบ: การค้นหาเชิงเส้นของรายการ 8 รายการ อาจต้องการ 8 ครั้งเปรียบเทียบเมื่อ itemCount ที่หาอยู่เป็นรายการสุดท้ายหรือไม่มีอยู่ การเพิ่มขนาดรายการสองเท่าจะเพิ่มจำนวนครั้งเปรียบเทียบในกรณี worst-case สองเท่าภายใต้โมเดลนี้ การค้นหาแบบเบี่ยง二分 ลดช่วงลงประมาณครึ่งหนึ่งในแต่ละขั้นตอนแต่ต้องใช้โครงสร้างที่จัดลำดับเหมาะสม
ตัวอย่าง:
การค้นหาเชิงเส้นสแกน 14 รายการทั้งหมดโดยไม่พบ-match เกิดการเปรียบเทียบ itemCount กี่ครั้ง? ใช้ลำดับเดียวกัน: ปริมาณที่ทราบ → โมเดล → ความสัมพันธ์ → แทนค่า → หน่วยและการตีความ
ตรวจสอบข้อสรุปและขอบเขต
การทดสอบตัวอย่างสำเร็จไม่ได้พิสูจน์ความถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด อย่านำไวยากรณ์伪 โค้ดเฉพาะ Cambridge มาใช้ในหลักสูตร IB โดยไม่มีแหล่งที่มาของหลักสูตร
กลับไปที่การสังเกตเดิม อธิบายว่าผลลัพธ์นี้สนับสนุนสิ่งใด มีเงื่อนไขใดบ้าง และเป็นอย่างไรในการทดสอบคำอธิบายอื่นที่ขัดแย้งกัน
เตือน:
การทดสอบตัวอย่างสำเร็จหนึ่งครั้งพิสูจน์อัลกอริทึมว่าถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด ข้อความนี้ไม่จริง: การทดสอบตัวอย่างสำเร็จไม่ได้พิสูจน์ความถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด อย่านำไวยากรณ์伪 โค้ดเฉพาะ Cambridge มาใช้ในหลักสูตร IB โดยไม่มีแหล่งที่มาของหลักสูตร
จุดสำคัญ:
อัลกอริทึม การติดตาม และหลักฐานความถูกต้อง: กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์
ลายเส้นที่ดำเนินการได้และขอบเขต
def first_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(first_index([4, 7, 4], 4))
print(first_index([4, 7, 4], 9))
print(first_index([], 4))
ผลลัพธ์ที่คาดหวัง:
0
-1
-1
ลูปจะทดสอบค่าดัชนี 0 ก่อน จะหยุดเมื่อพบการจับคู่ และจะคืนค่า −1 ก็ต่อเมื่อตรวจสอบรายการจนหมด ดังนั้นหากมีข้อมูลซ้ำกันจะได้ค่าดัชนีตัวแรก หากเป็นรายการว่างจะไม่มีการทำงานภายในลูป
