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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 17: แถว 17:
 
     else
 
     else
 
         k=n/2
 
         k=n/2
         a0 <--- (a[0],a[1],...,a[k])
+
         al <--- (a[1],a[2],...,a[k])
         a1 <--- (a[k+1],a[k+2],...,a[n-1])
+
         ar <--- (a[k+1],a[k+2],...,a[n])
         x <--- Maxinterval(a0,k)
+
         x <--- Maxinterval(al,k)
         y <--- Maxinterval(a1,n-k)
+
         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>