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

Cardcaptor: /* อัลกอริทึม */

2009-09-02T14:28:45Z

อัลกอริทึม

Cardcaptor: /* อัลกอริทึม */

2009-09-02T14:24:59Z

อัลกอริทึม

Cardcaptor: /* อัลกอริทึม */

2009-09-02T14:21:19Z

อัลกอริทึม

Cardcaptor: /* วัตถุ */

2009-09-02T14:19:05Z

วัตถุ

Cardcaptor: /* วัตถุ */

2009-09-02T14:12:47Z

วัตถุ

Cardcaptor: /* วัตถุ */

2009-09-02T14:12:36Z

วัตถุ

Cardcaptor เมื่อ 14:12, 2 กันยายน 2552

2009-09-02T14:12:24Z

Cardcaptor เมื่อ 14:09, 2 กันยายน 2552

2009-09-02T14:09:11Z

Cardcaptor เมื่อ 14:07, 2 กันยายน 2552

2009-09-02T14:07:21Z

Cardcaptor เมื่อ 14:06, 2 กันยายน 2552

2009-09-02T14:06:44Z

@@ แถว 39: / แถว 39: @@
 สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ <math>A[i+1] \,</math> กับ <math>B[j] \,</math> และ (2) เปรียบเทียบ <math>B[j+1] \,</math> กับ <math>A[i] \,</math> โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน
-# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราจะได้ว่าเราหา <math>(i,j) \,</math> ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้
+* <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราจะได้ว่าเราหา <math>(i,j) \,</math> ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้
-# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
-# <math>A[i+1] < B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' < i \,</math> เราจะได้ว่า <math>A[i'+1] < A[i+1] < B[j] < B[j'] \,</math> และ <math>B[j'+1] > B[j+1] > A[i] > A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' < i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
+* <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
 จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้
@@ แถว 65: / แถว 67: @@
+}
 </geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:24, 2 กันยายน 2552
แถว 42:		แถว 42:
	# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด		# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
	# <math>A[i+1] < B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' < i \,</math> เราจะได้ว่า <math>A[i'+1] < A[i+1] < B[j] < B[j'] \,</math> และ <math>B[j'+1] > B[j+1] > A[i] > A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' < i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด		# <math>A[i+1] < B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' < i \,</math> เราจะได้ว่า <math>A[i'+1] < A[i+1] < B[j] < B[j'] \,</math> และ <math>B[j'+1] > B[j+1] > A[i] > A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' < i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด
		+
		+	จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้
		+
		+	<geshi lang="c">
		+	Search(A, B, k)
		+	{
		+	i_left = 0
		+	i_right = k-1
		+
		+	while i_left <= i_right do
		+	{
		+	i = (i_left + i_right) / 2
		+	j = k - 1 - i
		+
		+	if A[i+1] > B[j] and B[j+1] > A[i] then
		+	return min(A[i+1], B[j+1])
		+	else if A[i+1] > B[j] and B[j+1] < A[i] then
		+	i_right = i-1
		+	else if A[i+1] < B[j] and B[j+1] > A[i] then
		+	i_left = i+1
		+	}
		+	}
		+	</geshi>

@@ แถว 40: / แถว 40: @@
 สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ <math>A[i+1] \,</math> กับ <math>B[j] \,</math> และ (2) เปรียบเทียบ <math>B[j+1] \,</math> กับ <math>A[i] \,</math> โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน
 # <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] > A[i] \,</math>: ในกรณีเราจะได้ว่าเราหา <math>(i,j) \,</math> ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้
-# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมดไป
+# <math>A[i+1] > B[j] \,</math> และ <math>B[j+1] < A[i] \,</math>: ในกรณีเราพบว่าสำหรับคู่ลำดับ <math>(i', j') \,</math> อื่นๆ ที่ <math>i' > i \,</math> เราจะได้ว่า <math>A[i'+1] > A[i+1] > B[j] > B[j'] \,</math> และ <math>B[j'+1] \leq B[j] < A[i] < A[i'] \,</math> ด้วยเหตุนี้ <math>(i',j') \,</math> จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ <math>k \,</math> ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ <math>(i',j') \,</math> โดยที่ <math>i' > i \,</math> ออกจากวัตถุที่เป็นไปได้ทั้งหมด

@@ แถว 35: / แถว 35: @@
 (ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี <math>i \,</math> และ <math>j \,</math> เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)
