Harvard CS50: การบ้านสัปดาห์ที่ 3 (การบรรยายที่ 7 และ 8) ตอนที่ 1

การบรรยายจากหลักสูตร Harvard เกี่ยวกับพื้นฐานของการเขียนโปรแกรม CS50 เนื้อหาเพิ่มเติม: สัญลักษณ์กำกับ การเรียงลำดับและการค้นหาอัลกอริธึม ส่วนที่สอง "แท็ก" ใน C

การตระเตรียม

ก่อนที่จะจัดการกับปัญหา ดูการบรรยายที่ 7-8อ่านและเจาะลึก " เนื้อหาเพิ่มเติมของสัปดาห์ที่สาม " พวกเขาทุ่มเทให้กับอัลกอริธึมการค้นหา (เชิงเส้นและไบนารี) การเรียงลำดับ (มีอยู่มากมาย!) รวมถึงงานของดีบักเกอร์ (ความสามารถในการทำงานร่วมกับดีบักเกอร์เพื่อดีบักโปรแกรมเป็นทักษะที่สำคัญอย่างยิ่ง!) หากทุกอย่างเป็นไปตามที่ควรในการบรรยายและทฤษฎี คุณสามารถตอบคำถามทดสอบได้อย่างง่ายดาย:

• เหตุใดการค้นหาแบบไบนารีจึงต้องมีอาร์เรย์ที่เรียงลำดับ
• เหตุใดการเรียงลำดับแบบฟองจึงประมาณว่าเป็น O(n2)
• เหตุใดการเรียงลำดับการแทรกจึงประมาณค่า Ω(n)
• การเรียงลำดับการเลือกทำงานอย่างไร อธิบายเป็นสามประโยค (หรือน้อยกว่า)
• ขีดจำกัดสูงสุด (กรณีที่แย่ที่สุด) คืออะไรในการเรียงลำดับแบบผสานที่สามารถทำงานได้
• ดีบักเกอร์ GDB ช่วยให้คุณสามารถดีบักโปรแกรมได้ และถ้าคุณกำหนดเจาะจงมากขึ้น มันช่วยให้คุณทำอะไรได้บ้าง?

เป้าหมาย

• เรียนรู้การทำงานกับโปรเจ็กต์ที่มีหลายไฟล์
• เรียนรู้การอ่านซอร์สโค้ดของผู้อื่น
• ทำความเข้าใจอัลกอริธึมและฟังก์ชันแบบเรียกซ้ำต่างๆ

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

เริ่ม

โปรดจำไว้ว่าสำหรับการฝึกแก้ปัญหาในสัปดาห์ที่หนึ่งและ สอง คุณได้เขียนโปรแกรมตั้งแต่เริ่มต้นและสร้างไดเร็กทอรี pset1และpset2 ของคุณเองโดยใช้ คำสั่ง mkdir สำหรับการมอบหมายแบบฝึกหัดสัปดาห์ที่สาม คุณต้องดาวน์โหลดการแจกจ่าย (หรือ "distro" ตามที่เราเรียกกัน) ที่เราเขียนและเพิ่มบรรทัดโค้ดของคุณเองลงไป ขั้นแรก อ่านโค้ดของเราแล้วพยายามทำความเข้าใจ ทักษะที่สำคัญที่สุดในสัปดาห์นี้คือการเรียนรู้วิธีอ่านโค้ดของผู้อื่น ดังนั้น ให้เข้าสู่ระบบ cs50.io และรันคำสั่ง update50 ในหน้าต่างเทอร์มินัลเพื่อให้แน่ใจว่าเวอร์ชันพื้นที่ทำงานเป็นเวอร์ชันล่าสุด หากคุณปิดหน้าต่างเทอร์มินัลโดยไม่ได้ตั้งใจและหาไม่พบ ให้ไปที่ เมนู มุมมองและตรวจสอบให้แน่ใจว่าได้เลือกตัวเลือกคอนโซลแล้ว (ตรวจสอบว่าไม่ใช่หรือไม่) คลิกที่ (+) ภายในวงกลมสีเขียวบนกรอบหน้าต่างเทอร์มินัล เลือกNew Terminal หลังจากนั้นให้รันคำสั่ง cd ~/workspace และตรวจสอบให้แน่ใจว่าคุณอยู่ในไดเร็กทอรีพื้นที่ทำงาน (นี่คือไดเร็กทอรีของคุณ) หลังจากนั้นให้รันคำสั่ง: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip เพื่อดาวน์โหลดไฟล์ ZIP ของหนังสือปัญหาลงในพื้นที่ทำงานของคุณ (wget คือคำสั่งดาวน์โหลด Linux) หากทุกอย่างเรียบร้อยดี คุณจะเห็นวลีต่อไปนี้ในบรรทัด: 'pset3.zip' saved ตรวจสอบให้แน่ใจว่าคุณดาวน์โหลดpset3.zip จริงๆ โดยรันคำสั่ง: ls จากนั้นรัน unzip pset3.zip เพื่อแตกไฟล์ หากคุณรัน คำสั่งls อีกครั้ง คุณจะเห็น ไดเร็กทอรี pset3ด้วย ไปที่มันโดยรันคำสั่ง cd pset3 แล้วขอดูเนื้อหาของไดเร็กทอรีอีกครั้ง: ls คุณจะเห็นว่ามีไดเร็กทอรีย่อยสองไดเร็กทอรีในไดเร็กทอรีนี้: fifteen find น่าสนใจอยู่แล้ว!

