Tip:
Highlight text to annotate it
X
>> [เล่นดนตรี]
>> ZAMYLA จัน: สิ่งแรกที่คุณอาจ แจ้งให้ทราบเกี่ยวกับการค้นพบก็คือว่าเราอยู่แล้ว
มีโค้ดที่เขียนสำหรับเรา
นี้เรียกว่ารหัสการกระจาย
ดังนั้นเราไม่ได้เพียงแค่เขียนของเราเอง รหัสจากรอยขีดข่วนอีกต่อไป
แต่เรากำลังการกรอกในช่องว่าง ในบางรหัสที่มีอยู่แล้ว
>> โปรแกรม find.c แจ้งให้สำหรับหมายเลข เพื่อเติมกองหญ้า, การค้นหา
กองหญ้าสำหรับเข็มที่ใช้ส่ง และมันไม่นี้โดยการโทรและการจัดเรียง
ฟังก์ชั่นการค้นหาที่กำหนดไว้ ใน helpers.c
ดังนั้น find.c ถูกเขียนอยู่แล้ว
งานของคุณคือการเขียนผู้ช่วยเหลือ
>> ดังนั้นสิ่งที่เรากำลังทำอะไร
เรากำลังดำเนินการทั้งสองฟังก์ชั่น
ค้นหาซึ่งผลตอบแทนจริงถ้าค่า ที่พบในกองหญ้ากลับ
เท็จถ้าค่าเป็น ไม่ได้อยู่ในกองหญ้า
แล้วเรายังมีการดำเนินการจัดเรียง ซึ่งเรียงลำดับแถวที่เรียกว่าค่า
>> เพื่อให้ต่อสู้ของการค้นหา
การค้นหาจะดำเนินการในปัจจุบันเป็น ค้นหาเชิงเส้น แต่คุณสามารถทำอะไรได้มาก
ดีกว่าว่า
ค้นหาเชิงเส้นจะดำเนินการใน O เวลา n ซึ่งคือค่อนข้างช้า
แม้ว่าจะสามารถค้นหา รายการใด ๆ ที่กำหนดให้
งานของคุณคือการใช้การค้นหาแบบไบนารี ซึ่งได้ใช้เวลา O ของบันทึก n
นั่นคืออย่างรวดเร็ว
>> แต่มีข้อตกลง
ค้นหาแบบไบนารีสามารถค้นหา ผ่านรายการที่เรียงลำดับก่อน
ทำไมจึงเป็นเช่นนั้น
>> ดีให้ดูตัวอย่าง
ป.ร. ให้ไว้ ณ อาร์เรย์ของค่า, กองหญ้าที่ เรากำลังจะมองหา
เข็ม
และในตัวอย่างนี้ สามจำนวนเต็ม
วิธีการที่ค้นหาแบบไบนารีทำงานคือ เราเปรียบเทียบค่ากลางของ
อาร์เรย์ที่เข็มเหมือนวิธี เราเปิดสมุดโทรศัพท์กลาง
ในสัปดาห์หน้าศูนย์
>> ดังนั้นหลังจากการเปรียบเทียบค่ากลาง เข็มคุณสามารถทิ้งอย่างใดอย่างหนึ่ง
ด้านซ้ายหรือด้านขวาของอาร์เรย์ โดยกระชับขอบเขตของคุณ
ในกรณีนี้ตั้งแต่สามเข็มของเรา น้อยกว่า 10 ค่ากลาง
ผูกพันที่เหมาะสมสามารถลด
แต่พยายามที่จะทำให้ขอบเขตของคุณ แน่นที่สุดเท่าที่ทำได้
ถ้าค่าตรงกลางไม่ได้เป็นเข็ม แล้วคุณจะรู้ว่าคุณไม่จำเป็นต้อง
รวมไว้ในการค้นหาของคุณ
ดังนั้นคุณผูกพันที่เหมาะสมสามารถกระชับ ขอบเขตการค้นหาเพียงเล็กน้อยมากขึ้น
และอื่น ๆ และอื่น ๆ จน คุณพบว่าเข็มของคุณ
>> ดังนั้นสิ่งที่จะ pseudocode มีลักษณะอย่างไร
ดีในขณะที่เรายังคงมองผ่าน รายการและยังมีองค์ประกอบ
ดูในเราจะกลางรายการ และเปรียบเทียบค่ากลางที่
เข็มของเรา
หากพวกเขากำลังเท่ากันแล้วนั่นหมายความว่าเราได้ พบเข็มและที่เราสามารถทำได้
กลับจริง
>> มิฉะนั้นถ้าเข็มน้อยกว่า ค่ากลางแล้วนั่นหมายความว่าเรา
สามารถทิ้งครึ่งหนึ่งที่เหมาะสมและเพียงแค่ ค้นหาที่ด้านซ้ายของแถว
มิฉะนั้นเราจะค้นหา ด้านขวาของอาร์เรย์
และในท้ายที่สุดถ้าคุณไม่ได้มี องค์ประกอบอื่น ๆ ที่เหลือในการค้นหา แต่คุณ
ยังไม่พบเข็มของคุณยังแล้วคุณ กลับเท็จเพราะเข็ม
แน่นอนไม่ได้อยู่ในกองหญ้า
>> ตอนนี้สิ่งที่ระเบียบเกี่ยวกับ pseudocode นี้ ในการค้นหาไบนารีที่จะสามารถ
ตีความว่าเป็นอย่างใดอย่างหนึ่งซ้ำแล้วซ้ำอีก หรือการดำเนินการซ้ำ
ดังนั้นมันจะซ้ำถ้าคุณเรียกว่า ฟังก์ชันการค้นหาในการค้นหา
ฟังก์ชั่นในครึ่งหนึ่งของอาร์เรย์ทั้ง
เราจะครอบคลุมการเรียกซ้ำอีกเล็กน้อยในภายหลัง แน่นอน แต่ไม่ทราบว่ามันเป็น
ตัวเลือกถ้าคุณต้องการที่จะลอง
>> ตอนนี้ให้ดูที่การจัดเรียง
เรียงใช้อาร์เรย์และจำนวนเต็ม n ซึ่งเป็นขนาดของอาร์เรย์
ขณะนี้มีชนิดที่แตกต่างกัน แปลกและคุณสามารถดูที่บาง
กางเกงขาสั้นเพื่อการสาธิตและคำอธิบาย
ประเภทผลตอบแทนของเรา ฟังก์ชั่นการจัดเรียงจะถือเป็นโมฆะ
เพื่อที่ว่าหมายความว่าเราจะไม่ เพื่อกลับอาร์เรย์ใด ๆ จากการจัดเรียง
เราจริงจะมีการเปลี่ยนแปลงมาก อาร์เรย์ที่ผ่านเข้ามาในเรา
>> และที่เป็นไปได้เพราะเป็นอาร์เรย์ ผ่านการอ้างอิงในซีตอนนี้เราจะ
ดูรายละเอียดเพิ่มเติมเกี่ยวกับเรื่องนี้ในภายหลัง แต่ ความแตกต่างที่สำคัญระหว่างการผ่าน
ในสิ่งที่ต้องการจำนวนเต็มและผ่าน ในอาร์เรย์คือว่าเมื่อคุณ
ผ่านในจำนวนเต็ม C เป็นเพียงการไป ทำสำเนาของจำนวนเต็มที่และผ่าน
มันฟังก์ชั่น
ตัวแปรเดิมจะไม่สามารถเปลี่ยนแปลงได้ เมื่อทำงานเสร็จสิ้น
กับอาร์เรย์ในมืออื่น ๆ ก็ จะไม่ทำสำเนาและคุณจะ
จริงจะแก้ไข อาร์เรย์ตัวเองมาก
>> ดังนั้นประเภทหนึ่งของการจัดเรียงเป็น เรียงลำดับการเลือก
เรียงลำดับการเลือกทำงานโดยเริ่มต้นที่ จุดเริ่มต้นและจากนั้นคุณย้ำ
กว่าและหาองค์ประกอบที่เล็กที่สุด
แล้วคุณสลับที่เล็กที่สุด องค์ประกอบกับคนแรก
แล้วคุณจะย้ายไปยังองค์ประกอบที่สอง หาที่เล็กที่สุดต่อไป
องค์ประกอบและจากนั้นสลับที่กับ องค์ประกอบที่สองในอาร์เรย์เพราะ
องค์ประกอบแรกจะเรียงลำดับแล้ว
และอื่น ๆ แล้วคุณยังคงสำหรับทุก องค์ประกอบในการระบุที่เล็กที่สุด
ค่าและการแลกเปลี่ยนมันออกมา
>> เพราะเราเท่ากับ 0, องค์ประกอบแรกมาก n การลบ 1, คุณจะเปรียบเทียบ
ทุกค่าถัดไปหลังจากนั้นและหา ดัชนีของค่าต่ำสุด
เมื่อคุณพบดัชนีค่าต่ำสุด คุณสามารถสลับค่าของแถวที่
ขั้นต่ำและแถวที่หนึ่ง
>> ประเภทของการจัดเรียงอื่นที่คุณสามารถ ดำเนินการจัดเรียงฟอง
ดังนั้นการจัดเรียงฟอง iterates ผ่านรายการ เปรียบเทียบองค์ประกอบอยู่ติดกันและ
การแลกเปลี่ยนองค์ประกอบที่ อยู่ในลำดับที่ไม่ถูกต้อง
และวิธีนี้เป็นองค์ประกอบที่ใหญ่ที่สุด ฟองจะสิ้นสุด
และรายการที่มีการจัดเรียงอีกไม่มาก องค์ประกอบได้รับการสลับ
>> ดังนั้นผู้เป็นสองตัวอย่างของการจัดเรียง ขั้นตอนวิธีการที่คุณสามารถใช้เพื่อ
โปรแกรมพบ
เมื่อคุณเสร็จสิ้นการจัดเรียงและคุณได้ ทำค้นหาคุณดำเนินการเสร็จสิ้น
ชื่อของฉันคือ Zamyla และนี่คือ CS50
>> [เล่นดนตรี]