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

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

เกมเริ่มต้นแล้ว!

ถึงเวลาเล่นแล้ว! คนส่วนใหญ่คุ้นเคยกับเกมปริศนา "Tag" เพื่อให้เป็นระเบียบ "แท็ก" เป็นฟิลด์ 4x4 สองมิติในฟิลด์นี้ไม่มี 16 แต่มี 15 สี่เหลี่ยมนั่นคือหนึ่งช่องยังคงว่างเปล่า แต่ละช่องจะมีหมายเลขและสามารถเคลื่อนที่ในแนวนอนหรือแนวตั้งภายในสนามได้ (แน่นอนว่ายังมีที่ว่างให้ขยับได้) เป้าหมายคือการวางตัวเลขตามลำดับตั้งแต่ 1 ถึง 15 จากซ้ายไปขวาจากบนลงล่าง จากนั้นพื้นที่ว่างจะอยู่ที่มุมขวาล่าง การเคลื่อนไหวของไทล์ใด ๆ (หรือหลาย ๆ อัน) ถือเป็น "ขั้นตอน" ในพื้นที่เกมนี้ ชุดค่าผสมที่แสดงในภาพด้านบนนั้นซ้อนกันอยู่แล้ว แต่โปรดทราบว่าสามารถดันแผ่นกระเบื้อง 12 หรือ 15 แผ่นลงในพื้นที่ว่างได้ กฎระบุว่าไม่สามารถเคลื่อนย้ายไทล์ในแนวทแยงหรือนำออกจากกระดานเล่นได้ จริงๆ แล้วมีการกำหนดค่ามากมายในการเริ่มเกม (คุณสามารถนับได้อย่างแน่นอน) แต่เพื่อความง่าย ลองจัดเรียงไทล์ตามลำดับจากใหญ่ที่สุดไปเล็กที่สุด และเว้นที่ว่างไว้ที่มุมขวาล่างของกระดาน . สิ่งเดียวคือลองสลับ 1 และ 2 เพื่อที่จะไขปริศนาได้ ตอนนี้ไปที่ไดเร็กทอรี~/ของ workbench จากนั้น /pset3/fifteenและเปิดfifteen.c มันมีรหัสสำหรับเอ็นจิ้นเกม ภารกิจคือการเพิ่มโค้ดให้กับเกม แต่ก่อนอื่น มารวบรวม "เครื่องยนต์" ของเรากันก่อน (คุณคงรู้วิธีการทำเช่นนี้อยู่แล้ว) แม้ว่าเกมจะยังไม่จบ แต่คุณสามารถเปิดแอปพลิเคชันได้ จะสะดวกกว่าหากเรียกใช้ในหน้าต่างเทอร์มินัลที่ใหญ่กว่าปกติ ซึ่งสามารถเปิดได้โดยคลิกที่เครื่องหมายบวกสีเขียว (+) ถัดจากแท็บโค้ดแท็บใดแท็บหนึ่งแล้วเลือกเทอร์มินัลใหม่ หรือคุณสามารถเปิดหน้าต่างเทอร์มินัลแบบเต็มหน้าจอได้โดยคลิกที่ ไอคอน ขยายใหญ่สุดที่มุมขวาบนของคอนโซล คุณจะเห็นว่าบางสิ่งได้ผล แต่ในความเป็นจริงแล้วเกมส่วนใหญ่ยังไม่ได้เขียนเลย และที่นี่ - เตรียมพร้อม - คือทางออกของคุณ!

ศึกษา

ศึกษาโค้ดและความคิดเห็นของ fifteen.cแล้วตอบคำถามด้านล่าง:

1. นอกเหนือจากบอร์ด 4x4 แล้ว เครื่องยนต์ของเราอนุญาตให้ใช้สนามขนาดใดได้บ้าง?
2. โครงสร้างข้อมูลของฟิลด์เกมคืออะไร?
3. ฟังก์ชั่นอะไรที่เรียกว่าทักทายผู้เล่นเมื่อเริ่มเกม?
4. คุณต้องใช้คุณสมบัติอะไรบ้าง?
5. หมายเหตุ: หากคุณต้องการให้ตรวจสอบอัตโนมัติบอกคุณว่าคุณตอบคำถามถูกต้องหรือไม่ ให้ค้นหาไฟล์ fifteen.txt ถัดจากไฟล์ fifteen.c และจดคำตอบสำหรับคำถามเหล่านี้ไว้

การนำไปปฏิบัติ