ค้นหา

ตอนนี้เรามาดูหนึ่งในไดเร็กทอรีย่อยเหล่านี้กัน ในการดำเนินการนี้ให้รันคำสั่ง: cd ~/workspace/pset3/find หากคุณแสดงเนื้อหาของโฟลเดอร์นี้บนหน้าจอ (คุณคงจำวิธีการทำเช่นนี้ได้แล้ว) นี่คือสิ่งที่คุณควรเห็น: helpers.c helpers.h Makefile find.c generate.c ว้าว มีไฟล์จำนวนมาก แต่ไม่ต้องกังวล เราจะจัดการกับพวกเขาตอนนี้ ไฟล์Generate.cมีโค้ดสำหรับโปรแกรมที่ใช้ "ตัวสร้างตัวเลขสุ่มหลอก" (สร้างโดย ฟังก์ชัน drand48 ) เพื่อสร้างตัวเลขสุ่มจำนวนมาก (จริงๆ แล้วเป็นการสุ่มหลอก คอมพิวเตอร์ไม่สามารถจัดการตัวเลขสุ่มล้วนๆ ได้!) และวางไว้ทีละรายการในบรรทัด คอมไพล์โปรแกรม: make generate ตอนนี้ให้รันมันโดยการรันคำสั่ง: ./generate โปรแกรมจะให้ข้อความต่อไปนี้แก่คุณ: Usage: generate n [s] ซึ่งหมายความว่าโปรแกรมคาดหวังอาร์กิวเมนต์บรรทัดคำสั่งหนึ่งหรือสองอาร์กิวเมนต์ ใช้อันแรก n เป็นค่าบังคับ โดยตัวเลขนี้หมายถึงจำนวนตัวเลขสุ่มเทียมที่คุณต้องการสร้าง พารามิเตอร์ s เป็นทางเลือก ตามที่ระบุในวงเล็บเหลี่ยม ตัวเลข s สามารถเรียกว่า "seed" สำหรับตัวสร้างตัวเลขสุ่มเทียม โดย "seed" เราหมายถึงข้อมูลอินพุตไปยังตัวสร้างตัวเลขสุ่มเทียมที่ส่งผลต่อเอาต์พุต ตัวอย่างเช่น หากคุณใช้ drand48 อันดับแรก โดยการเรียก srand48 (ฟังก์ชันอื่นที่มีจุดประสงค์เพื่อ "seed" drand48) พร้อมอาร์กิวเมนต์ของ พูด 1 และ จากนั้นเรียก drand48 สามครั้ง drand48 อาจส่งคืน 2728 จากนั้น 29785 จากนั้น 54710 หากคุณแทนที่จะเป็นอันก่อนหน้าโดยใช้ drand48 ให้โทร srand48 ก่อนพร้อมอาร์กิวเมนต์พูด 2 แล้วใช้ drand48 อีกครั้งสามครั้ง drand48 อาจ กลับ 59797 จากนั้น 10425 จากนั้น 37569 แต่ถ้าคุณดู drand48 อีกครั้งโดยการโทร srand48 อีกครั้งโดยมีอาร์กิวเมนต์เป็น 1 ผลลัพธ์ของการเรียก drand48 สามครั้งถัดไป คุณจะได้รับ 2728 อีกครั้ง จากนั้น 29785 จากนั้น 54710! คุณจะเห็นทุกอย่างเกิดขึ้นด้วยเหตุผล รันโปรแกรมอีกครั้ง คราวนี้พูด n=10 ดังรูปด้านล่าง คุณจะเห็นรายการตัวเลขสุ่มหลอก 10 หมายเลข ./generate 10 เรามารันโปรแกรมครั้งที่สามด้วยค่า n เท่ากัน; คุณจะเห็นรายการหมายเลข 10 อีกรายการ ตอนนี้ลองรันโปรแกรมด้วยพารามิเตอร์สองตัว ลองใช้ s=0 ดังที่แสดงด้านล่าง ./generate 10 0 ตอนนี้รันคำสั่งเดียวกันอีกครั้ง: ./generate 10 0 คุณไม่สามารถโต้แย้งได้: คุณเห็นลำดับ "สุ่ม" เดิมที่มีตัวเลขสิบหลักอีกครั้ง นี่คือสิ่งที่จะเกิดขึ้นถ้าคุณไม่เปลี่ยนเมล็ดกำเนิดตัวเลขสุ่มเทียม ทีนี้มาดู ตัวโปรแกรม Generate.c กันดีกว่า(จำได้อย่างไร?) ความคิดเห็นที่ตอนต้นของไฟล์นี้จะอธิบายการทำงานทั่วไปของโปรแกรม แต่ดูเหมือนว่าเราจะลืมแสดงความคิดเห็นเกี่ยวกับโค้ดนั้น อ่านโค้ดอย่างละเอียดและอ่านจนกว่าคุณจะเข้าใจความหมายของแต่ละบรรทัด จากนั้นแสดงความคิดเห็นโค้ดนี้ให้เรา โดยแทนที่ TODO แต่ละรายการด้วยวลีที่อธิบายวัตถุประสงค์หรือการทำงานของบรรทัดหรือบรรทัดของโค้ดที่เกี่ยวข้อง (หมายเหตุ: int ที่ไม่ได้ลงนามคือ int "ที่ไม่ได้ลงนาม" ซึ่งหมายความว่าไม่สามารถเป็นค่าลบได้) หากต้องการข้อมูลเพิ่มเติมเกี่ยวกับ rand หรือ srand ให้รัน: man drand48 หรือ man srand48 หลังจากที่คุณได้แสดงความคิดเห็นให้มากที่สุดเท่าที่จะเป็นไปได้ใน Generate.c แล้ว ให้คอมไพล์โปรแกรมใหม่เพื่อให้แน่ใจว่าคุณไม่ได้เสียหายอะไร: make generate หากสร้างไม่คอมไพล์อีกต่อไป ให้แก้ไขสิ่งที่คุณ แตกหัก: )! โปรดทราบว่า คำสั่ง makeทำการคอมไพล์โค้ดโดยอัตโนมัติ ดังนั้นคุณจึงไม่จำเป็นต้องรันคำสั่ง clang โดยการแทรกสวิตช์จำนวนมากด้วยตนเอง แต่ในความเป็นจริงแล้ว make เพียงแค่ทำให้อินพุตของเราง่ายขึ้น แต่ในความเป็นจริงแล้ว เสียงกราวเดียวกันกับพารามิเตอร์ที่เราต้องการนั้นถูกซ่อนอยู่ด้านหลัง อย่างไรก็ตาม เมื่อโปรแกรมของคุณมีขนาดใหญ่ขึ้น make ไม่สามารถเข้าใจวิธีการคอมไพล์โค้ดจากบริบทได้อีกต่อไป ในกรณีนี้ คุณจะต้องบอกวิธีการคอมไพล์โปรแกรม โดยเฉพาะอย่างยิ่งหากเกี่ยวข้องกับการใช้ไฟล์ต้นฉบับที่แตกต่างกัน (เช่น .c) เพื่อแก้ไขปัญหานี้ เราจะใช้ไฟล์คอนฟิกูเรชัน (Makefiles) ที่บอกให้ชัดเจนว่าต้องทำอย่างไร คำสั่ง make รู้ได้อย่างไรว่าเราควรคอมไพล์สร้างอย่างไร? จริงๆ แล้วทีมงานใช้ไฟล์คอนฟิกูเรชันที่เราเขียนไว้แล้ว ไฟล์นี้เรียกว่าMakefileและอยู่ในไดเร็กทอรีเดียวกันกับGenerate.c Makefile คือรายการกฎที่ระบุวิธีสร้างไฟล์ที่สร้างจาก Generate.c ในไฟล์คุณจะพบบรรทัดที่เกี่ยวข้องโดยเฉพาะ: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c บรรทัดแรกบอกว่า make ว่า "เป้าหมาย" ที่เรียกว่าสร้างควรถูกสร้างขึ้นโดยการเรียกคำสั่งจากบรรทัดที่สอง ยิ่งไปกว่านั้น บรรทัดแรกบอกว่า make นั้น Generic ขึ้นอยู่กับ Generate.c ซึ่งหมายความว่า Make จะสร้าง Gene ขึ้นมาใหม่เฉพาะในการรันครั้งต่อๆ ไปหากไฟล์นั้นมีการเปลี่ยนแปลง ไม่ใช่เคล็ดลับการประหยัดเวลาที่แย่ใช่ไหม? ที่จริงแล้ว ให้รันคำ สั่ง ด้านล่างอีกครั้งหากคุณไม่ได้เปลี่ยนGenerate.c make generate คุณจะได้รับแจ้งว่าการ build ได้รับการอัพเดตเป็นเวอร์ชันปัจจุบันแล้ว หมายเหตุ : การเยื้องที่จุดเริ่มต้นของบรรทัดที่สองไม่ใช่ลำดับของการเว้นวรรค แต่เป็นอักขระแท็บ น่าเสียดายที่คำสั่ง make ต้องมีแท็บนำหน้า ดังนั้นระวังอย่าเปลี่ยนเป็นช่องว่าง ไม่เช่นนั้นคุณจะพบข้อผิดพลาดแปลกๆ! ธง-Werrorบอก คำสั่ง เสียงดังกราวถือว่าคำเตือน (แย่) เป็นข้อผิดพลาด (แย่กว่านั้น) ดังนั้นคุณจะถูกบังคับ (ในทางที่ดีและเป็นการศึกษา!) ให้แก้ไขให้ถูกต้อง ตอนนี้เรามาดู ไฟล์ find.cกัน โปรดทราบว่าโปรแกรมนี้คาดหวังอาร์กิวเมนต์บรรทัดคำสั่งหนึ่งรายการ: "igloo" ซึ่งจะต้องพบใน "กองหญ้า" ของค่าต่างๆ หลังจากนั้นให้ตรวจสอบโค้ดและคอมไพล์โปรแกรมโดยใช้คำสั่งด้านล่าง make find โดยพื้นฐานแล้วให้เราดังต่อไปนี้: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm ให้ความสนใจ! คุณเพิ่งรวบรวมแอปพลิเคชันที่ประกอบด้วย ไฟล์เดียว แต่มีสองไฟล์: helpers.cและfind.c ทราบเรื่องนี้ได้อย่างไร? เพื่อให้เข้าใจสิ่งนี้ ให้เปิด Makefile อีกครั้งเพื่อดูว่าเกิดอะไรขึ้นจริงๆ บรรทัดที่เกี่ยวข้องอยู่ด้านล่าง find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm สิ่งที่เราหมายถึงโดยการพึ่งพา (หลังเครื่องหมายทวิภาค) คือการเปลี่ยนแปลงใด ๆ ในfind.c , helpers.cหรือhelpers.hจะบังคับให้ make สร้างใหม่ find ในครั้งถัดไปที่ถูกเรียกเพื่อวัตถุประสงค์เหล่านั้น ตอนนี้ให้รันโปรแกรมนี้โดยทำดังต่อไปนี้: ./find 13 หลังจากนี้ คุณจะถูกขอให้จัดเตรียมสแต็กจำนวนหนึ่ง (นั่นคือจำนวนเต็ม) และป้อนฟางทีละอัน เมื่อคุณเบื่อกับการพิมพ์ตัวเลขแล้ว ให้กดคีย์ผสมCtrl -D การรวมกันนี้จะส่งอักขระจุดสิ้นสุดไฟล์ (EOF) ให้โปรแกรม สัญลักษณ์จะบังคับให้ ฟังก์ชันGetIntจากไลบรารี CS50 ส่งคืนค่าคงที่INT_MAXและในทางกลับกันfind.cจะบังคับให้ find หยุดพิมพ์ "stack" ตอนนี้โปรแกรมจะค้นหาเข็มในกองหญ้าที่คุณให้ไว้ และในที่สุดมันจะบอกคุณว่าพบเข็มนั้นหรือไม่ กล่าวโดยสรุปคือ โปรแกรมจะค้นหาค่าบางค่าในอาเรย์ อย่างน้อยเธอก็ควร แต่สิ่งที่จับได้ก็คือเธอจะไม่พบอะไรเลย! แต่ที่นี่คุณมาเพื่อช่วยเหลือ! เราจะพูดถึงความสำคัญของบทบาทของคุณในภายหลัง ในความเป็นจริง กระบวนการจัดเตรียมกองหญ้าสามารถทำให้เป็นอัตโนมัติได้ อย่างน้อยก็โดยการ "รวม" ผลลัพธ์ของการสร้างให้เป็น find เป็นอินพุต ตัวอย่างเช่น คำสั่งด้านล่างส่งผ่านตัวเลขสุ่มเทียม 1,000 ตัวเพื่อค้นหา ซึ่งจะค้นหาค่าเหล่านั้นเป็น 42 ./generate 1000 | ./find 42 โปรดทราบว่าเมื่อสร้างส่งข้อมูลดิบเพื่อค้นหา คุณจะไม่เห็นหมายเลขสร้าง แต่คุณจะเห็นว่าการค้นหากำลังทำงานอยู่ . หรือคุณสามารถ "เปลี่ยนเส้นทาง" ผลลัพธ์ของการสร้างไปยังไฟล์ด้วยคำสั่งดังนี้: ./generate 1000 > numbers.txt เนื้อหาของไฟล์นี้สามารถเปลี่ยนเส้นทางไปยังอินพุตของการค้นหาด้วยคำสั่ง: ./find 42 < numbers.txt ลองมาดูโค้ดใน Makefile อีกครั้งแล้วสังเกต บรรทัดต่อไปนี้: all: find generate ซึ่งหมายความว่าคุณสามารถสร้างสร้างและค้นหาได้โดยการรันคำสั่งต่อไปนี้: make all ยิ่งไปกว่านั้น คำสั่งด้านล่างบรรทัดนี้เทียบเท่ากับคำสั่งด้านบน เนื่องจาก make สร้างรายการแรกใน Makefile ตามค่าเริ่มต้น make ถ้าเพียงคุณเท่านั้นที่สามารถสรุปงานฝึกหัดทั้งหมดนี้ให้เป็นคำสั่งเดียวได้! แต่ - อนิจจา! สุดท้ายนี้ ให้ใส่ใจกับบรรทัดสุดท้ายเหล่านี้ใน Makefile: clean: rm -f *.o a.out core find generate รายการนี้ช่วยให้คุณสามารถลบไฟล์ทั้งหมดที่ลงท้ายด้วย .o หรือที่เรียกว่า core (เราจะอธิบายสิ่งนี้ในอีกสักครู่!) และยังเรียกใช้การค้นหาหรือสร้างโปรแกรมได้ง่ายๆ โดยดำเนินการบรรทัด: หากคุณต้องการ make clean ทดลอง ต่อไปนี้เป็นสิ่งที่ต้องระวัง: อย่าเพิ่ม พูด*.cในบรรทัดสุดท้ายของ Makefile! (ทำไม?) ทุกบรรทัดที่ขึ้นต้นด้วยเครื่องหมาย # เป็นเพียงความคิดเห็น

