สวัสดีค่ะ ในส่วนของบทความนี้ผู้เขียนมีวัตถุประสงค์เพื่อให้ผู้อ่านที่มีความตั้งใจที่จะศึกษาหาความรู้ และทำความเข้าใจในเรื่องต่างๆ ของวิชา Data Structure รวมถึงหลักการ องค์ประกอบ และขั้นตอนการเขียนโปรแกรมในภาษาต่างๆเบื้องต้น เพื่อให้ผู้อ่านได้รับประโยชน์ในการเขียนโปรแกรมต่างๆทางด้านวิชาการในระดับอุดมศึกษา ซึ่งเป็นส่วนหนึ่งของการสําเร็จการศึกษา ดังจะกล่าวตามลําดับต่อไปนี้ เริ่มต้นกันด้วย ข้อ R-4.1
R-4.1 Describe a recursive algorithm for finding the minimum element in a sequence, S, of n elements. What is your running time and space usage?
แปลโจทย์ : ให้อธิบายขั้นตอนหรือวิธีการในเรื่องของ recursive ในการหาองค์ประกอบน้อยที่สุดในลำดับ S ขององค์ประกอบ n คุณใช้เวลาทำงานและการใช้พื้นที่อย่างไร
Code (C++)
หลักการทำงานของโปรแกรม
if หากมีองค์ประกอบภายในเพียงแค่ตัวเดียว return ค่านั้นกลับออกมา
else ให้ return ค่าที่น้อยที่สุดขององค์ประกอบที่ได้ติดตามทั้งหมดออกมา
Example
Input : A = {1, 4, 3, -5, -4, 8, 6};
Output : -5
————————————————————————————————————————————-
C-4.10 Describe a recursive algorithm to compute the integer part of the base-two logarithm of n using only addition and integer division.
แปลโจทย์ : ให้อธิบาย algorithm แบบทวนซ้ำ เพื่อคำนวณหาจำนวนเต็มส่วนหนึ่งของลอการิทึมฐานสองของ n โดยใช้การหารเฉพาะและจำนวนเต็มเท่านั้น
Code (Python)
หลักการทำงานของโปรแกรม
Logarithm จะเป็นการดำเนินการทางคณิตศาสตร์ที่เป็นฟังก์ชันผกผันของฟังก์ชันเลขชี้กำลัง ค่าลอการิทึมของจำนวนหนึ่งโดยกำหนดฐานไว้ให้ จะมีค่าเทียบเท่ากับการเอาฐานมายกกำลังค่าลอการิทึม ซึ่งจะให้คำตอบเป็นจำนวนนั้น ตัวอย่างเช่น
Example
- ลอการิทึมของ 1000 ในฐาน 10 มีค่าเป็น 3 เพราะว่า 10 คูณกัน 3 ตัว แล้วได้ 1000 นั่นคือ10 × 10 × 10 = 1000
- ลอการิทึมของ 32 ในฐาน 2 มีค่าเป็น 5 เพราะว่า 2 คูณกัน 5 ตัวแล้วได้ 32 นั่นคือ2 × 2 × 2 × 2 × 2 = 32
ถ้าเขียนด้วยสัญลักษณ์ยกกำลัง จะได้ว่า
- 103= 1000 ดังนั้น log10 1000 = 3
- 25= 32 ดังนั้น log2 32 = 5
————————————————————————————————————————————-
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.
แปลโจทย์ ใช้ class SubstitutionCipher กับตัวสร้างที่ใช้สตริงที่มีตัวพิมพ์ใหญ่ 26 ตัว ในลำดับที่สั่งโดย arbitrary order และใช้สำหรับการทำ mapping ล่วงหน้าสำหรับการเข้ารหัส (คล้ายๆกับอักขระ self._forward ใน class CaesarClass ของ code ส่วนที่ 5.11) คุณควรได้รับการ mapping ย้อนหลังจากการส่งต่อเวอร์ชัน
Code (Python)
หลักการทำงานของโปรแกรม
Shift cipher Caesar’s code หรือ Caesar shift เป็นเทคนิคการเข้ารหัสที่ง่ายและแพร่หลายที่สุด โดยใช้หลักการแทนที่ตัวอักษร ซึ่งในแต่ละตัวอักษรที่อยู่ในข้อความจะถูกแทนที่ด้วยตัวอักษรที่อยู่ลำดับถัดไปตามจำนวนตัวอักษรที่แน่นอน อย่างเช่น แปลงตัวอักษรไป 3 ตัว อักษร “A” ก็จะถูกแทนที่ด้วยอักษร “D”
Example
การแปลงสามารถแสดงด้วยการปรับแนวสองพยัญชนะ พยัญชนะรหัสเป็นพยัญชนะธรรมดาที่หมุนซ้ายหรือขวาบางตำแหน่ง ตัวอย่างเช่น ต่อไปนี้เป็นรหัสซีซาร์ที่ใช้การหมุนซ้ายสามตำแหน่ง เทียบเท่าหมุนขวา 23 ตำแหน่ง
ข้อความรหัส : ABCDEFGHIJKLMNOPQRSTUVWXYZ
รหัส : XYZABCDEFGHIJKLMNOPQRSTUVW
————————————————————————————————————————————-
R-6.6 Give a precise and complete definition of the concept of matching for grouping symbols in an arithmetic expression. Your definition may be recursive.
แปลโจทย์ : ให้คำนิยามที่ถูกต้องและครบถ้วนของแนวคิดการจับคู่สำหรับการจัดกลุ่มสัญลักษณ์ในนิพจน์เลขคณิต ความหมายของคุณอาจจะเป็น recursive
Code (Python)
หลักการทำงานของโปรแกรม
โปรแกรมนี้จะเป็นการเช็คความถูกต้องของสัญลักษณ์การจักกลุ่มทางคณิตศาสตร์ จะแยกออกเป็น 3 ประเภท ดังนี้ วงเล็บ (), วงเล็บปีกกา {}, วงเล็บเหลี่ยม [] โปรดสังเกตุว่าสัญลักษณ์ของการจัดกลุ่มนั้นไม่สามารถวางทับซ้อนกันได้ ซึ่งในทุกๆวงเล็บจะต้องมีคู่และวางถูกตำแหน่งเท่านั้นถึงจะถูกต้อง
Example
(A(B)} : false
{A(B)} : True
————————————————————————————————————————————-
C-6.29 In certain applications of the queue ADT, it is common to repeatedly dequeuer an element, process it in some way, and then immediately enqueuer the same element. Modify the ArrayQueue implementation to include a rotate () method that has semantics identical to the combination, Q.enqueue (Q.dequeue()). However, your implementation should be more efficient than making two separate calls (for example, because there is no need to modify _size).
แปลโจทย์ : ในบางโปรแกรมของ ADT เป็นเรื่องปกติที่องค์ประกอบของ dequeue ประมวลผลด้วยวิธีใดวิธีหนึ่ง และจากนั้นให้ใส่องค์ประกอบเดียวกันเพื่อปรับเปลี่ยนการดำเนินการ ArrayQueue เพื่อรวมวิธี rotate () ที่มีความหมายเหมือนกับการรวมกัน Q.enqueue (Q.dequeue()) อย่างไรก็ตามการใช้งานของคุณควรมีประสิทธิภาพมากกว่าการ calls แยกกันสองครั้ง (ตัวอย่างเช่น เนื่องจากไม่มีความจำเป็นต้องแก้ไขขนาด)
Code (Python)
หลักการทำงานของโปรแกรม
คิวเป็นคอนเทนเนอร์ของวัตถุ (คอลเล็กชันเชิงเส้น) ที่แทรกและนำออกตามหลักการแรกสุดก่อนออก (FIFO)
Example
คิวคือสายสีม่วง การเพิ่มใหม่กับเส้นที่ทำขึ้นที่ด้านหลังของคิวขณะที่การนำออกเกิดขึ้นที่ด้านหน้า ในคิวการดำเนินงานเพียงสองรายการเท่านั้นที่จะได้รับอนุญาตให้ใช้ enqueue และ dequeue Enqueue หมายถึงการแทรกรายการลงในด้านหลังของคิว ซึ่ง dequeue หมายถึงการนำรายการด้านหน้าออก ซึ่งความแตกต่างระหว่าง stack และ queue อยู่ในการลบ (stack เรานำรายการที่เพิ่มล่าสุด, queue เรานำรายการที่เพิ่งเพิ่มออกไป) รูปภาพแสดงถึงการเข้าถึง (FIFO)
————————————————————————————————————————————-
R-7.1 Give an algorithm for finding the second-to-last node in a singly linked list in which the last node is indicated by a next reference of None.
แปลโจทย์ : ให้อัลกอริทึมสำหรับการหาโหนดที่สองไปยังโหนดสุดท้ายใน singly linked list ซึ่งในโหนดสุดท้ายจะถูกระบุโดยการอ้างอิงตัวถัดไปของ None
Code (Python)
หลักการทำงานของโปรแกรม
ให้ linked list และ ตัวเลข n จำนวน เขียนฟังก์ชั่นที่ส่งคืนค่าที่โหนด n จากส่วนท้ายของlinked list
Example
ถ้า input อยู่ด้านล่าง list และ n = 3 ผลลัพธ์ก็คือ “B”
————————————————————————————————————————————-
C-7.28 Describe a fast recursive algorithm for reversing a singly linked list.
แปลโจทย์ : ให้อธิบายขั้นตอนวิธีการเรียกซ้ำแบบรวดเร็วสำหรับการย้อนกลับของ singly linked list.
Code (C)
หลักการทำงานของโปรแกรม
ผ่านหัวชี้ไปที่เป็นโหนด และทำการตรวจสอบว่าโหนดถัดไปของโหนดเป็น None หรือไม่ ถ้าใช่ แสดงว่าเราได้ไปถึงจุดสิ้นสุดของ linked list แล้ว ตั้งตัวหัวชี้ไปที่โหนดนี้ ถ้าไม่มีให้ส่งโหนดถัดไปของโหนดไปยัง reverse method เมื่อถึงโหนดสุดท้ายการ reverse จะเกิดขึ้น
Example
Given linked list
85 15 4 20
Reversed Linked list
20 4 15 85
————————————————————————————————————————————-
และนี่ก็คือคลิปอธิบายหลักการทำงานของโค้ดด้านบนแบบละเอียดนะคะ
สำหรับบทความนี้ ก็จบลงเพียงเท่านี้นะคะ พบกันใหม่โอกาสหน้า Final ค่ะ ขอบคุณค่ะ