เรามาเริ่มใช้งานเกมกันดีกว่า จำไว้ว่าเรากำลังก้าวไปทีละก้าว อย่าพยายามทำทุกอย่างพร้อมกัน แต่ให้ลองใช้ฟีเจอร์ทีละรายการแทน และตรวจสอบให้แน่ใจว่าฟีเจอร์เหล่านั้นใช้งานได้ก่อนที่จะดำเนินการต่อ โดยเฉพาะอย่างยิ่ง เราขอแนะนำให้คุณใช้ฟังก์ชันเกมตามลำดับต่อไปนี้: เริ่มต้น (การเริ่มต้น) เสมอ (วาด) เคลื่อนที่ (ก้าวหนึ่ง) ชนะ (ชนะ) การตัดสินใจในการออกแบบ (เช่น พื้นที่ว่างที่จะแทรกระหว่างไทล์ตัวเลขของเรา) เป็นของคุณ สนามแข่งขันควรมีลักษณะดังนี้: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ อีกครั้งหนึ่ง โปรดทราบว่าในตำแหน่งเริ่มต้น 1 และ 2 จะอยู่ในลำดับย้อนกลับ (ใช้กับสนาม 4x4 แบบคลาสสิก หากจำนวนช่องเป็นเลขคี่) หากจำนวนไทล์เป็นเลขคู่และฟิลด์เป็น 3x3 ไม่จำเป็นต้องสลับไทล์ที่ "ต่ำที่สุด" สองอัน 8 7 6 5 4 3 2 1 _ หากต้องการทดสอบการใช้งาน "แท็ก" คุณต้องลองเล่นมัน (อย่าลืม คุณสามารถออกจากโปรแกรมก่อนที่มันจะเสร็จสมบูรณ์ตามปกติโดยกดคีย์ผสม crtl+c) ตรวจสอบให้แน่ใจว่าโปรแกรมจะทำงานหากป้อนตัวเลขไม่ถูกต้อง และจำไว้ว่าเมื่อคุณป้อนข้อมูลการค้นหาโดยอัตโนมัติ คุณสามารถทำให้ “คำแนะนำ” ของเกมเป็นแบบอัตโนมัติได้ ที่จริงแล้ว ใน โฟลเดอร์ ~cs50/pset3มีไฟล์3x3.txtและ4x4.txtซึ่งมีลำดับขั้นตอนทั้งหมดสำหรับการชนะในฟิลด์ 3x3 และ 4x4 หากต้องการทดสอบโปรแกรม เช่น ใช้ไฟล์แรก ให้รันคำสั่งต่อไปนี้ ./fifteen 3 < ~cs50/pset3/3x3.txt ตั้งค่าอาร์กิวเมนต์ที่คุณต้องการเพื่อเพิ่มความเร็วให้กับแอนิเมชั่น และโดยทั่วไป หากคุณต้องการ คุณสามารถเปลี่ยนเกมได้ตลอดเวลา เพื่อความสนุกสนานกับ "ANSI Escape Sequences" รวมไปถึงสีสัน ดูการใช้งานclear ของเรา และดูที่http://isthe.com/chongo/tech/comp/ansi_escapes.htmlเพื่อเรียนรู้เทคนิคใหม่ๆ หากคุณต้องการ ให้เขียนฟังก์ชันของคุณเองหรือเปลี่ยนต้นแบบของฟังก์ชันที่เราเขียน ข้อจำกัดเพียงอย่างเดียวคือ คุณไม่เปลี่ยนลอจิกของฟังก์ชันหลัก มิฉะนั้น เราจะไม่สามารถใช้การทดสอบอัตโนมัติบางอย่างเพื่อยืนยันว่าโปรแกรมของคุณทำงานอย่างถูกต้อง โดยเฉพาะอย่างยิ่ง main จะต้องคืนค่า 0 หากผู้ใช้ไขปริศนาได้เท่านั้น ต้องส่งคืนค่าที่ไม่ใช่ศูนย์สำหรับตัวเลือกข้อผิดพลาดทั้งหมด หากมีข้อผิดพลาดเกิดขึ้น โปรดเขียนถึงเรา หากคุณต้องการเล่นกับการใช้งานแอปพลิเคชันที่เตรียมไว้โดยผู้ช่วย CS50 ให้รันคำสั่งต่อไปนี้: ~cs50/pset3/fifteen หากคุณสนใจที่จะเห็นการใช้งานที่เจ๋งกว่าพร้อมการไขปริศนาอัตโนมัติ ลองดูโปรแกรมเวอร์ชัน "แฮ็กเกอร์": ~cs50/hacker3/fifteen แทนที่จะป้อนตัวเลขในหน้าต่างเกม ให้พิมพ์คำว่าGOD. เยี่ยมมากใช่มั้ย? หากคุณต้องการตรวจสอบความถูกต้องของโปรแกรมของคุณอย่างเป็นทางการด้วย check50 โปรดทราบว่า check50 จะถือว่าพื้นที่ว่างของสนามเด็กเล่นเต็มไปด้วย 0; หากคุณเลือกค่าอื่น ให้แทนที่ด้วยศูนย์เพื่อการตรวจสอบความถูกต้อง นอกจากนี้ check50 จะถือว่าคุณกำลังสร้างดัชนีฟิลด์บอร์ดตามลำดับ [แถว] [คอลัมน์] ไม่ใช่บอร์ด [คอลัมน์] [แถว] check50 2015.fall.pset3.fifteen fifteen.c

