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

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

2009-09-04T09:30:39Z

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

2009-09-02T06:54:01Z

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

2009-09-02T06:51:03Z

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

2009-08-18T07:37:01Z

ข้อย่อย 2

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

2009-08-18T07:36:31Z

ข้อย่อย 2

Aoy เมื่อ 07:35, 18 สิงหาคม 2552

2009-08-18T07:35:59Z

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

2009-08-18T07:29:32Z

ข้อย่อย 2

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

2009-08-18T07:22:59Z

ข้อย่อย 1

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

2009-08-18T07:13:52Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: เซตของจำนวนเต็ม $A \,$ ซึ่งมีสมาชิกอยู่
2009-08-18T07:11:02Z

หน้าที่ถูกสร้างด้วย 'อินพุต: เซตของจำนวนเต็ม <math>A \,</math> ซึ่งมีสมาชิกอยู่ <math…'

หน้าใหม่
อินพุต: เซตของจำนวนเต็ม <math>A \,</math> ซึ่งมีสมาชิกอยู่ <math>n \,</math> ตัว และจำนวนเต็ม <math>x \,</math>

เอาพุต: มีคู่ของจำนวนเต็ม <math>a, b \in A \,</math> ที่ <math>a < b, a+b =x \,</math> อยู่กี่คู่

แนวคิด จากโจทย์ เราต้องการหาคู่ของจำนวนเต็ม <math>a,b \in A \,</math> ที่ <math>a < b, a+b =x \,</math> ซึ่งในห้องเรียนเราได้รู้วิธีการหา combination มาแล้ว ซึ่งข้อนี้ก็คือการหาซับเซตของ <math>A \,</math> ที่มีขนาด 2 ที่ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x ว่ามีทั้งหมดกี่คู่นั่นเอง

@@ แถว 10: / แถว 10: @@
 ตัวแปรทุกอย่างขออ้างอิงจากในห้องเรียน โดยที่ข้อนี้ให้ l = 2
 COUNT(c,x)
 GENERARTE(m,l)
-−
+{
-: if l = 0
+    if l = 0
+         return(COUNT(c,x))
-:: return(COUNT(c,x))
+    else{
+         for c[l-1]=l to m
-: else
+             GENERATE(c[l-1]-1,l-1)
-−
+    }
-:: for c[l-1]=l to m
+</geshi>
 == ข้อย่อย 2 ==
@@ แถว 38: / แถว 39: @@
 เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>
 GENERATE(A,x,n)
-:count <-- 0
-: for i=0 to n-1
+     count <-- 0
-:: if (EXIST(x-A[i]))
+     for i=0 to n-1
-::: count <-- count + 1
-: return (count)
+         if (EXIST(x-A[i]))

@@ แถว 28: / แถว 28: @@
 : else
-:: for c[l-1]=0 to c[l-1] = 2
+:: for c[l-1]=l to m
 ::: GENERATE(c[l-1]-1,l-1)

@@ แถว 20: / แถว 20: @@
 :return(count)
-GENERARTE(m,x)
+GENERARTE(m,l)
 : if l = 0

@@ แถว 36: / แถว 36: @@
 แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม  <math>a \in A \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
-เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราก็จะทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>
+เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>
 GENERATE(A,x,n)

@@ แถว 35: / แถว 35: @@
 อินพุต เอาพุตยังเหมือนข้อย่อย 1
-แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม  <math>x \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
+แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม  <math>a \in A \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
 เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราก็จะทำงานได้ในเวลา <math>O(n.f(n)) \,</math> ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม <math> b \,</math> มีอยู่ในเซต <math> A \, </math> หรือไม่ และใช้เวลาทำงานเป็น  <math>O(f(n)) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:35, 18 สิงหาคม 2552
แถว 36:		แถว 36:

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:29, 18 สิงหาคม 2552
แถว 33:		แถว 33:

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
		+	อินพุต เอาพุตยังเหมือนข้อย่อย 1
		+
		+	แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ <math>a + b =x \,</math> นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม <math>x \,</math> ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม <math>b \,</math> ซึ่งเท่ากับ <math>x-a \,</math> นั้นมีอยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา<math>O(f(n)) \,</math>
		+	เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราก็จะทำงานได้ในเวลา <math>O(n.f(n)) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:22, 18 สิงหาคม 2552
แถว 7:		แถว 7:

	จากแนวคิดข้างต้น เมื่อเขียนเป็น pseudocode จะได้ดังนี้		จากแนวคิดข้างต้น เมื่อเขียนเป็น pseudocode จะได้ดังนี้
		+
		+	ตัวแปรทุกอย่างขออ้างอิงจากในห้องเรียน โดยที่ข้อนี้ให้ l = 2
		+
		+	COUNT(c,x)
		+
		+	: count <-- 0
		+
		+	:if(c[0]+c[1]= x)
		+
		+	:: count <-- count + 1
		+
		+	:return(count)
		+
		+	GENERARTE(m,x)
		+
		+	: if l = 0
		+
		+	:: return(COUNT(c,x))
		+
		+	: else
		+
		+	:: for c[l-1]=0 to c[l-1] = 2
		+
		+	::: GENERATE(c[l-1]-1,l-1)

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==

@@ แถว 1: / แถว 1: @@
 อินพุต: เซตของจำนวนเต็ม <math>A \,</math> ซึ่งมีสมาชิกอยู่ <math>n \,</math> ตัว และจำนวนเต็ม <math>x \,</math>
 เอาพุต: มีคู่ของจำนวนเต็ม <math>a, b \in A \,</math> ที่ <math>a < b, a+b =x \,</math> อยู่กี่คู่
-แนวคิด จากโจทย์ เราต้องการหาคู่ของจำนวนเต็ม <math>a,b \in A \,</math> ที่ <math>a < b, a+b =x \,</math> ซึ่งในห้องเรียนเราได้รู้วิธีการหา combination มาแล้ว ซึ่งข้อนี้ก็คือการหาซับเซตของ <math>A \,</math> ที่มีขนาด 2 ที่ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x ว่ามีทั้งหมดกี่คู่นั่นเอง
+แนวคิด จากโจทย์ เราต้องการหาคู่ของจำนวนเต็ม <math>a,b \in A \,</math> ที่ <math>a < b, a+b =x \,</math> ซึ่งในห้องเรียนเราได้รู้วิธีการหา combination มาแล้ว ซึ่งข้อนี้ก็คือการหาซับเซตของ <math>A \,</math> ที่มีขนาด 2 ที่ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x ว่ามีทั้งหมดกี่คู่นั่นเอง จากแนวคิดข้างต้น เราจะได้ว่าวัตถุที่เราสนใจคือ combination ของ <math>A \,</math> ที่มีขนาด 2 และเงื่อนไขคือ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x นั่นเอง