418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 3 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 09:25, 4 กันยายน 2552

2009-09-04T09:25:25Z

Aoy เมื่อ 09:24, 4 กันยายน 2552

2009-09-04T09:24:42Z

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

2009-09-02T07:08:47Z

Aoy: /* ข้อย่อย 2 */

2009-09-02T07:08:19Z

ข้อย่อย 2

Aoy เมื่อ 06:58, 2 กันยายน 2552

2009-09-02T06:58:31Z

Aoy เมื่อ 06:47, 2 กันยายน 2552

2009-09-02T06:47:13Z

Aoy เมื่อ 05:15, 24 สิงหาคม 2552

2009-08-24T05:15:07Z

Aoy เมื่อ 05:14, 24 สิงหาคม 2552

2009-08-24T05:14:05Z

Aoy เมื่อ 05:13, 24 สิงหาคม 2552

2009-08-24T05:13:41Z

Aoy เมื่อ 05:13, 24 สิงหาคม 2552

2009-08-24T05:13:23Z

@@ แถว 42: / แถว 42: @@
+      }
+}
 ซึ่งเราจะได้ว่าเวลาการทำงานของอัลกอริทึมข้างต้นคือเวลาที่ใช้ในการเรียง A ก่อนหน้านี้ กับเวลาที่สมาชิกในแต่ละตัวตรวจสอบกับสมาชิกตัวถัดไปอีกสองตัว ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(f(n)+ n)\,</math>

@@ แถว 8: / แถว 8: @@
 จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ (ให้ค่า l=3)
 GENERATE(n,l)