-== วัตถุ ==
+== อัลกอริทึม ==
 อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ <math>(i,j) \,</math> โดยที่ <math>i+j = k-1 \,</math> โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก <math>k \,</math> ตัวด้วยกัน ได้แต่ <math>(0,k-1), (1,k-2), (2,k-3), \ldots, (k-2,1), (k-1,0) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:12, 2 กันยายน 2552
แถว 36:		แถว 36:

	== วัตถุ ==		== วัตถุ ==
−	อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ <math>(i,j) \,</math> โดยที่ <math>i+j = k-1 \,</math> โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก <math>k \,</math> ตัวด้วยกัน ได้แต่ <math>(0,k-1), (1,k-2), (2,k-3), \ldots, (k-2,1), (k-1,0) \</math>	+	อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ <math>(i,j) \,</math> โดยที่ <math>i+j = k-1 \,</math> โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก <math>k \,</math> ตัวด้วยกัน ได้แต่ <math>(0,k-1), (1,k-2), (2,k-3), \ldots, (k-2,1), (k-1,0) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:12, 2 กันยายน 2552
แถว 34:		แถว 34:

	(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี <math>i \,</math> และ <math>j \,</math> เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)		(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี <math>i \,</math> และ <math>j \,</math> เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)
		+
		+	== วัตถุ ==
		+	อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ <math>(i,j) \,</math> โดยที่ <math>i+j = k-1 \</math> โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก <math>k \,</math> ตัวด้วยกัน ได้แต่ <math>(0,k-1), (1,k-2), (2,k-3), \ldots, (k-2,1), (k-1,0) \</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:09, 2 กันยายน 2552
แถว 32:		แถว 32:

	'''Proposition 4:''' เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> ได้โดยการหาจำนวนเต็ม <math>i \,</math> และ <math>j \,</math> ที่ทำให้ (1) <math>i+j = k-1 \,</math> และ (2) <math>A[i+1] > B[j] \,</math> และ (3) <math>B[j+1] > A[i] \,</math> แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math>		'''Proposition 4:''' เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> ได้โดยการหาจำนวนเต็ม <math>i \,</math> และ <math>j \,</math> ที่ทำให้ (1) <math>i+j = k-1 \,</math> และ (2) <math>A[i+1] > B[j] \,</math> และ (3) <math>B[j+1] > A[i] \,</math> แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math>
		+
		+	(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี <math>i \,</math> และ <math>j \,</math> เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:07, 2 กันยายน 2552
แถว 31:		แถว 31:
	สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า		สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า

−	'''Proposition 4:''' เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> ได้โดยการหาจำนวนเต็ม <math>i \,</math> และ <math>j \,</math> ที่ทำให้ (1) <math>i+j = k-1 \,</math> และ (2) <math>A[i+1] > B[j] \,</math> และ (3) </math>B[j+1] > A[i] \,</math>	+	'''Proposition 4:''' เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ <math>k \,</math> ในอะเรย์ <math>A \,</math> และ <math>B \,</math> ได้โดยการหาจำนวนเต็ม <math>i \,</math> และ <math>j \,</math> ที่ทำให้ (1) <math>i+j = k-1 \,</math> และ (2) <math>A[i+1] > B[j] \,</math> และ (3) <math>B[j+1] > A[i] \,</math> แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง <math>A[i+1] \,</math> และ <math>B[j+1] \,</math>

@@ แถว 1: / แถว 1: @@
 ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก
-เพื่อความสะดวก เราจะกำหนดให้อะเรย์ <math>A \,</math> และ <math>B \,</math> มีช่อง <math>A[0] \,</math> และ <math>B[0] \,</math> โดยที่ <math>A[0] = -\infty \,</math> และ <math>B[0] = -\infty \,</math> กล่าวคือ <math>A[0] \,</math> และ <math>B[0] \,</math> จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด
+เพื่อความสะดวก เราจะกำหนดให้อะเรย์ <math>A \,</math> และ <math>B \,</math> มีช่อง <math>A[0] \,</math> และ <math>B[0] \,</math> โดยที่ <math>A[0] = -\infty \,</math> และ <math>B[0] = -\infty \,</math> กล่าวคือ <math>A[0] \,</math> และ <math>B[0] \,</math> จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด แต่เราจะไม่นับว่าช่องที่เพิ่มมาใหม่นี้เป็นส่วนหนึ่งของอะเรย์
 เราจะพิสูจน์ข้อความสามข้อความต่อไปนี้
@@ แถว 27: / แถว 27: @@
 '''พิสูจน์:''' ใช้วิธีพิสูจน์เดียวกันกับ lemma 2