ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
แถว 17: | แถว 17: | ||
else | else | ||
k=n/2 | k=n/2 | ||
− | + | al <--- (a[1],a[2],...,a[k]) | |
− | + | ar <--- (a[k+1],a[k+2],...,a[n]) | |
− | x <--- Maxinterval( | + | x <--- Maxinterval(al,k) |
− | y <--- Maxinterval( | + | y <--- Maxinterval(ar,n-k) |
z <--- Interval(x,k,y,n-k) | z <--- Interval(x,k,y,n-k) | ||
+ | </geshi> | ||
+ | |||
+ | <geshi lang="c"> | ||
+ | Interval(x,l,y,r) | ||
+ | for i=l down to 1 | ||
+ | v=value(a,i,l) | ||
+ | if v > max | ||
+ | max = v | ||
+ | maxi=i | ||
+ | maxj=l | ||
+ | for j=r to n | ||
+ | v=value(a,r,j) | ||
+ | if v > max | ||
+ | max = v | ||
+ | maxi=r | ||
+ | maxj=j | ||
</geshi> | </geshi> |
รุ่นแก้ไขเมื่อ 04:22, 6 กันยายน 2552
อินพุต:อะเรย์ขนาด ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว
เอาพุต: คู่ลำดับ ที่ ที่ทำให้ มีค่ามากที่สุด
แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ ส่วนเงื่อนไขคือ คู่ลำดับ ดังกล่าวข้างต้นที่ ที่ทำให้ มีค่ามากที่สุด
ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ
คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่ม การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากทีสุดระหว่างสองกลุ่มนั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ กับ อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ ส่วนกลุ่มขวาเป็นอะเรย์ ) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดระหว่างสองกลุ่มนี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง
จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> Maxinterval(a,n)
if n= 1 return a else k=n/2 al <--- (a[1],a[2],...,a[k]) ar <--- (a[k+1],a[k+2],...,a[n]) x <--- Maxinterval(al,k) y <--- Maxinterval(ar,n-k) z <--- Interval(x,k,y,n-k)
</geshi>
<geshi lang="c"> Interval(x,l,y,r)
for i=l down to 1 v=value(a,i,l) if v > max max = v maxi=i maxj=l for j=r to n v=value(a,r,j) if v > max max = v maxi=r maxj=j
</geshi>