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

สวัสดีครับวันนี้ผมจะมาแสดงวิธีทำ ของโจทย์จากหนังสือ Data-Structures and Algorithms in python ของผมจะมีทั้งหมด 7 ข้อได้แก่ P-4.25, R-5.3, C-5.20, R-6.10, C-6.31, R-7.2, C-7.41 แต่คำตอบของผมอาจจะไม่ถูกต้องทั้งหมดและอาจมีการปรับเปลี่ยนโจทย์ให้สามารถทำได้ง่ายขึ้นครับ

 

มาเริ่มข้อแรกกันเลยครับ คือข้อ P-4.25 จะเป็นเรื่อง Recursion, Recursion คือการเรียกใช้ฟังก์ชั่นที่เรียกใช้ตัวเอง การเขียนโปรแกรม Recursion เพื่อให้การหาคำตอบทำได้ง่ายขึ้น โจทย์คือ

Provide a non-recursive implementation of the draw interval function for the English ruler project of Section 4.1.2. There should be precisely 2^c−1 lines of output if c represents the length of the center tick. If incrementing a counter from 0 to 2^c −2, the number of dashes for each tick line should be exactly one more than the number of consecutive 1’s at the end of the binary representation of the counter.

จากโจทย์ที่ได้ ผมจะใช้ Recursion Code ในการเรียกใช้ฟังก์ชั่นซ้ำๆ ในการทำไม้บรรทัด (English ruler) จากรูปด้านร่าง

จะเห็นได้ว่า Code ใน function main มีแค่เพียง 2 บรรทัด บรรทัดแรกคืออการเรียกใช้ function draw_ruler และใน function draw_ruler กูจะไปเรียกใช้ function draw_line และ draw_interval เพื่อให้ output ออกมาเป็นไม้บรรทัดแบบด่านล่าง

 

ข้อต่อมาข้อ R-5.3 จะเป็นเรื่อง Array-Based Sequences

Modify the experiment from Code Fragment 5.1 in order to demonstrate that Python’s list class occasionally shrinks the size of its underlying array when elements are popped from a list.

   code Fragment 5.1

จากโจทย์จะให้แสดงการทำงานใน python และดูขนาดของ array เมื่อมีelement ถูก popped
และ Code ด่านล่างจะแสดงในเห็นขนาด และขนาดในbytes บนการทำของของ python

 code R-5.3

                                                                                     output R-5.3

     ข้อต่อมาก็ยังเป็นเรื่องของ Array-Based Sequences ก็คือข้อ C-5.20 จากโจทย์

Consider a variant of Exercise C-5.16, in which an array of capacity N, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/2. Show that there exists a sequence of n operations that requires Ω(n2) time to execute.

ให้เรานำโจทย์จากข้อ C-5.16 มาปรับเปลี่ยน และในโจทย์ C-5.16 ก็ให้เอา Code จาก Code Fragment5.3

นี่ก็คือCode การสร้าง Dynamic Array โดย

Function init เหมือนเป็นการประกาศค่าต่างของ Code ต่อมา

Function len ก็เป็นฟังชั่นที่บอก ขนาดของ Array

Function get item เป็นการรับค่า

Function append คือการกำหนดความจุของ Array

ส่วนรูปด้านล่างคือการทำงานคร่าวๆของ Code ด้านบน

 

ข้อต่อไปเป็นข้อ R-6.10 เป็นเรื่องของ Stack/Queues/Deques ในที่นี้โจทย์ที่ได้ก็คือ

Consider what happens if the loop in the ArrayQueue. resize method at
lines 53–55 of Code Fragment 6.7 had been implemented as:

for k in range(self. size):
self. data[k] = old[k]               # rather than old[walk]

Give a clear explanation of what could go wrong.

จากรูปก็คือ Code ของ Array Queue การทำงานคือ FIFO หรือ First in first out โดยจะใช้ ฟังก์ชั่น enqueue ในการรับค่าและฟังก์ชั่น dequeue เพื่อเอาค่าออก

 

นี่คือตัวอย่างคำสั่งการใช้ array queue แบบ FIFO

และ output ที่ได้จะเป็นแบบนี้

    ข้อต่อไปเป็นข้อที่ ยาก ที่สุดสำหรับผมเพราะผมไม่สารามถเขียน Code ข้อนี้ออกมาได้แต่สามารถ หา solution ในการแก้โจทย์ได้ เพราะฉะนั้น จะแสดงให้เพียงวิธีแก้โจทย์ไม่มี code ครับ ข้อนั้นคือ C-6.31

Suppose Bob has four cows that he wants to take across a bridge, but only  one yoke, which can hold up to two cows, side by side, tied to the yoke. The yoke is too heavy for him to carry across the bridge, but he can tie (and untie) cows to it in no time at all. Of his four cows, Mazie can cross the bridge in 2 minutes, Daisy can cross it in 4 minutes, Crazy can cross it in 10 minutes, and Lazy can cross it in 20 minutes. Of course, when two cows are tied to the yoke, they must go at the speed of the slower cow. Describe how Bob can get all his cows across the bridge in 34 minutes.

วิธีแก้โจทย์คือ

ให้ผูก Daisy(4mins) กับ Mazie(2mins) นำทั้งคู่ข้ามสะพานไป จะใช้เวลา 4 นาที
กลับมากลับ Mazie(2mins) ใช้เวลาไปอีก 2 นาที  (total 6 mins)
ผูก Crazy(10 mins) กับ lazy(20 mins) นำทั้งคู่ข้ามสะพาน จะใช้เวลา 20 นาที (total 26 mins)
กลับมากับ Daisy(4mins) ใช้เวลา 4 นาที (total 30 mins)
ผูก Daisy(4mins ) กับ Mazie(2 mins) และนำข้ามสะพานใช้เวลา 4 นาที

เพราะฉะนั้นจะใช้เวลาทั้งหมด 34 นาที พอดี

ข้อถัดมาเป็นข้อR-7.2

Describe a good algorithm for concatenating two singly linked lists L and M, given only references to the first node of each list, into a single list L that contains all the nodes of L followed by all the nodes of M.

ป็นเรื่อง Singly Linked List คือการนำข้อมูลมาใส่ใน link list

อันนี้คือ ตัวอย่างการใช้ ฟังก์ชั่นแต่ละฟังก์ชั่นใน code

ข้อสุดท้ายข้อ C-7.41 Exercise C-5.29 introduces the notion of a natural join of two databases. Describe and analyze an efficient algorithm for computing the natural join of a linked list A of n pairs and a linked list B of m pairs.

เป็นการนำข้อ C-5.29 มาประยุกต์

และรูปด้านล่างคือ code ที่นำเรื่อง Doubly Linked Base มาเข้ากับ Linked Deque

รูปด้านล่างเป็นรูปตัวอย่างการใช้ Function จาก  Linked Deque

และ output  คือ

YouTube Preview Image

  •  
  •  
  •  
  •  
  •  
  •  
PATTANA PATTANASING
at GlurGeek.Com

Leave a Reply