ภารกิจที่ 1: ค้นหา

ถึงเวลาสำหรับสิ่งที่น่าสนใจแล้ว! โปรดทราบว่าfind.cเรียกsearchซึ่งเป็นฟังก์ชันที่ประกาศในhelpers.h น่าเสียดายที่เราลืมใช้ฟังก์ชันนี้อย่างสมบูรณ์ในhelpers.c ! (ควรสังเกตว่าเราสามารถรวมเนื้อหาของhelpers.hและhelpers.c ไว้ใน find.cเดียวแต่บางครั้งก็เป็นการดีกว่าที่จะแยกโปรแกรมออกเป็นหลายไฟล์ โดยเฉพาะอย่างยิ่งหากฟังก์ชันบางอย่างหรือฟังก์ชันยูทิลิตี้ค่อนข้างจะมีประโยชน์ สำหรับโปรแกรมอื่นๆ เช่น ฟังก์ชั่นไลบรารี CS50 เป็นต้น ลองดูที่helpers.cแล้วคุณจะเห็นว่าการค้นหาจะส่งกลับค่าเท็จเสมอไม่ว่าค่าที่กำหนดจะเป็นค่าหรือไม่ก็ตาม เขียนการค้นหาใหม่เพื่อใช้การค้นหาเชิงเส้นโดยส่งคืนค่าจริง , ถ้าค่าอยู่ในค่าและเป็นเท็จถ้าค่าไม่อยู่ในค่า ดูแลให้คืนค่า false ทันทีถ้า n ไม่เป็นค่าบวก เมื่อคุณพร้อมที่จะตรวจสอบความถูกต้องแล้วให้ลองเรียกคำสั่งต่อไปนี้: เนื่องจากหนึ่งในตัวเลขที่พิมพ์ออก ./generate 1000 50 | ./find 127 มา ด้วยการสร้างเมื่อ 50 ถูก seed คือ 127 โค้ดของคุณควรหาเข็ม ในทางกลับกัน ลองใช้คำสั่งนี้: ./generate 1000 50 | ./find 128 เนื่องจาก 128 ไม่ได้อยู่ในชุดตัวเลขที่สร้างขึ้นโดยสร้างเมื่อ 50 ถูก seed โค้ดของคุณจึงไม่จำเป็นต้องค้นหา "needle" . รันการทดสอบอื่นๆ โดยการรัน Generate ด้วย Seed วิเคราะห์ผลลัพธ์ และมองหาเข็มที่ควรอยู่ในกองหญ้า โปรดทราบว่า main ใน find.c ถูกเขียนในลักษณะที่ find ส่งคืน 0 หากพบ "needle" มิฉะนั้นจะส่งคืน 1 คุณสามารถตรวจสอบสิ่งที่เรียกว่า "โค้ดเอาต์พุต" ที่ main ส่งคืนเมื่อดำเนินการหลังจากรันโค้ดอื่น ๆ คำ echo $? สั่ง ตัวอย่างเช่น หากการดำเนินการค้นหาของคุณถูกต้อง หากคุณเรียกใช้ ./generate 1000 50 | ./find 127 echo $? คุณจะเห็น 0 ในขณะที่ 127 เป็นหนึ่งในผลลัพธ์ 1,000 หมายเลขที่สร้างด้วยค่าเริ่มต้น 50 ดังนั้นการค้นหาที่คุณเขียนควรคืนค่าเป็นจริง ในกรณีนี้ main (เขียนโดยเรา) ควรส่งคืน 0 (นั่นคือ exit) หากคุณป้อนข้อมูลต่อไปนี้ ./generate 1000 50 | ./find 128 echo $? คุณจะเห็น 1 เนื่องจาก 128 ไม่ได้อยู่ในจำนวน 1,000 หมายเลขที่สร้างขึ้นด้วยค่าเมล็ด 50 ในกรณีนี้ การค้นหา (เขียนโดยคุณ) จะส่งกลับค่าเท็จ และค่าหลัก (เขียนโดยเรา) ) จะส่งกลับ 1 ( จากนั้นจึงทำงานให้เสร็จ) คุณเข้าใจตรรกะหรือไม่? เมื่อทุกอย่างพร้อมที่จะตรวจสอบโดยใช้ check50 ให้รันคำสั่งต่อไปนี้: check50 2015.fall.pset3.find helpers.c อย่างไรก็ตาม คุณไม่ควรคุ้นเคยกับการทดสอบโค้ดของคุณโดยใช้ check50 ก่อนที่จะทดสอบด้วยตัวเอง ท้ายที่สุดแล้ว check50 ไม่มีอยู่จริง ดังนั้นการรันโค้ดกับตัวอย่างอินพุตของคุณเอง การเปรียบเทียบเอาต์พุตจริงกับเอาต์พุตที่คาดหวัง จึงเป็นนิสัยที่ดีที่สุดที่คุณจะได้รับ ณ จุดนี้ เรื่องจริงอย่าเสพติด! หากคุณสนใจที่จะลองใช้ find ของผู้ช่วย cs50 ให้รันคำสั่งนี้: ~cs50/pset3/find

