Python Lab Midterm

 1.P-4.26 Write a program that can solve instances of the Tower of Hanoi problem
(from Exercise C-4.14).

จากโจทย์ – ให้เขียนโปรแกรมแก้ปัญหา Tower Of Hanoi

• Answer

Tower of Hanoi จะประกอบด้วยหมุด 3 แท่ง และ จานกลมแบนขนาดต่าง ๆ ซึ่งมีรูตรงกลางสำหรับให้หมุดลอด เกมเริ่มจากจานทั้งหมดวางอยู่ที่หมุดเดียวกัน โดยเรียงตามขนาดจากใหญ่ที่สุดอยู่ทางด้านล่าง จนถึงจานขนาดเล็กที่สุดอยู่ด้านบนสุด เป็นลักษณะกรวยคว่ำตามรูป

 

ป้าหมายของเกมคือ พยายามย้ายกองจานทั้งหมดไปไว้ที่อีกหมุดหนึ่ง โดยการเคลื่อนย้ายจานจะต้องเป็นไปตามกติกาคือ

• สามารถย้ายจานได้เพียงครั้งละ 1 ใบ
• ไม่สามารถวางจาน ไว้บนจานที่มีขนาดเล็กกว่าได้

Link Youtube

————————————————————————————————————————————————————

2.R-5.8 Experimentally evaluate the efficiency of the pop method of Python’s list
class when using varying indices as a parameter, as we did for insert on
page 205. Report your results akin to Table 5.5.

จากโจทย์ – การคำนวนของ Efficiency of the pop method of python’s list class เมื่อใช้ค่าตาม parameter หน้า 205, ให้บันทึกค่าที่คล้ายกับ ตาราง 5.5

• Answer

จากตาราง 5.5 จะเป็นการแสดงค่าของเวลาเฉลี่ยที่ทำการแทรกค่าเข้าไปในลิสต์โดยจะใช้ Parameter N ในการกำหนดค่าที่ต้องการเพิ่มลงไปในลิสต์ โดยจะมีคำสั่งของการที่จะเพิ่มค่าเข้าไปใน List มีทั้งหมด 3 Case ดังนี้

Case 1 จะเป็นการเพิ่มข้อมูลจากด้านหน้าหรือตัวเริ่มต้น (0)

Case 2 จะเป็นการเพิ่มข้อมูลจากตรงกลาง (N//2)

Case 3 จะเป็นการเพิ่มข้อมูลจากด้านหลังหรือส่วนท้ายของข้อมูล (N)

โดยมองข้อมูลจาก List ข้อมูลดังนี้

ผลลัพธ์ของการเพิ่มข้อมูลในแบบ Case ต่าง ๆ จะมีเวลาเฉลี่ยในการเพิ่มข้อมูลดังนี้

จะเห็นว่าเวลาเฉลี่ยของการเพิ่มข้อมูลในแต่ละ Case จะแสดงผลลัพธ์ที่แตกต่างกันอย่างสิ้นเชิงโดยวัดจากปริมาณข้อมูล(N)ที่มีปริมาณมาก ๆ โดยความเร็วของการเพิ่มข้อมูลจะเรียงลำดับดังนี้ K=n < k=n//2 < k=0

LINK Youtube

————————————————————————————————————————————————————

3.P-6.33 Give an array-based implementation of a double-ended queue supporting
all of the public behaviors shown in Table 6.4 for the collections.dequeclass, including use of the maxlen optional parameter. When a length-limited deque is full, provide semantics similar to the collections.dequeclass, whereby a call to insert an element on one end of a deque causes an
element to be lost from the opposite side.

จากโจทย์ – ถามว่าจากตัว Implementation ในตาราง 6.4 เมื่อขนาดของ Deque เต็มแล้ว เมื่อเพิ่มตัว element เข้าไปในคิว สาเหตุที่ทำให้ตัว element ตรงข้ามกันตัวหนึ่งหายไปคืออะไร

• Answer

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

LINK Youtube

————————————————————————————————————————————————————

4.C-7.29 Describe in detail an algorithm for reversing a singly linked list L using
only a constant amount of additional space and not using any recursion.

จากโจทย์ – อธิบายรายละเอียด Algorithm ของ reversing a singly link list L และไม่ใช้ recursion ใด ๆ

• Answer

การเรียงค่า link list แบบกลับ จะมี Algorithm ดังรูปต่อไปนี้

1.

2.

3.

4.

5.

โดยการทำงานหลักๆของ Algorithm นี้จะทำงานโดยเช็คอยู่ 4 ค่า คือค่าของสถานะได้แก่

1. previous (ก่อนหน้า)
2. next (ถัดไป)
3. current (ปัจจุบัน)
4. head (หัว)

การทำงานของ Algorithm หลักที่จะต้องดูคือค่าของ Current ว่าอยู่ตรงไหนโดยถ้าไปอยู่ตรงที่ Null จะเป็นการหลุด loop เลยโดยที่ Head จะตกไปอยู่ที่สถานะก่อนหน้า Current โดยบรรทัด Code ที่จะชี้กลับไปจะไปอยู่ที่บรรทัดที่

Current->next = prev;

โดยบรรทัดนี้จะเป็นการชี้กลับไปยังค่าเริ่มต้นเพื่อทำการ Reversing Link List โดยที่จะไม่ใช้ Recursive

————————————————————————————————————————————————————

• Line