ดูต้นฉบับสำหรับ 418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ

== ข้อ 1 ==
[ดัีดแปลงจาก Dasgupta, Papadimitriou, Vazirani 2.16] คุณได้รับอะเรย์ <math>A[\cdot] \,</math> ซึ่งมีจำนวนช่องเท่ากับจำนวนของจำนวนเต็มทั้งหมด (สมาชิกของอะเรย์นี้คือ <math>A[1], A[2], A[3], \ldots \,</math>) อะเรย์นี้มีคุณสมบัติว่าสมาชิก <math>n \,</math> ตัวแรกของมันจะมีค่าเท่ากับ 0 (กล่าวคือ <math>0 = A[1] = A[1] = \dotsb = A[n]\,</math>) โดยที่ <math>n \,</math> เป็นจำนวนเต็มหนึ่งตัว และสมาชิกที่เหลือมีค่าเท่ากับ 1 (กล่าวคือ <math>1 = A[n+1] = A[n+2] = A[n+3] = \dotsb \,</math>)

คุณไม่ทราบค่า <math>n \,</math> จงหาอัลกอริทึมที่หาค่า <math>n \,</math> ได้ในเวลา <math>O(\log n) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 1|เฉลย]]

== ข้อ 2 ==
[Dasgupta, Papadimitriou, Vazirani 2.17] กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่มีขนาด <math>n \,</math> ช่องที่เรียงจากน้อยไปหามาก นอกจากนี้เลขในอะเรย์ทุกตัวจะมีค่าไม่เท่ากัน คุณอยากจะทราบว่ามีจำนวนเต็ม <math>i \,</math> ที่ทำให้ <math>A[i] = i\,</math> หรือไม่ จงหาอัลกอริทึมที่สามารถหาค่า <math>i \,</math> ดังกล่าวมาหนึ่งค่าหรือตอบว่าไม่มีค่า <math>i \,</math> ดังกล่าวเลยได้ในเวลา <math>O(\log n) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 2|เฉลย]]

== ข้อ 3 ==
[Dasgupta, Papadimitriou, Vazirani 2.19] สมมติว่าคุณมีอะเรย์ที่เรียงแล้วอยู่ <math>k \,</math> อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ <math>n \,</math> ตัว คุณต้องการรวมอะเรย์ทั้งหมดเป็นอะเรย์ที่เรียงแล้วขนาด <math>kn \,</math> ช่อง
# นี่เป็นวิธีการหนึ่งที่คุณสามารถจะทำได้ ใช้อัลกอริทีม <code>merge</code> ที่เรียนไปในชั้นเรียนทำการรวมอะเรย์สองอะเรย์แรก เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สาม เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สี่ เช่นนี้ไปเรื่อยๆ วิธีการนี้มีเวลาการทำงานเป็นเท่าใดในรูปของ <math>n \,</math> และ <math>k \,</math>?
# จงออกอัลกอริทึมที่มีประสิทธิภาพกว่านี้โดยใช้เทคนิค divide and conquer

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 3|เฉลย]]

== ข้อ 4 ==
[Dasgupta, Papadimitriou, Vazirani 2.22] กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่เรียงแล้วขนาด <math>m \,</math> ช่อง และกำหนดอะเรย์ <math>B[\cdot] \,</math> ที่เรียงแล้วขนาด <math>n \,</math> ช่อง โดยที่ไม่มีจำนวนสองตัวใดๆ ในอะเรย์ทั้งสองตัวที่ซ้ำกัน จงออกแบบอัลกอริทึีมเพื่อหาสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ของเซตของตัวเลขที่เกิดจากการนำเอาตัวเลขในอะเรย์ทั้งสองตัวมารวมกัน อัลกอริทึีมของคุณควรจะทำงานได้ในเวลา <math>O(\log n + \log m) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4|เฉลย]]

== ข้อ 5 ==
ใำห้ <math>x \,</math> และ <math>k \,</math> เป็นจำนวนเต็มที่ไม่เป็นลบ จงออกแบบอัลกอริทึมเพื่อทำการคำนวณ <math>x^k \,</math> ซึ่งทำงานได้ในเวลา <math>O(\log k) \,</math> โดยสมมติว่าเราสามารถคูณเลขสองตัวได้ในเวลา <math>O(1) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5|เฉลย]]

== ข้อ 6 ==
เลขฟิโนนักชีมีนิยามดังต่อไปนี้
<math>f_n = \begin{cases}0 & n = 0 \\ 1 & n = 1 \\ f_{n-1} + f_{n-2} & n \geq 2 \end{cases} \,</math>
# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1}  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
# จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 6|เฉลย]]

== ข้อ 7 ==
พิจารณาปัญหาการหาลำดับย่อยที่มีผลบวกสูงสุด (ซึ่งเราเคยเรียนกันในชั้นเรียนแล้ว) ดังต่อไปนี้

กำหนดอะเรย์ <math>A[\cdot] \,</math> ขนาด <math>n \,</math> ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว เราต้องการหาลำดับย่อย <math>A[i], A[i+1], \ldots, A[j] \,</math> โดยที่ <math>1 \leq i \leq j \leq n \,</math> ที่ทำให้ <math>A[i] + A[i+1] + A[i+2] + \dotsb + A[j] \,</math> มีค่ามากที่สุด

จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา <math>O(n \log n) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7|เฉลย]]

== ข้อ 8 ==
[Kleinberg & Tardos 5.2] กำหนดอะเรย์ <math>A[.]</math> ขนาด <math>n \,</math> ช่อง นิยาม<b>อินเวอร์ชันสำััคัญ</b>ว่าเป็นคู่ลำดับ <math>(i,j)\,</math> ที่ <math>i < j \,</math> และ <math>A[i] > 2A[j] \,</math>

จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 8|เฉลย]]

== ข้อ 9 ==
[Kleinberg & Tardos 5.3] คุณให้คำปรึกษาธนาคารแห่งหนึ่งเกี่ยวกับการตรวจสอบการฉ้อโกง ขณะนี้ธนาคารมีปัญหาดังต่อไปนี้

ธนาคารได้ยึดบัตร ATM จำนวน <math>n \,</math> ใบมา บัตร ATM แต่ละใบจะมีหมายเลขบัญชีธนาคารฝังอยู่ในไมโครชิป โดยบัตรหลายๆ ใบอาจมีหมายเลขบัญชีธนาคารเดียวกันก็ได้ เรากล่าวว่าบัตร ATM สองใบใดๆ จะ<i>สมมูล</i>กันมันตรงกับบัญชีธนาคารเดียวกัน

การอ่านเลขบัญชีออกมาจากบัตร ATM เป็นเรื่องที่ทำยาก (สมมตินะครับ) แต่ธนาคารมีเครื่อง "ตรวจสอบความสมมูล" ที่คุณสามารถเอาบัตร ATM สองใบไปเสียบ แล้วมันจะบอกว่าบัตรสองใบนี้สมมูลกันหรือไม่

ธนาคารต้องการตอบคำถามต่อไปนี้: ในบัตร <math>n \,</math> ใบนี้ั มีกลุ่มของบัตรที่มีจำนวนมากกว่า <math>n/2 \,</math> สักกลุ่มหรือไม่ที่บัตรทุกใบในกลุ่มนี้สมมูลกันทั้งหมด?

สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น

[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9|เฉลย]]