วันนี้ผู้เขียนจะขอนำโจทย์ในวิชา data structure มาอธิบายกันนะคะ ทั้งนี้ผู้อ่านควรมีความรู้พื้นฐานในรายวิชากันมาบ้างแล้ว แล้วจึงมาทำความเข้าใจโจทย์ประยุกต์เหล่านี้ ผู้เขียนหวังว่าบทความนี้จะมีประโยชน์ไม่มากก็น้อย มาเริ่มกันเลยค่ะ
R-4.4 Draw the recursion trace for the execution of function reverse(S, 0, 5) (Code Fragment 4.10) on S = [4, 3, 6, 2, 6].
แปลโจทย์ : จงวาดแผนผังของการทำงานฟังก์ชั่น reverse(S, 0, 5) (ใช้โค้ด 4.10) โดย S = [4, 3, 6, 2, 6]
Source Code
Output
Recursion Trace
โปรแกรมนี้ใช้สำหรับสลับค่าภายใน array จากหน้าไปหลัง กลายเป็นหลังมาหน้า โดยการทำงานเริ่มจากเรียก Reverse (S,0,5) โปรแกรมทำการตรวจสอบว่า input ที่จะทำการสลับมีค่าอย่างน้อย 2 ตัว จากนั้นสลับค่าแรกสุดและค่าหลังสุดโดยดูจาก parameter ตัวที่ 2 และ 3 เช่น (S,0,5) หมายความว่าตัวแรกที่จะสลับคือ S[0] และตัวสุดท้ายที่จะสลับด้วยคือ S[4] ดังนั้นค่า S จึงเปลี่ยนไปโดยเลข 6 และ 4 สลับที่กัน
หลังจากทำการสลับค่าในรอบแรกแล้ว โปรแกรมจะทำการเรียกตัวเองโดยเพิ่มค่าแรกสุดไป 1 และค่าท้ายสุดลดลง 1 กล่าวคือครั้งใหม่จะเรียก Reverse (S,1,4) เพื่อสลับค่า S[1] กับ S[3] หรือ 2 กับ 3 เมื่อสลับแล้วจะเรียก Reverse (S,2,3) โปรแกรมทำการตรวจสอบพบว่าค่าที่จะสลับมีค่าเดียวคือ S[2] จึงทำการจบโปรแกรม ได้ผลออกมา S = [6,2,6,3,4]
หมายเหตุ: S[0] หมายถึง index ที่ 0 ใน S ดังนั้น S มี 5 ค่า จะมีค่าตั้งแต่ S[0] จนถึง S[4]
C-4.19 Write a short recursive Python function that rearranges a sequence of integer values so that all the even values appear before all the odd values.
แปลโจทย์ : จงเขียนฟังก์ชั่นภาษา Python ที่ใช้สำหรับเรียงจำนวนเต็มใหม่ โดยให้เลขคู่ทั้งหมด อยู่หน้าเลขคี่
Source Code
Output
สร้างฟังก์ชั่นชื่อ rearrange โดยรับค่า I ซึ่งเป็นเซตของจำนวนเต็ม และ start ซึ่งเป็น index เริ่มต้นของข้อมูลที่ต้องการจะเรียง จากนั้นเข้า if ตัวแรกเพื่อตรวจสอบว่าตัวเลขที่ index start เป็นเลขคู่หรือไม่ หากไม่เป็นเลขคู่ให้เข้าลูปหาเลขคู่ตัวถัดไป แล้วทำการสลับค่าที่หาได้กับค่าที่ index start แล้วจึงหลุดออกจาก if ที่ตรวจสอบว่าเป็นเลขคู่หรือไม่ ไปทำการเรียกฟังก์ชั่นตัวเองและขยับ start ไปอีก 1 เนื่องจากค่า start เดิมเราได้ทำการเรียงแล้วใน I
อย่างในกรณีนี้ I = [1,2,8,3,0]
- ครั้งแรกโปรแกรมตรวจสอบพบว่า 1 เป็นเลขคี่ จึงทำการหาเลขคู่ตัวถัดไปซึ่งก็คือ 2 จากนั้นจึงสลับ 1 กับ 2
- ครั้งที่สอง start จะเป็น 1 คือตรวจสอบที่ 1 ซึ่งก็เป็นเลขคี่จึงสลับกับ 8 ที่เป็นเลขคู่ตัวถัดไป
- ครั้งที่สามตรวจสอบพบว่า 1 เป็นเลขคี่ สลับกับเลขคู่ตัวถัดไปคือ 0
- ครั้งที่สี่ตรวจสอบพบว่า 3 เป็นเลขคี่ แล้วไม่พบว่ามีเลขคู่ใดๆอีก จึงทำการจบโปรแกรม โดยสุดท้ายได้ผลลัพธ์เป็น I = [2, 8, 0, 3, 1]
P-5.35 Implement a class, SubstitutionCipher, with a constructor that takes a string with the 26 uppercase letters in an arbitrary order and uses that for the forward mapping for encryption (akin to the self. forward string in our CaesarCipher class of Code Fragment 5.11). You should derive the
backward mapping from the forward version.
แปลโจทย์ : จงเขียนคลาส SubstitutionCipher ที่จะทำการเข้ารหัสข้อความด้วยตัวอักษรพิมพ์ใหญ่ โดยให้กำหนด key หรือกุญแจ26 ตัว แล้วใช้ในการเข้ารหัส และถอดรหัส (คล้ายๆ กับในโค้ด 5.11)
Source Code
Output
ทำการสร้างคลาส SubstitutionCipher ขึ้นมา โดยภายในมีการประกาศตัวแปร 3 ตัว คือ
- alphabet คือตัวอักษรพิมพ์ใหญ่ภาษาอังกฤษทั้ง 26 ตัว เพราะเราจะเข้ารหัสตัวอักษรเหล่านี้
- key คือกุญแจที่เราจะใช้ ในการเข้ารหัสแบบ substitution cipher คือเข้ารหัสแบบเทียบตัวอักษร โดยจะเทียบ key กับ alphabet
- plaintext คือข้อความที่เราต้องการจะนำมาเข้า-ถอดรหัส
สร้างฟังก์ชั่นเข้ารหัสหรือ encrypt โดยรับข้อความ คีย์ และตัวอักษร A-Z เข้ามาเป็น input แล้วทำการเทียบตัวอักษร การทำงานจะเริ่มที่นำเอา alphabet ทุกตัวมาเทียบกับ key แล้วเข้าลูปเพื่อแทนค่า alphabet ใน paintext ทุกตัวให้กลายเป็นตัวที่เทียบมาจาก key เช่น ตัว A ใน plaintext จะถูกเทียบกับ alphabet ได้เป็น A แล้วจึงนำ A ไปเทียบกับ key ผลที่ได้หลังเข้ารหัสคือ A จะกลายเป็นตัว N แทน เป็นต้น
สร้างฟังก์ชั่นถอดรหัสหรือ decrypt โดยใช้หลักการเดียวกับการเข้ารหัสเพียงแต่เทียบกลับจากเดิมที่เทียบ alphabet กับ key ให้เทียบ key กับ alphabet เช่น รหัสที่ถูกเข้าเป็นตัว N ให้เข้าไปดูใน key ว่า N อยู่ตำแหน่งใดใน string แล้วจึงเอาไปเทียบที่ตำแหน่งเดียวกันใน alphabet ได้ผลออกมาเป็นตัว A
จากนั้นตั้งตัวแปร cipher เพื่อเป็นตัวแปรที่เก็บข้อความที่ถูกเข้ารหัส แล้วจึงทำการปริ้นผลลัพธ์ออกมา ในโปรแกรมนี้สามารถแก้ไข key และ plaintext ได้โดยที่ไม่ต้องแก้ฟังก์ชั่นก็ยังสามารถใช้งานได้
R-6.8 Suppose an initially empty queue Q has executed a total of 32 enqueue operations, 10 first operations, and 15 dequeue operations, 5 of which raised Empty errors that were caught and ignored. What is the current size of Q?
แปลโจทย์ : สมมติให้เริ่มต้นคิว Q เป็นคิวว่าง และถูกใส่ข้อมูลไป 32 ครั้ง, เรียกดูข้อมูลตัวแรก 10 ครั้ง, เอาข้อมูลออกจากคิว 15 ครั้ง โดย 5 ครั้งมีการแจ้งเตือนว่าคิวว่าง ไม่ต้องทำงาน ปัจจุบันขนาดของ Q คือเท่าไร
คิวถูกใส่ข้อมูลไป 32 ค่า → 0 + 32 = 32
ถูกเรียกดูข้อมูลขนาดของคิวจะไม่เปลี่ยนแปลง ดังนั้นยังคงเป็น 32
เอาข้อมูลออกจากคิว 15 ครั้ง แต่ error ไป 5 ครั้ง จึงเอาออกแค่ 10 ครั้ง ดังนั้นขนาดของคิวจะเหลือ 32 – 10 = 22
C-6.21 Show how to use a stack S and a queue Q to generate all possible subsets of an n-element set T nonrecursively.
แปลโจทย์ : จงแสดงว่าสามารถใช้ stack กับ queue ในการหาซับเซตทั้งหมดของเซต T ซึ่งมีสมาชิก n ตัว โดยไม่ใช่ recursive หรือฟังก์ชั่นเรียกตัวเอง
Source Code
Output
โปรแกรมนี้มีการประกาศคลาส ArrayStack โดยเริ่มจาก stack ว่างๆ มีฟังก์ชั่น
• len หาความยาวภายในอาร์เรย์หรือหาจำนวนข้อมูลใน stack
• is_empty ใช้หาว่าภายใน stack นั่นว่างหรือไม่ ตอบเป็น True หรือ False
• push ใช้ใส่ค่า parameter ของฟังก์ชั่นลงไปใน stack
• top มีการตรวจสอบว่าอาร์เรย์ว่างหรือไม่โดยใช้ is_empty ถ้าว่างพิมพ์กลับไป “Stack is empty” ถ้าไม่ ให้ส่งค่าตัวล่าสุดที่อยู่ใน stack กลับไป เป็นการรีเทิร์นค่าแบบ first in last out
• pop มีการตรวจสอบว่าอาร์เรย์ว่างหรือไม่โดยใช้ is_empty ถ้าว่างพิมพ์กลับไป “Stack is empty” ถ้าไม่ ให้ pop ค่าล่าสุดออกมา (ลบค่าภายในอาร์เรย์ด้วย ต่างจาก top ที่ดึงมาใช้แต่ไม่ลบค่าในอาร์เรย์)
สร้างคลาส ArrayQueue ให้เริ่มต้นเป็นคิวว่างๆ มีความจุ 10 มีข้อมูลภายใน 0 และชี้ตำแหน่งแรกสุด
• len รีเทิร์นจำนวนข้อมูลภายในคิว
• is_empty รีเทิร์น True or False ว่าจำนวนข้อมูลภายในเท่ากับ 0 หรือไม่
• first เริ่มที่เช็คว่าคิวว่างไหม ถ้าว่างบอก Queue is empty ถ้าไม่ให้รีเทิร์นค่าแรกสุดในคิว
• dequeue เริ่มที่เช็คว่าคิวว่างไหม ถ้าว่างบอก Queue is empty ถ้าไม่ให้รีเทิร์นค่าแรกสุดในคิว แล้วลบค่านั้นออกแทนด้วยค่าว่าง None จากนั้นเปลี่ยนตำแหน่งแรกของคิวเพิ่มไป 1 และ mod ด้วยความจุเพื่อไม่ให้ชี้เกินขนาดของคิว แล้วลบจำนวนข้อมูลไป 1 (เพราะเอาค่าออกไปแล้ว)
• enqueue เริ่มจากเช็คว่าคิวเต็มไห ถ้าเต็มเพิ่มความจุคิวไป 2 เท่า จากนั้นใส่ค่าใหม่เข้าไปที่ท้ายสุดของคิว เช็คโดยเอาตำแหน่งแรกสุดของคิว + จำนวนข้อมูล mod ด้วยความจุ แล้วบวกจำนวนข้อมูลไปอีก 1
• resize ใช้เพิ่มขนาดคิวให้เท่ากับค่า cap ที่รับเข้ามา ภายในฟังก์ชั่นมีการโอนข้อมูลเดิมของคิวไปใส่ในคิวใหม่ แล้วเปลี่ยนตำแหน่งต้นคิวเป็นตำแหน่งแรกสุดที่ 0
แล้วตามด้วย main ส่วนหลักของโปรแกรม
• สร้างเซต n มีสมาชิกเป็น 1 2 3 4 5
• สร้างตัวแปรประเภทที่เป็น ArrayStack และ ArrayQueue แล้วใช้คำสั่ง q.enqueue(set()) เพื่อใส่ค่าเซตว่าง { } ลงใน q
• pop ค่าใส่ลง stack (ใส่ค่าแรกลงไปล่างสุด ค่าสุดท้ายจะอยู่บนสุด)
• สร้างลูปตราบใดที่ stack ยังไม่ว่างให้ pop ค่าบนสุดออก ปริ้นค่านั้นๆ แล้วสร้าง for loop เท่ากับจำนวนสมาชิกในคิว ในลูปจะทำการเอาค่าในคิวออก (ค่าแรกสุด) ใส่ในตัวแปร a ปริ้นออกมา แล้วใส่ค่านั้นๆกลับไปท้ายคิว จากนั้นตรงตัวแปร b คือการ union กันของ a และค่าที่ถูก pop ออกมาจาก stack จากนั้นนำตัวแปร b ใส่ลงในคิว ปริ้นค่า b
• ลูปสุดท้ายคือการปริ้นค่าทั้งหมดภายในคิว ซึ่งคิวจะเก็บซับเซตทั้งหมดที่เป็นไปได้ของเซต n
ตัวอย่าง :
เริ่มลูป while อันแรก pop ค่าใน stack ออก ซึ่งก็คือ 5 (cur_el = 5) จากนั้นเข้าลูป for จะได้ว่า a = { } ซึ่งคือค่าในคิว ปริ้นแสดงผล แล้วนำค่า { } กลับเข้าไปในคิว ส่วน b จะเป็นการ union ของ { } และ {5} จึงได้ {5} ปริ้นแสดงผล แล้วนำค่าใส่เข้าคิว
จบลูปแรก q = { } {5}
วนครั้งที่สอง pop 4 ออกมา แล้ว a มีค่า { } และ b คือการนำ { } union 4 จะได้ {4} ปริ้นแสดงผล ใส่ค่าเข้าคิว
ปัจจุบัน q = {5} { } {4}
จากนั้นวนอีกรอบเพราะ len(q) = 2 (ก่อนจะมีการแก้ไขใดๆ) อีกรอบจะได้ a = {5} และ b = {5} union {4} = {4,5}
ทำเช่นนี้ไปจน cur เป็น 1 แล้วจึงหลุดลูปการคำนวนหา subset ไปเข้าลูปการปริ้นค่าภายในคิวเพื่อแสดง subset ทั้งหมด ผลที่ได้จะเป็นดังนี้
Output ( ต่อ )
R-7.19 Suppose that we have made kn total accesses to the elements in a list L of n elements, for some integer k ≥ 1. What are the minimum and maximum number of elements that have been accessed fewer than k times?
แปลโจทย์ : สมมติว่าเรามีการเข้าถึงข้อมูล kn ครั้งภายใน list ที่มี n สมาชิก โดย k เป็นเลขจำนวนเต็มที่มีค่ามากกว่าเท่ากับ 1 จำนวนสมาชิกที่เป็นไปได้มากสุดและน้อยที่สุดที่ถูกเข้าถึงข้อมูลน้อยกว่า k ครั้ง
- กรณีน้อยที่สุด : ถ้าข้อมูล n ค่าถูกเข้าถึงอย่างละครั้งทุกตัว จะมีการเข้าถึงข้อมูล kn ครั้ง โดย k จะเป็น 1 ดังนั้นจำนวนสมาชิกที่ถูกเข้าถึงข้อมูลน้อยกว่า k ครั้งจะเป็น 0 เพราะสมาชิกทุกตัวถูกเข้าถึงอย่างอย่างละ 1 ครั้ง ในขณะที่ k มีค่าเป็น 1
- กรณีมากที่สุด : ถ้าข้อมูล n ค่าแต่มีสมาชิกเพียงตัวเดียวที่ถูกเรียกใช้ สมาชิกที่เหลือถูกเข้าถึง 0 ครั้ง ดังนั้นสมาชิกที่ถูกเข้าถึงข้อมูลน้อยกว่า k จะเป็น n-1 (1 ตัวถูกเข้าถึงตลอด จึงมากกว่า k)
C-7.25 Give a complete implementation of the queue ADT using a singly linked list that includes a header sentinel.
แปลโจทย์ : จงสร้างคิวโดยใช้โครงสร้างข้อมูลแบบ linked list ซึ่งจะต้องประกอบไปด้วยหัวและท้ายของ list
Source Code
Output
สร้างคลาส Node เพื่อใช้ในการสร้าง linked list ภายในประกอบไปด้วยข้อมูลปัจจุบัน และ Node ก่อนหน้า และ Node ถัดจากตัวมันเอง ในตอนต้นมีแค่ตัวมันไม่มี Node อื่นมาเชื่อมต่อด้วย
สร้างคลาส Queue ประกอบไปด้วยฟังก์ชั่นดังนี้
- init จำกัดค่าเริ่มต้นขนาดของ list คือ 0 และไม่มี Node ใดๆต่ออยู่ใน list
- enqueue มี input เป็น x ซึ่งก็คือข้อมูลที่ต้องการจะนำเข้ามาในคิว ภายในฟังก์ชั่นจะเริ่มจากสร้าง Node ใหม่ที่มีข้อมูล x จากนั้นให้ Node ถัดจาก newNode ไม่มีค่า หรือก็คือไม่มี Node ต่อจากตัวมันเอง แล้วจึงเข้าตรวจสอบเงื่อนไขหากหัวของ list ไม่มีค่า (ไม่มีค่าใดๆในคิวอยู่เลย) ให้ใส่ค่าใหม่นี้เข้าไป และตัวมันเองจะเป็นทั้งต้นคิวและท้ายคิวเพราะมีค่าเดียว แต่หากในคิวมีค่าอื่นจะใช้ newNode ไปท้ายคิว และท้ายคิวใหม่จะถูกเปลี่ยนเป็น Node ใหม่ จากนั้นเพิ่มขนาดของคิวไปอีกหนึ่ง
- dequeue นำข้อมูลที่หัวคิวออก จากนั้นให้หัวคิวตัวใหม่เป็นตัวที่สองในคิวเดิม ลดขนาดของคิวไปอีกหนึ่ง แล้วรีเทิร์นค่าถูกที่นำออกกลับมา
- front อ่านค่าหัวของคิว (ไม่มีการลดหรือเพิ่มข้อมูลในคิว)
- size บอกขนาดของคิว
เมื่อสร้างคลาสแล้วก็ทดลองโปรแกรมโดยเริ่มจากประกาศตัวแปร q เป็นคลาส Queue แล้วทำการใส่ค่า 5 ลงในคิว ปริ้น front (ข้อมูลตัวแรก) ออกมา จากนั้นใส่ค่า 7 และ 2 ตามลำดับ ดังนั้นในคิวจะมีค่า 5 7 2 แล้วจึงทำการนำค่าออกจากคิว ค่า 5 จะถูกนำออก และในคิวจะเหลือ 7 2 ดังนั้นเมื่อเรียกข้อมูลตัวแรกจะได้ 7 และขนาดของคิวจะอยู่ที่ 2
สำหรับคนที่ต้องการชมวิดิโออธิบายสามารถรับชมได้ตามนี้ (มี 2 part)
