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

Aoy เมื่อ 07:39, 4 กันยายน 2552

2009-09-04T07:39:54Z

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

2009-09-02T08:36:46Z

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

2009-09-02T08:26:48Z

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

2009-09-02T08:17:03Z

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

2009-09-02T08:14:31Z

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

2009-09-02T08:13:53Z

Aoy เมื่อ 07:45, 2 กันยายน 2552

2009-09-02T07:45:55Z

Aoy เมื่อ 07:43, 2 กันยายน 2552

2009-09-02T07:43:54Z

Aoy เมื่อ 07:42, 2 กันยายน 2552

2009-09-02T07:42:47Z

Aoy เมื่อ 07:41, 2 กันยายน 2552

2009-09-02T07:41:54Z

@@ แถว 14: / แถว 14: @@
 เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ (รอบแรกของการทำงานให้ ให้ j=1)
 FindInterval(a,j)
-:if j<0
+    if j<0
-:: return -1
+        return -1
-:else
+    else
-:: k = 2^j
+        k = 2^j
-:: if a[k]=0 and a[k+1]=1
+    if a[k]=0 and a[k+1]=1
-::: return k
+        return k
-:: else if a[k]=1 and a[k+1]=1
+    else if a[k]=1 and a[k+1]=1
-::: return FindN(a,2^(j-1),2^j) // ได้ช่วงจำกัดที่ต้องการมาแล้ว
+        return FindN(a,2^(j-1),2^j) // ได้ช่วงจำกัดที่ต้องการมาแล้ว
-:: else if a[k]= 0 and a[k+1]=0
+        else if a[k]= 0 and a[k+1]=0
-::: return FindInterval(a,j+1) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา
+        return FindInterval(a,j+1) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา
 FindN(a,i,j)
-: if j<i
+    if j<i
-::return -1
+        return -1
-: else
+    else
-:: k = (i+j)/2
+        k = (i+j)/2
-:: if a[k]=0 and a[k+1]=1
+    if a[k]=0 and a[k+1]=1
-::: return k
+        return k
-:: else if a[k]=1 and a[k+1]=1
+    else if a[k]=1 and a[k+1]=1
-::: return FindN(a,i,k-1)
+        return FindN(a,i,k-1)
-:: else if a[k]= 0 and a[k+1]=0
+    else if a[k]= 0 and a[k+1]=0
-::: return FindN(a,k+1,j)
+        return FindN(a,k+1,j)
 เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ

@@ แถว 5: / แถว 5: @@
 วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า <math> n \, </math> จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า <math> n \, </math> ดังกล่าวเป็น <math>O(\log n) \,</math> จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว
-วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้เป็นศูนย์หรือไม่ ตำแหน่งดังกล่าวคือ <math>2^1, 2^2,2^3,...,2^j</math> การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการค้นหาอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ binary search อีกทีว่าค่าที่ต้องการอยู่ตรงไหน
+วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้  <math>2^1, 2^2,2^3,...,2^j \,</math> เป็นศูนย์หรือไม่ การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ binary search อีกทีว่าค่าที่ต้องการอยู่ตรงไหน
 จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้
@@ แถว 22: / แถว 22: @@
 ::: return k
 :: else if a[k]=1 and a[k+1]=1
-::: return FindN(a,2^(j-1),2^j)
+::: return FindN(a,2^(j-1),2^j) // ได้ช่วงจำกัดที่ต้องการมาแล้ว
 :: else if a[k]= 0 and a[k+1]=0
-::: return FindInterval(a,j+1)
+::: return FindInterval(a,j+1) // วิ่งไปหาช่วงต่อไปในอะเรย์ด้านขวา
 FindN(a,i,j)
@@ แถว 34: / แถว 34: @@
 ::: return k
 :: else if a[k]=1 and a[k+1]=1
 ::: return FindN(a,k+1,j)
 เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ

@@ แถว 1: / แถว 1: @@
-อินพุต: อะเรย์ <math>A[.] \,</math> ที่มีขนาดเป็น infinity ที่มีคุณสมบัติคือสมาชิกชิก <math> n \, </math> ตัวแรกมีค่าเป็นศูนย์ นอกนั้นมีค่าเป็นหนึ่ง
+อินพุต: อะเรย์ <math>A[.] \,</math> ที่มีขนาดเป็น infinity ที่มีคุณสมบัติคือสมาชิก <math> n \, </math> ตัวแรกมีค่าเป็นศูนย์ นอกนั้นมีค่าเป็นหนึ่ง
 เอาพุต: ค่า <math> n \, </math>
@@ แถว 5: / แถว 5: @@
 วัตถุ ที่เราต้องทำการตรวจสอบในข้อนี้คือ ตัวเลข 1,2,3,... (หรือ index ของอะเรย์นั่นเอง) ซึ่ง ค่า <math> n \, </math> จะเป็นค่าที่อยู่ในช่วงดังกล่าว และมีเงื่อนไขคือ A[0]ถึง A[n]มีค่าเป็นศูนย์ และ A[n+1] เป็นต้นไปมีค่าเป็นหนึ่ง (เขียนสั้น ๆ คือ A[n]=0 และ A[n+1]=1) แต่โจทย์ต้องการให้เวลาในการหาค่า <math> n \, </math> ดังกล่าวเป็น <math>O(\log n) \,</math> จากการตัวอย่างการค้นหาในห้องเรียน เราได้เรียน binary search ไปแล้ว เราจะใช้วิธีดังกล่าว
-วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้เป็นศูนย์หรือไม่ ตำแหน่งดังกล่าวคือ <math>2^1, 2^2,2^3,...,2^j</math> จากในห้องเรียนเราได้เห็นแล้วว่าเงื่อนไขของ binary search มีสามเงื่อนไขคือ หยุด ไปทางซ้าย และไปทางขวา สำหรับข้อนี้เงื่อนไขเหล่านี้จะเป็นดังนี้
+วิธีการค้นหาจะทำดังนี้ ให้เริ่มค้นหาก่อนว่าค่าของอะเรย์ในตำแหน่งต่อไปนี้เป็นศูนย์หรือไม่ ตำแหน่งดังกล่าวคือ <math>2^1, 2^2,2^3,...,2^j</math> การค้นหาดังกล่าวทำเพื่อที่จะจำกัดช่วงของคำตอบว่าค่าที่ต้องการค้นหาอยู่ในช่วงไหนกันแน่ เพราะจากโจทย์ขนาดของอะเรย์ที่เป็นอินพุตมีขนาดไม่จำกัด ดังนั้นการหาค่ากลางจะทำไม่ได้ พอได้ช่วงของคำตอบที่เป็นไปได้ที่เป็นช่วงจำกัดมา เราจึงทำการหาแบบ binary search อีกทีว่าค่าที่ต้องการอยู่ตรงไหน
 :เงื่อนไขหยุด คือ A[k]=0 and A[k+1]=1
 :เงื่อนไขไปทางซ้ายคือ A[k]=1 and A[k+1]=1 // แสดงว่าวิ่งเกินมาทางขวาเกินไปแล้ว คำตอบต้องอยู่ทางซ้ายแน่นอน

@@ แถว 12: / แถว 12: @@
 เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ (รอบแรกของการทำงานให้ ให้ j=1)
-FindN(a,j)
+FindInterval(a,j)
 :if j<0
 :: return -1
@@ แถว 20: / แถว 20: @@
 ::: return k
 :: else if a[k]=1 and a[k+1]=1
-::: return FindInSmallInterval(a,2^(j-1),2^j)
+::: return FindN(a,2^(j-1),2^j)
 :: else if a[k]= 0 and a[k+1]=0
-::: return FindN(a,j+1)
+::: return FindInterval(a,j+1)
-FindInSmallInterval(a,i,j)
+FindN(a,i,j)
 : if j<i
 ::return -1
@@ แถว 32: / แถว 32: @@
 ::: return k
 :: else if a[k]=1 and a[k+1]=1
-::: return FindInSmallInterval(a,k+1,j)
+::: return FindN(a,k+1,j)
 :: else if a[k]= 0 and a[k+1]=0
-::: return FindInSmallInterval(a,i,k-1)
+::: return FindN(a,i,k-1)
-เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInSmallInterval ซึ่ง FindN จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindInSmallInterval จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ
+เวลาการทำงานของอัลกอริทึมจะแบ่งออกเป็นการค้นหาใน FindN และการค้นหาใน FindInterval ซึ่ง FindInterval จะหยุดทำเมื่อค่า <math> n \leq 2^j < 2n \,</math> ซึ่งจะทำงานทั้งหมด <math> j \, </math> รอบ ส่วน FindN จะทำการหาค่า <math> n\, </math> ในช่วงย่อยที่อยู่ระหว่างค่าศูนย์กับหนึ่งแล้ว ซึ่งทำงานทั้งหมด <math> O(\log 2^j)=O(\log n) \,</math> รอบ ดังนั้นเวลาการทำงานทั้งหมดจะเป็น <math> j+O(\log n)=O(\log n) </math> รอบ

@@ แถว 10: / แถว 10: @@
 :เงื่อนไขไปทางขวาคือ A[k]=0 and A[k+1]=0 // แสดงว่าวิ่งยังไม่ถึงคำตอบ วิ่งช้าไป คำตอบต้องอยู่ทางขวาแน่นอน
-เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้
+เมื่อนำแนวคิดดังกล่าวมาเขียนเป็น pseudocode จะได้ดังนี้ (รอบแรกของการทำงานให้ ให้ j=1)
 FindN(a,j)
 :if j<0

@@ แถว 22: / แถว 22: @@
 ::: else if a[k]=1 and a[k+1]=1
 :::: return FindN(a,i,k-1)
-::: else
+::: else if a[k]= 0 and a[k+1]=0
 :::: return FindN(a,k+1,j)
 เวลาการทำงานของอัลกอริทึมคือ จะทำทั้งหมด <math> 2^j \, </math> รอบ โดยที่เรารู้ว่า <math> n \leq 2^j < 2n \, </math> ดังนั้นเวลาการทำงานคือ <math> O(2^j)=O(\log n) \,</math> นั่นเอง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:42, 2 กันยายน 2552
แถว 25:		แถว 25:
	:::: return FindN(a,k+1,j)		:::: return FindN(a,k+1,j)

−	เวลาการทำงานของอัลกอริทึมคือ จะทำทั้งหมด <math> 2^j \, </math> รอบ โดยที่เรารู้ว่า <math> n \leq 2^j < 2n \, </math> ดังนั้นเวลาการทำงานคือ <math> O(2^j)=O(log n)</math> นั่นเอง	+	เวลาการทำงานของอัลกอริทึมคือ จะทำทั้งหมด <math> 2^j \, </math> รอบ โดยที่เรารู้ว่า <math> n \leq 2^j < 2n \, </math> ดังนั้นเวลาการทำงานคือ <math> O(2^j)=O(\log n)</math> นั่นเอง