เรียนรู้เพิ่มเติมเกี่ยวกับการใช้งานฟังก์ชันเกมทั้งสิบห้า

• init (การเริ่มต้น)
• วาด
• ย้าย (ก้าว)
• ชนะ (ชนะ)

ในนั้น

ในฟังก์ชันนี้ เราจะแนะนำสนามเด็กเล่น ในการดำเนินการนี้ เราใช้อาร์เรย์จำนวนเต็มสองมิติ มิติข้อมูลอาร์เรย์คือ MAX x MAX โดยที่ MAX คือค่าคงที่ที่ระบุจำนวนไทล์สูงสุดที่สามารถใส่ในแถวหรือคอลัมน์ของฟิลด์ได้ ดังนั้น เราจำเป็นต้องกำหนดตัวแปรint board[MAX][MAX] อย่างไรก็ตาม โปรดจำไว้ว่าขนาดของสนามเด็กเล่นจะถูกกำหนดโดยผู้ใช้ ดังนั้นเราจึงจำเป็นต้องกำหนดตัวแปรที่จะระบุขนาดบอร์ดที่ผู้ใช้ต้องป้อน นี่คือint d โดยที่ d คือมิติของบอร์ด d <= MAX อย่างไรก็ตาม ในภาษา C คุณไม่สามารถเปลี่ยนขนาดของอาร์เรย์ได้ ดังนั้นคุณต้องกำหนดขนาดสูงสุด ในการเริ่มต้นคุณต้องใส่ค่าบนกระดาน อ่านเพิ่มเติมเกี่ยวกับอาร์เรย์สองมิติหากคุณยังไม่ได้ใช้งาน กล่าวโดยสรุป มีสองดัชนี ดัชนีแรกหมายถึงหมายเลขแถว ดัชนีที่สองคือหมายเลขคอลัมน์ สำหรับปัญหาของเรา เราเริ่มต้นด้วยจำนวนสูงสุดและสิ้นสุดในกรณีของ d = 3 (“แปด”) ด้วยหนึ่งและมุมว่าง หากเรายังมี “แท็ก” เราก็จะสลับ 1 และ 2 จะทำอย่างไรกับพื้นที่ว่าง? อาร์เรย์ของเราประกอบด้วยจำนวนเต็ม ดังนั้นช่องว่างจึงต้องเติมจำนวนเต็มบางส่วน ดังนั้น คุณต้องเลือกจำนวนเต็มเพื่อเริ่มต้นไทล์ว่าง (หรือในกรณีของเกมจริง จะต้องไม่มีไทล์) สามารถใช้ลูปเพื่อเริ่มต้นกระดานเกมและเติมด้วยชุดแผ่นเริ่มต้น เราวนซ้ำดัชนี i และ j โดยที่board[i][j]เป็นไทล์ที่อยู่ในแถวหมายเลข i และคอลัมน์หมายเลข j เราเติมกระดานตามลำดับจากมากไปน้อย หากจำนวนไทล์ (ไม่มีช่องว่าง) เป็นเลขคี่ ให้สลับ 1 และ 2

วาด

