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

180.183.159.37 เมื่อ 04:22, 28 กรกฎาคม 2553

2010-07-28T04:22:18Z

158.108.183.136 เมื่อ 09:49, 2 กันยายน 2552

2009-09-02T09:49:36Z

Aoy เมื่อ 08:55, 2 กันยายน 2552

2009-09-02T08:55:44Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ $A[.] \,$ ที่เรียงจากน้อยไปหามากแล้…'

2009-09-02T08:55:11Z

หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ <math> A[.] \, </math> ที่เรียงจากน้อยไปหามากแล้…'

หน้าใหม่

อินพุต: อะเรย์ <math> A[.] \, </math> ที่เรียงจากน้อยไปหามากแล้ว โดยที่ตัวเลขทุกตัวในอะเรย์มีค่าต่างกัน

เอาพุต: ตอบว่ามี ถ้ามี <math>A[i]=i \,</math> และไม่มีถ้ากรณีดังกล่าวไม่เป็นจริง

วัตถุที่เราต้องตรวจสอบคือ ตัวเลข <math>0,1,2,... \,</math> โดยที่เงื่อนไขคือ ตัวเลข <math>i \,</math> ที่อยู่ในช่วงดังกล่าวที่ทำให้ <math>A[i]=i \,</math> และโจทย์ต้องการให้เวลาการทำงานทั้งหมดเป็น <math>O(\log n)</math> ดังนั้นเราจะใช้ binary search ที่เรียนกันไปในห้องเรียน

เนื่องจากเราใช้ binary search เราต้องรู้ให้ได้ว่าเงื่อนไขสามเงื่อนไขที่ใช้ในการตรวจสอบคืออะไร

แน่นอนว่าเงื่อนไขในการหยุดคือ <math>A[i]=i \,</math> พิจารณากรณีที่ <math>A[i]< i \,</math> สมมติให้ <math>A[i]=x \,</math> เนื่องจากอะเรย์เรียงจากน้อยไปมากแล้ว ดังนั้นเมื่อพิจารณาอะเรย์ฝั่งซ้ายของตำแหน่งที่ <math> i \, </math> จะได้ <math>A[i-1]\leq x-1,A[i-2]\leq x-2,A[i-3]\leq x-3 \, </math> สำหรับ index <math>i-1, i-2, i-3, ...</math> ดังนั้นคำตอบ <math> i \, </math> ที่จะทำให้ <math>A[i]=i \,</math> จึงไม่อยู่ในฝั่งซ้ายนี้แน่นอน เพราะว่าค่าในอะเรย์ทุกค่าน้อยกว่า ค่า index มันหมดเลย ดังนั้นเราจึงควรไปค้นหาในฝั่งขวา และเมื่อพิจารณาแบบเดียวกันก็จะได้เงื่อนไขทั้งสามเงื่อนไขเป็นดังนี้

:เงื่อนไขหยุดคือ <math>A[i]=i \,</math>
:เงื่อนไขไปทางซ้ายคือ <math>A[i]>i \,</math>
:เงื่อนไขไปทางขวาคือ <math>A[i]<i \,</math>

เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้

FindI(a,b,e)
:if e<b
:: return -1
:else
:: i=(b+e)/2
:: if a[i] = i
::: return i
:: else if a[i] > i
::: retrun FindI(a,i,k-1)
:: else if a[i] < i
::: return FindI(a,k+1,j)

ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี

@@ แถว 21: / แถว 21: @@
      return -1
 else
-     i=(b+e)/2
+     k=(b+e)/2
-     if a[i] = i
+     if a[k] = k
-         return i
+         return k
-     else if a[i] > i
+     else if a[k] > k
-         retrun FindI(a,i,k-1)
+         retrun FindI(a,b,k-1)
-     else if a[i] < i
+     else if a[k] < k
-         return FindI(a,k+1,j)
+         return FindI(a,k+1,e)
+}
 </geshi>
 ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี

@@ แถว 15: / แถว 15: @@
 เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้
 FindI(a,b,e)
-:if e < b
-:: return -1
+if e < b
-:else
+    return -1
-:: i=(b+e)/2
+else
-:: if a[i] = i
+    i=(b+e)/2
-::: return i
+    if a[i] = i
-:: else if a[i] > i
+        return i
-::: retrun FindI(a,i,k-1)
+    else if a[i] > i
-:: else if a[i] < i
+        retrun FindI(a,i,k-1)
-::: return FindI(a,k+1,j)
+    else if a[i] < i
 ซึ่งเวลาการทำงานของอัลกอริทึมดังกล่าวก็จะเป็น <math> O(\log n) \,</math> เหมือน binary serach พอดี

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

180.183.159.37 เมื่อ 04:22, 28 กรกฎาคม 2553

158.108.183.136 เมื่อ 09:49, 2 กันยายน 2552

Aoy เมื่อ 08:55, 2 กันยายน 2552

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ A[.] \, ที่เรียงจากน้อยไปหามากแล้…'

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: อะเรย์ $A[.] \,$ ที่เรียงจากน้อยไปหามากแล้…'