การเรียงลำดับ

การค้นหาเชิงเส้นไม่ใช่สิ่งที่น่าประทับใจอย่างแท้จริง แต่จากการบรรยายครั้งแรก (และในวันที่ 7 เราได้ทำซ้ำเคล็ดลับนี้อีกครั้ง!) คุณจำได้ว่าคุณจะพบเข็มในกองหญ้าได้เร็วกว่ามาก แต่ก่อนอื่นเราต้องเรียงลำดับกองหญ้าของเราก่อน โปรดทราบว่าการเรียกfind.c sortซึ่งเป็นฟังก์ชันที่ประกาศในhelpers.h น่าเสียดายที่เรา “ลืม” ใช้งานฟีเจอร์นี้ในhelpers.c อย่างเต็มรูปแบบ ! ลองเข้าไปที่ helpers.cแล้วคุณจะเห็นว่าการเรียงลำดับนั้นกลับมาทันที แม้ว่าฟังก์ชันหลักของ find จะส่งผ่านอาร์เรย์จริงก็ตาม ตอนนี้จำไวยากรณ์การประกาศอาร์เรย์ คุณไม่เพียงแต่ระบุประเภทองค์ประกอบของอาร์เรย์นี้ แต่คุณยังระบุขนาดในวงเล็บเหลี่ยมด้วย นี่คือสิ่งที่เราทำเพื่อกองหญ้าในfind.c : int haystack [MAX]; แต่เมื่อสำรวจอาร์เรย์ คุณจะระบุเพียงชื่อเท่านั้น และเราทำแบบเดียวกันทุกประการเมื่อเราผ่านกองหญ้าเพื่อทำการเรียงลำดับในfind.c : sort (haystack, size); (ลองเดาดูว่าทำไมเราถึงส่งขนาดของอาร์เรย์นั้นแยกกัน) เมื่อเราประกาศฟังก์ชันที่รับอาร์เรย์หนึ่งมิติเป็นอาร์กิวเมนต์ เราไม่จำเป็นต้องระบุขนาดของอาร์เรย์ ในทำนองเดียวกัน เราไม่ได้ทำเช่นนี้เมื่อเราประกาศ sort ใน helpers.h (และ helpers.c): void sort (int values [] int n); ใช้ sort เพื่อให้ฟังก์ชันเรียงลำดับอาร์เรย์ของตัวเลขจากเล็กไปใหญ่ จำเป็นต้องรันไทม์เท่ากับ O(n ² ) โดยที่ n คือขนาดของอาร์เรย์ คุณอาจต้องการใช้การเรียงลำดับแบบฟอง การเรียงลำดับการเลือก หรือการเรียงลำดับการแทรก ตามที่เราได้เรียนรู้เกี่ยวกับสิ่งเหล่านั้นในสัปดาห์ที่สาม อย่างไรก็ตาม สิ่งสำคัญที่ควรทราบ: ไม่มีวิธีที่ "ถูกต้อง" ในการใช้อัลกอริทึมเหล่านี้ มีรูปแบบต่างๆ มากมาย ในความเป็นจริง คุณสามารถปรับปรุงสิ่ง เหล่านี้ได้เสมอหากคุณเห็นว่าเหมาะสม ตราบใดที่การใช้งานของคุณมาบรรจบกับ O(n2 ⁾ อย่างไรก็ตาม ปล่อยให้การทดลองเป็นหน้าที่ของฟังก์ชัน และเพื่อให้การทดสอบง่ายขึ้น อย่าเปลี่ยนการประกาศการเรียงลำดับของเรา ควรมีลักษณะดังนี้: void sort (int values [] int n); เนื่องจากฟังก์ชันส่งกลับค่าเป็นโมฆะ จึงไม่ควรส่งคืนอาร์เรย์ที่เรียงลำดับแล้ว แต่จะต้องเรียงลำดับอาร์เรย์จริงที่ "ทำงาน" ผ่าน "แบบทำลายล้าง" แทน โดยย้ายองค์ประกอบต่างๆ ในสัปดาห์ที่สี่ เราจะอภิปรายว่าอาร์เรย์ถูกส่งผ่านโดยการอ้างอิง ไม่ใช่ตามค่า นั่นคือ sort จะไม่รับสำเนาของอาเรย์ แต่เป็นอาเรย์ดั้งเดิมเอง แม้ว่าคุณไม่สามารถเปลี่ยนการประกาศการเรียงลำดับของเราได้ แต่คุณสามารถกำหนดฟังก์ชันของคุณเองใน helpers.c ได้ตลอดเวลา ซึ่งสามารถเรียกจากการเรียงลำดับได้ ตัดสินใจด้วยตัวเองว่าวิธีที่ดีที่สุดในการทดสอบการใช้งานการเรียงลำดับของคุณ อย่าลืมว่า printf และ GDB จะช่วยคุณได้! และอย่าลืมว่าคุณสามารถสร้างลำดับตัวเลขสุ่มหลอกที่เหมือนกันซ้ำแล้วซ้ำเล่าโดยระบุค่าเริ่มต้นสำหรับการสร้างอย่างชัดเจน

การค้นหาแบบไบนารีเคล็ดลับ

สิ่งแรกที่คุณต้องเข้าใจเกี่ยวกับ ฟังก์ชัน findคือเราได้เขียนโค้ด (การแจกแจง) ไว้แล้ว เราเพียงแค่เติมช่องว่างบางส่วนในโค้ดที่มีอยู่ โปรแกรมfind.cร้องขอการป้อนตัวเลข (นั่นคือเพื่อเติม "สแต็ก") จากนั้นค้นหา "เข็ม" ในนั้นตามคำขอของผู้ใช้ โดยใช้ฟังก์ชันการเรียงลำดับและการค้นหาที่กำหนดไว้ในhelpers.c ดังนั้นfindเขียนไว้แล้ว เราจึงต้องเขียนhelpers นี่คือสิ่งที่เราต้องทำ:

1. ดำเนินการค้นหา ฟังก์ชันนี้ควรคืนค่าเป็นจริงหากพบค่าในสแต็กและเป็นเท็จหากไม่มีอยู่ในนั้น
2. ใช้ sort ซึ่งเป็นฟังก์ชันที่เรียงลำดับอาร์เรย์ของค่า

ในขั้นต้น การค้นหาจะดำเนินการเป็นเส้นตรง แต่คุณสามารถทำได้ดีกว่า อัลกอริธึมการค้นหา เชิง เส้นทำงานใน เวลาO(n) งานของคุณคือเขียนอัลกอริทึมการค้นหาแบบไบนารี เวลาดำเนินการของมันคือO (log n) อย่างไรก็ตามปัญหาคือจำเป็นต้องจัดเรียงข้อมูลเป็นอินพุต ไม่เช่นนั้นจะไม่ทำงาน คุณจำตัวอย่างหนังสือที่ฉีกขาดได้ และคุณคงรู้ว่าเหตุใดจึงเป็นเช่นนั้น หากคุณได้ผ่านการค้นหาแบบไบนารีผ่านองค์ประกอบต่างๆ และไม่มีเหลือองค์ประกอบเหล่านั้นอีกต่อไป (นั่นคือไม่มี "เข็ม" ใน "สแต็กนี้") คุณต้องใช้ฟังก์ชันเพื่อคืนค่าเท็จ การค้นหาแบบไบนารี่สามารถดำเนินการซ้ำหรือวนซ้ำได้ (David Malan พูดถึงการเรียกซ้ำในการบรรยายที่แปด)