ฟังก์ชันนี้ควรพิมพ์สถานะปัจจุบันของสนามเด็กเล่น โปรดจำไว้ว่าเราสามารถมีค่าหนึ่งหรือสองหลักได้ ดังนั้นสำหรับการจัดรูปแบบที่สวยงามหลังหมายเลข 1-9 ฟังก์ชันควรเว้นวรรค ( #s ) ซึ่ง สามารถทำได้โดยใช้ ตัวยึดตำแหน่ง %2d printf (“%2d”, board[i][j]); อย่าลืมเกี่ยวกับเซลล์ว่างด้วย เลือกอักขระที่จะเป็นตัวแทน (ในตัวอย่างของเรา นี่คือขีดล่าง) ฟังก์ชันวาดควรวาดอักขระนี้ทันทีที่คุณเข้าสู่เซลล์ว่าง ดังนั้นการวนซ้ำของเราจะเป็นดังนี้: for каждой строки for каждого element строки print meaning и пробел print новую строку โปรดจำไว้ว่าลำดับที่ฟังก์ชัน Draw ดึงไทล์ไปที่หน้าจอควรสะท้อนถึงลำดับที่อยู่ในอาร์เรย์ที่กำหนดไว้ในฟังก์ชัน init

เคลื่อนไหว

เมื่อคุณได้เริ่มต้นสนามเด็กเล่นและวาดตำแหน่งไทล์เริ่มต้นแล้ว คุณต้องอนุญาตให้ผู้ใช้แก้ไขตำแหน่งของไทล์ ซึ่งก็คือ ทำการเคลื่อนไหว ดังนั้นในFifteen.cโปรแกรมจะรับเอาต์พุตจากผู้ใช้ สร้างบอร์ดเกม จากนั้นเรียกใช้ฟังก์ชันย้าย และบอกว่าไทล์ใดที่เขาต้องการย้าย ระวัง: คุณกำลังใช้ฟังก์ชันกับตัวเลขบนไทล์โดยเฉพาะ และไม่ใช่กับตำแหน่งบนกระดาน (ในอาร์เรย์) ดังนั้นคุณต้องค้นหาตำแหน่งที่แท้จริงของกระเบื้อง นอกจากนี้ คุณควรอนุญาตให้ผู้ใช้ย้ายไทล์เมื่อเป็นไปได้เท่านั้น ในภาพด้านบน เราสามารถย้ายได้เฉพาะไทล์หมายเลข 2, 5 และ 8 เท่านั้น จะทราบได้อย่างไร? โดยค่าของกระเบื้องเปล่า ดังนั้น ฟังก์ชัน moveจึงมีลักษณะดังนี้:

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

วอน

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

วิธีตรวจสอบรหัสของคุณและรับเครื่องหมาย

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

1. เข้าสู่ระบบ CS50 IDE
2. ใกล้กับมุมซ้ายบนของ CS50 IDEซึ่งเป็นที่ตั้งของไฟล์เบราว์เซอร์ (ไม่ใช่ในหน้าต่างเทอร์มินัล) ให้คลิกขวาที่ไดเร็กทอรี pset3 ของคุณแล้วคลิกDownload คุณจะเห็นว่าเบราว์เซอร์ดาวน์โหลด ไฟล์เก็บ ถาวร pset3.tar.gzแล้ว
3. ในหน้าต่างหรือแท็บแยกต่างหาก ให้เข้าสู่ระบบ CS50 ส่ง
4. คลิกที่ ไอคอน ส่งที่มุมซ้ายบนของหน้าจอ
5. ในรายการโฟลเดอร์ทางด้านซ้าย ให้คลิกที่ ไดเร็กทอรี Problem Set 3จากนั้นคลิกปุ่มอัปโหลดการส่งใหม่ มันอยู่ทางขวา
6. บนหน้าจอที่ปรากฏขึ้นให้คลิกที่ ปุ่ม เพิ่มไฟล์ ... หน้าต่างสำหรับเลือกไฟล์จากคอมพิวเตอร์ของคุณจะเปิดขึ้น
7. นำทางไปยังโฟลเดอร์ที่คุณบันทึก pset3.tar.gz ส่วนใหญ่แล้วจะอยู่ใน โฟลเดอร์ Downloads ของคุณ หรือที่ใดก็ตามที่เบราว์เซอร์ของคุณใส่ไฟล์ตามค่าเริ่มต้น เมื่อคุณพบpset3.tar.gzให้คลิกที่หนึ่งครั้งเพื่อเลือก จากนั้นคลิกOpen
8. คลิกเริ่มอัปโหลด ไฟล์ของคุณจะถูกอัป โหลด ไปยัง เซิร์ฟเวอร์CS50
9. บนหน้าจอที่ปรากฏขึ้น คุณจะเห็นหน้าต่างNo File Selected หากคุณเลื่อนเคอร์เซอร์ไปทางซ้าย คุณจะเห็นรายการไฟล์ที่ดาวน์โหลด เพื่อยืนยันให้คลิกที่แต่ละรายการ หากคุณไม่แน่ใจเกี่ยวกับบางสิ่งบางอย่าง คุณสามารถอัปโหลดไฟล์อีกครั้งโดยทำซ้ำขั้นตอนเดียวกัน คุณสามารถทำเช่นนี้ได้บ่อยเท่าที่คุณต้องการจนถึงสิ้นปี 2559