-:if l=0
-:: if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
+    if l=0
-::: then return 1
-:: else
+          if c[0] + c[1] > c[2] then // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
-::: return 0
+                             return 1
-:else
+          else
-:: for c[l-1] = l to n
+              return 0
-::: GENERATE(c[l-1]-1,l-1)
+    }else{
 เวลาการทำงานของอัลกอริทึมข้างต้น คือเวลาที่ใช้ในการคำนวณหา combination ที่มีสมาชิก 3 ตัว คือ <math>{n \choose 3}= \Theta(n^3) \,</math> นั่นเอง
@@ แถว 25: / แถว 31: @@
 ซึ่งจากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้
 GENERATE(A)
-:for i=0 to i < n
-:: if A[i] + A[i+1] > A[i+2]
+     for i=0 to i < n
-::: return 1
-:: else
+         if A[i] + A[i+1] > A[i+2]
-::: return 0
+              return 1
 ซึ่งเราจะได้ว่าเวลาการทำงานของอัลกอริทึมข้างต้นคือเวลาที่ใช้ในการเรียง A ก่อนหน้านี้ กับเวลาที่สมาชิกในแต่ละตัวตรวจสอบกับสมาชิกตัวถัดไปอีกสองตัว ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(f(n)+ n)\,</math>

@@ แถว 8: / แถว 8: @@
 จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ (ให้ค่า l=3)
-GENERATE(m,l)
+GENERATE(n,l)
 :if l=0
 :: if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
@@ แถว 15: / แถว 15: @@
 ::: return 0
 :else
-:: for c[l-1] = l to m
+:: for c[l-1] = l to n
 ::: GENERATE(c[l-1]-1,l-1)

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

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
		+	สังเกตว่าถ้าเราเรียงจำนวนที่อยู่ใน A ได้แล้ว พิจารณาจำนวน <math>a \in A \,</math> เราจะทำการตรวจสอบจำนวนที่ติดกับ <math>a \,</math> ไปทางขวาอีกแค่สองตัวเท่านั้น (นั่นคือจำนวน <math>b,c \,</math> จะอยู่ทางขวาของ a ไปอีกสองตำแหน่ง) ตามเงื่อนไข <math>a < b < c \,</math> เพราะจำนวนถัดไปจำนวนที่สาม ตรวจสอบไปก็ไม่เกิดประโยชน์ ดังนั้นการเรียงจำนวนที่อยู่ใน A ก่อนจะทำให้เราลดจำนวนวัตถุที่เราต้องพิจารณาลงไปได้
		+
		+	ซึ่งจากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	GENERATE(A)
		+	:for i=0 to i < n
		+	:: if A[i] + A[i+1] > A[i+2]
		+	::: return 1
		+	:: else
		+	::: return 0
		+
		+	ซึ่งเราจะได้ว่าเวลาการทำงานของอัลกอริทึมข้างต้นคือเวลาที่ใช้ในการเรียง A ก่อนหน้านี้ กับเวลาที่สมาชิกในแต่ละตัวตรวจสอบกับสมาชิกตัวถัดไปอีกสองตัว ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(f(n)+ n)\,</math>

@@ แถว 1: / แถว 1: @@
 อินพุต: เซตของจำนวนเต็ม <math>A \,</math> ที่มีสมาชิกอยู่ <math>n \,</math> ตัว
@@ แถว 5: / แถว 6: @@
 แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง  ๆ คือ <math>a+b > c \,</math> หรือไม่
-จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้
+จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ (ให้ค่า l=3)
 GENERATE(m,l)
 :if l=0
-::
+:: if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
 :else
-:: for c[l-1] =3 to m
+:: for c[l-1] = l to m
 ::: GENERATE(c[l-1]-1,l-1)

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

	จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้		จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	GENERATE(m,l)
		+	:if l=0
		+	::
		+	:else
		+	:: for c[l-1] =3 to m
		+	::: GENERATE(c[l-1]-1,l-1)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:15, 24 สิงหาคม 2552
แถว 4:		แถว 4:

	แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่		แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่
		+
		+	จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:14, 24 สิงหาคม 2552
แถว 4:		แถว 4:

	แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่		แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่
−
−	~~เวลาการทำงานของอัลกอริทึมดังกล่าวคือ <math>{n \choose 3}=O(n^3)</math>~~

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:13, 24 สิงหาคม 2552
แถว 5:		แถว 5:
	แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่		แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่

−	เวลาการทำงานของอัลกอริทึมดังกล่าวคือ <math>{n \choose 3}</math>	+	เวลาการทำงานของอัลกอริทึมดังกล่าวคือ <math>{n \choose 3}=O(n^3)</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:13, 24 สิงหาคม 2552
แถว 3:		แถว 3:
	เอาพุต: มีจำนวนเต็ม <math>a,b,c \in A \,</math> โดยที่ <math>a < b< c \,</math> และ <math>a+b > c \,</math> หรือไม่		เอาพุต: มีจำนวนเต็ม <math>a,b,c \in A \,</math> โดยที่ <math>a < b< c \,</math> และ <math>a+b > c \,</math> หรือไม่

−	แนวคิด	+	แนวคิด วัตถุที่เราต้องพิจารณาคือ จำนวนเต็ม 3 ตัวจาก จำนวนเต็มทั้งหมด <math>n \,</math> ตัว ซึ่งในห้องเรียน เราได้เรียนวิธีในการหยิบของ <math>k \,</math> สิ่ง จากของทั้งหมด <math>n \,</math> สิ่งมาแล้ว ในเรื่องของ combination นั่นเอง เราจะใช้วิธีนั้นกัน ส่วนเงื่อนไขในข้อนี้คือ จำนวนเต็ม <math>a,b,c \,</math>สามตัวที่เลือกมานั้น ต้องมีคุณสมบัติว่า <math>a < b< c \,</math> ซึ่งถ้าเลือกตามวิธีในห้องเรียน ก็จะมีคุณสมบัติดังกล่าวอยู่แล้ว ดังนั้นเงื่อนไขที่ต้องตรวจสอบจริง ๆ คือ <math>a+b > c \,</math> หรือไม่
		+
		+	เวลาการทำงานของอัลกอริทึมดังกล่าวคือ <math>{n \choose 3}</math>