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

Aoy เมื่อ 07:23, 8 กันยายน 2552

2009-09-08T07:23:50Z

Aoy เมื่อ 07:23, 8 กันยายน 2552

2009-09-08T07:23:17Z

Aoy เมื่อ 07:19, 8 กันยายน 2552

2009-09-08T07:19:49Z

แสดงการเปลี่ยนแปลง

158.108.238.178 เมื่อ 06:53, 8 กันยายน 2552

2009-09-08T06:53:29Z

Aoy เมื่อ 06:53, 7 กันยายน 2552

2009-09-07T06:53:25Z

Aoy เมื่อ 06:50, 7 กันยายน 2552

2009-09-07T06:50:04Z

Aoy เมื่อ 06:49, 7 กันยายน 2552

2009-09-07T06:49:00Z

Aoy เมื่อ 04:42, 6 กันยายน 2552

2009-09-06T04:42:08Z

Aoy เมื่อ 04:40, 6 กันยายน 2552

2009-09-06T04:40:03Z

Aoy เมื่อ 04:38, 6 กันยายน 2552

2009-09-06T04:38:22Z

@@ แถว 61: / แถว 61: @@
          al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
          ar <--- (a[k+1],a[k+2],...,a[n])
          (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
                  (iR,jR,mR) <--- Maxinterval(ar,n-k)
          (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
                  (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา

@@ แถว 7: / แถว 7: @@
 ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น <math> O(n \log n) \,</math> นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ <math>T(n)=2T(n/2)+O(n) \,</math> จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน <math> O(n) \, </math> เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ
 *'''DIVIDE:''' แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้  k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>)
@@ แถว 13: / แถว 16: @@
 *'''COMBINE:''' ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง <math> i \, </math> โดยที่ <math> 1 \leq i \leq k \,</math> และตำแหน่งสิ้นสุดของช่วง <math> j \, </math> โดยที่ <math> k+1 \leq j \leq n \,</math>
 คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ <math> A[k] \, </math> กับ  <math> A[k+1] \, </math> อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า <math> A[k] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ <math> A[k+1] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง

@@ แถว 19: / แถว 19: @@
          al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
          ar <--- (a[k+1],a[k+2],...,a[n])
          (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
-                (iR,jR,mR) <--- Maxinterval(ar,n-k)
+        (iR,jR,mR) <--- Maxinterval(ar,n-k)
          (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
                  (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา

@@ แถว 17: / แถว 17: @@
      else
          k=n/2
-         al <--- (a[1],a[2],...,a[k]) // เป็นปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
+         al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
          ar <--- (a[k+1],a[k+2],...,a[n])
-         (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกด้านซ้าย
+         (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
                  (iR,jR,mR) <--- Maxinterval(ar,n-k)
          (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
                  (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
-                 maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
+                 maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
-                 maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดระหว่างฝั่งซ้ายกับฝั่งขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
+                 maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
                  max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
                  if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา

@@ แถว 27: / แถว 27: @@
                  max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
                  if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา
-−
+                {
               if mL >= max then // และถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
-−
+                          {
                    i <--- iL  // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านซ้าย
-                  j <--- jL
+                                    j <--- jL
                    m <--- mL
               }else{          // ผลบวกมากสุดด้านซ้ายมากกว่าด้านขวา แต่น้อยกว่าผลบวกข้ามซ้ายขวา
-                  i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
+                                    i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
-                  j <--- maxj
+                                    j <--- maxj
                    m <--- max
+              }
          }else  // ถ้าผลบวกมากสุดด้านขวามากกว่าผลบวกมากสุดด้านซ้าย
-−
+               {
               if mR >= max then // และถ้าผลบวกมากสุดด้านขวามากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
-−
+                          {
                    i <--- iR // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านขวา
-                  j <--- jR
+                                    j <--- jR
                    m <--- mR
               }else{        // ผลบวกมากสุดด้านขวามากกว่าด้านซ้าย แต่น้อยกว่าผลบวกข้ามซ้ายขวา
-                  i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
+                                    i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
-                  j <--- maxj
+                                    j <--- maxj
                    m <--- max
+              }

@@ แถว 20: / แถว 20: @@
          ar <--- (a[k+1],a[k+2],...,a[n])
          x <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย
-        y <--- Maxinterval(ar,n-k)
+                y <--- Maxinterval(ar,n-k)
          L <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
                  R <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา

@@ แถว 17: / แถว 17: @@
      else
          k=n/2
-         al <--- (a[1],a[2],...,a[k])
+         al <--- (a[1],a[2],...,a[k]) // เป็นปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
          ar <--- (a[k+1],a[k+2],...,a[n])
-         x <--- Maxinterval(al,k)
+         x <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย
          y <--- Maxinterval(ar,n-k)
-         z <--- Interval(x,k,y,n-k)
+         L <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
 </geshi>
 <geshi lang="c">
-Interval(x,l,y,r)
+IntervalL(x,y,k)
-     for i=l down to 1
+     for i=k down to 1 // เวลาการทำงาน for loop นี้จะเป็น n/2
-         v=value(a,i,l)
+         v=value(a,i,k) // หาผลบวกของอะเรย์ตำแหน่งที่ i ถึง k
-         if v > max
+         if v > maxL // เก็บช่วงที่มีผลบวกมากสุดไว้
-             max = v
+             maxL = v
-             maxi=i
+             maxiL=i
-             maxj=l
+             maxjL=k
-    for j=r to n
+</geshi>
-         v=value(a,r,j)
-         if v > max
+<geshi lang="c">
-             max = v
+IntervalR(x,y,k)
-             maxi=r
+for j=k+1 to n  // for loop นี้อีก n/2
-             maxj=j
+         v=value(a,k+1,j)
 </geshi>