[4 Thanawan] ฝึกทำโจทย์ Data Structures and Algorithms – Tree/Sorting/Graph

             สวัสดีค่ะ ในส่วนของบทความนี้ผู้เขียนมีวัตถุประสงค์เพื่อให้ผู้อ่านที่มีความตั้งใจที่จะศึกษาหาความรู้ และทำความเข้าใจในเรื่องต่างๆ ของวิชา Data Structure รวมถึงหลักการ องค์ประกอบ  และขั้นตอนการเขียนโปรแกรมในภาษาต่างๆเบื้องต้น เพื่อให้ผู้อ่านได้รับประโยชน์ในการเขียนโปรแกรมต่างๆทางด้านวิชาการในระดับอุดมศึกษา ซึ่งเป็นส่วนหนึ่งของการสําเร็จการศึกษา ดังจะกล่าวตามลําดับต่อไปนี้ เริ่มต้นกันด้วย ข้อ C-8.54

C-8.54 Design an algorithm for drawing general trees, using a style similar to the inorder traversal approach for drawing binary trees.

แปลโจทย์ : การออกแบบอัลกอริทึมสำหรับการวาดภาพ tree ทั่วไปโดยใช้สไตล์ที่คล้ายคลึง inorder traversal กับในการวาด binary tree

Code ()

หลักการทำงานของโปรแกรม

เป็นการเดินเข้าไปเยือนโหนดต่าง ๆใน tree ด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้

(1) ท่องไปใน tree ย่อยทางซ้ายแบบ inorder

(2) เยือนโหนดราก

(3) ท่องไปใน tree ย่อยทางขวาแบบ inorder

Example

___________________________________________________________

 

 

 

C-12.4 Describe an in-place version of the quick-select algorithm in pseudo-code, assuming that you are allowed to modify the order of elements.

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

Code ()

หลักการทำงานของโปรแกรม

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

จากรูปแสดงให้เห็นว่า 54 จะทำหน้าที่เป็นค่าเดือยแรกของเรา เนื่องจากเราได้ดูตัวอย่างนี้ไม่กี่ครั้งแล้วเรารู้ว่า 54 จะสิ้นสุดในตำแหน่งที่ถืออยู่ 31 กระบวนการพาร์ทิชันจะเกิดขึ้นต่อไป จะพบจุดแยกและในเวลาเดียวกันย้ายรายการอื่น ๆ ไปยังด้านที่เหมาะสมของรายการทั้งที่น้อยกว่าหรือมากกว่าค่าเดือย

Example

__________________________________________________________

R-14.25 Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of the Prim-Jarn ́ık algorithm for computing the minimum spanning tree of this graph.

แปลโจทย์ : วาดกราฟที่มีการใช้งานง่ายแบบเชื่อมต่อแบบไม่มีทิศทางซึ่งมี 8 จุดและ 16 ขอบแต่ละอันมีน้ำหนักที่ไม่ซ้ำกัน แสดงการดำเนินการของอัลกอริทึม Prim-Jarn ́ık สำหรับการคำนวณโครงสร้างสแปนนิ่งขั้นต่ำของกราฟนี้

Code ()

หลักการทำงานของโปรแกรม

ให้ V เป็นชุดของจุดยอดทั้งหมด ความคิดพื้นฐานคือเริ่มต้นด้วยจุดสูงสุดโดยพลการและเพิ่มไปยังชุดใหม่ S ทำซ้ำต่อไปนี้จนกว่า S = V:

หาขอบที่มีต้นทุนต่ำสุดที่เชื่อมต่อv∈Sกับจุดสูงสุดw∉S

เพิ่มขอบที่ e ไปยังชุดของขอบ T (มันจะกลายเป็นต้นไม้ของคุณ)

เพิ่ม w ไปยัง S.

ตัวอย่างเช่นสมมติว่าคุณเริ่มต้นที่จุดสุดยอด 4 ดังนั้น S = {4} จะเริ่มต้น ขอบต้นทุนต่ำสุดที่นำค่า “ออกจาก” S 2 ขอบเชื่อมต่อขอบ 4 ถึง 5 ตอนนี้ S = {4,5}

เพื่อให้ได้คำตอบแบบเต็มคุณจะดำเนินการต่อไปจนกว่า S = {1,2,3,4,5} ปัญหาของฉันเกี่ยวกับปัญหาคือลำดับขอบถูกเลือกขึ้นอยู่กับจุดยอดที่คุณเริ่มต้น แต่หวังว่าตอนนี้คุณคุ้นเคยกับอัลกอริธึมของ Prim แล้ว

Example

__________________________________________________________

 

และนี่ก็คือคลิปอธิบายหลักการทำงานของโค้ดด้านบนแบบละเอียดนะคะ

 

สำหรับบทความนี้ ก็จบลงเพียงเท่านี้นะคะ ขอบคุณค่ะ

  •  
  •  
  •  
  •  
  •  
  •  
THANAWAN KAMOLSUKSRI
at GlurGeek.Com
นางสาวธนวรรณ กมลสุขศรี 1590901920 ศึกษาอยู่คณะวิศวกรรมศาสตร์ ภาควิชาวิศวกรรมคอมพิวเตอร์

Leave a Reply