[6-Pokavin] ฝึกทำโจทย์ Data Structures and Algorithms – Recursion/Array/Stack/Queue/Linked Lists

Chapter 4

R-4.3 draw the recursion trace for computation of power (2,18) using repeated squaring algorithm, as implemented in code fragment 4.12.

ตัวโค้ดที่ได้มานั้นมาจาก Code Fragment 4.12 ในหนังสือ

การทำงานของโค้ดจากฟังก์ชั่น power

1.จะทำการเช็คค่า n ที่กำหนดให้ว่ามีค่าเป็น 0 หรือไม่ หากเป็น 0 จะ Return ค่า 1 ออกมาเนื่องจาก 2^0 = 1 นั้นเอง

2.หากไม่ใช่ค่า 0 จะกำหนดให้ partial = power(x,n // 2) โดยที่ n//2 คือการนำค่า n ไปหารสองแล้วปัดเศษลง เช่น หาก n เป็น 3 ค่า n//2 จะมีค่าเท่ากับ 1

3.กำหนดให้ result = partial*partial

4.เช็คค่า n ว่าเป็นจำนวนคี่หรือไม่หากเป็นกำหนดให้ผลลัพธ์มีค่า result*= x หรือก็คือ result = result * x (x ในที่นี้กำหนดให้มีค่าเท่ากับ 2 เนื่องจากเป็นการหาค่ายกกำลังของ 2)

5.return ค่าผลลัพธ์ออกมา

Recursion Trace

C-4.9 Write a short recursive Python fuction that finds the minimum and maximum values in a sequence without using any loop.

การทำงานของฟังก์ชั่น side_values

1.กำหนดให้ side_values รับค่าเป็น num_list

2.กำหนดให้ results_list = sorted(num_list) [นำค่าจาก num_list มาเรียงจากน้อยไปมาก]

3. return ค่า results_list ที่ [0](ตัวที่มีค่าน้อยที่) และ [-1](เนื่องจาก[0]เป็นตัวแรก [-1] จะย้อนไปหาค่าตัวสุดท้ายซึ่งก็คือตัวที่มีค่าเยอะที่สุด)

4.กำหนดค่าให้ฟังก์ชั่น side_values([1, 12, 2, 53, 23, 6, 17])

5.ปริ้นค่า min & max ที่ได้

Chapter 5

P-5.32 Write a Python function that takes two three-dimensional numeric data and add them componentwise.

การทำงานของโค้ด

1.กำหนดค่า size = 3

2.กำหนดให้ memory = []

3.for loop สำหรับสร้าง three-dimensional numeric data โดยให้ค่าข้างในทั้งหมดเป็น 0

4.for loop สำหรับ print ค่า str ที่เก็บไว้ใน memory ทุกตัวออกมา

5. สำหรับการบวกกันของตัว three-dimensional numeric data นั้นผมใช้การ append str แต่ล่ะตัวไปเลย(ซึ่งจะไม่ได้ค่าเป็นการบวกแบบ int ปกติ) และจะต้องทำในทุกๆตัวถึงจะได้ค่าการบวกกันของ three-dimensional numeric data สองตัว

Chapter 6

R-6.8 Supposed an initially empty queue Q has executed a total of 32  enqueue operations , 10 first operations, and 15 dequeue operations, 5 of which raised an empty error that were caught and ignored. What is the current size of Q?

การทำงานของโค้ดแบ่งออกเป็นจะมี 7 ฟังก์ชั่นย่อย

1.เป็นฟังก์ชั่นในการสร้างคิวเปล่าๆขึ้นมาโดยมีขนาด 30

2.เป็นฟังก์ชั่นในการเก็บค่าข้อมูลแต่ล่ะตัวที่ทำการ Enqueue เข้ามาในรูปแบบของ str

3. เป็นฟังก์ชั่นเช็คว่าคิวว่างหรือเปล่า

4.เป็นฟังก์ชั่นเช็คว่าคิวเต็มหรือไม่โดยใช้ คำสั่ง len เทียบกับ limit สูงสุดของคิว (30)

5.เป็นฟังก์ชั่น enqueue โดยจะมี if ย่อยข้างในในการเช็คว่าสามารถ enqueue ได้หรือเปล่า(คิวเต็ม), กำหนดค่าตัวแรกของคิว, บวกจำนวนคิวเพิ่ม

6.เป็นฟังก์ชั่นในการ dequeue โดยจะไม่สามารถ dequeue ได้ถ้าหากคิวว่างและ dequeue โดยคำสั่ง pop

7.เป็นฟังก์ชั่นในการวัดขนาดของคิวโดยใช้คำสั่ง len

 

C-6.30 Alice has two queues, Q and R, which can store integers. Bob gives Alice 50 odd integers and 50 even integers and insists that she store all 100 integers in Q and R. They then play a game where Bob picks Q or R at random and then applies the round-robin scheduler, described in the chapter, to the chosen queue a random number of times. If the last number to be processed at the end of this game was odd, Bob wins. Otherwise, Alice wins. How can Alice allocate integers to queues to optimize her chances of winning? What is her chance of winning?

Chapter 7

R-7.4 Describe in detail how to swap two nodes x and y (and not just their con- tents) in a singly linked list L given references only to x and y. Repeat this exercise for the case when L is a doubly linked list. Which algorithm takes more time?

Singly Linked List

*โค้ดเป็นตัวอย่างโค้ด Singly Linked List จากใน Lab 4.1

การสลับ Node Singly Linked List

Doubly Linked list

*โค้ดเป็นตัวอย่างโค้ด Doubly Linked list จากใน Lab 4.6

การสลับ Node Doubly Linked list

C-7.40 Describe an efficient method for maintaining a favorites list L, with move- to-front heuristic, such that elements that have not been accessed in the most recent n accesses are automatically purged from the list.

 

*เป็นตัวอย่างโค้ดที่ให้มาจากในหนังสือ

การใช้ move-to-front heuristic ใน favorites list นั้นมีข้อดีตรงที่

1.จะทำการจัดเรียงข้อมูลใหม่ทุกครั้งที่ favorites list ถูกเรียกใช้ข้อมูลใดก็ตามจะนำข้อมูลนั้นมาเป็น Node แรกเสมอทำให้ค้นหาข้อมูลที่ใช้บ่อยเจอได้ง่ายขึ้น

2.สามารถเขียนเพิ่มลงไปใน list ได้ง่ายกว่าการเปลี่ยนไปใช้ list แบบอื่นเลย

 

วิดิโออธิบายโค้ด

YouTube Preview Image
  •  
  •  
  •  
  •  
  •  
  •  
Pokavin Pakeeree on sabemail
Pokavin Pakeeree
at GlurGeek.Com
Student, dream chaser

Leave a Reply