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

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

2009-09-04T09:18:50Z

Aoy เมื่อ 08:01, 19 สิงหาคม 2552

2009-08-19T08:01:19Z

Aoy เมื่อ 08:00, 19 สิงหาคม 2552

2009-08-19T08:00:51Z

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

2009-08-18T11:40:47Z

125.27.52.227 เมื่อ 11:40, 18 สิงหาคม 2552

2009-08-18T11:40:05Z

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

2009-08-18T07:24:29Z

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

2009-08-18T06:37:36Z

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

2009-08-18T06:32:31Z

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

2009-08-18T06:27:08Z

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

2009-08-18T05:36:21Z

@@ แถว 8: / แถว 8: @@
 จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">
 SUM(A,G,n)
-:sum <-- 0
-:for i=0 to n-1
+    sum <-- 0
-::if G[i] = 1
+    for i=0 to n-1
-:::sum = sum + A[i]
-:return(sum)
+         if G[i] = 1
 GENERATE(k)
-:if k=0
-::v<--SUM(A,G,n)
+     if k=0
-::if (v=S)
-::: return 1
+         v<--SUM(A,G,n)
-::else
+         if (v=S)
-::: return 0
-:else
+              return 1
-:: for G[k-1]= 1 to G[k-1]=2
+         }else{
-::: GENERATE(k-1)
+              return 0
 เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง

@@ แถว 11: / แถว 11: @@
 SUM(A,G,n)
 :sum <-- 0
-::for i=0 to n-1
+:for i=0 to n-1
-:::if G[i] = 1
+::if G[i] = 1
-::::sum = sum + A[i]
+:::sum = sum + A[i]
-::return(sum)
+:return(sum)
 GENERATE(k)

@@ แถว 14: / แถว 14: @@
 :::if G[i] = 1
 ::::sum = sum + A[i]
-:if(sum=S)
+::return(sum)
 GENERATE(k)
 :if k=0
 ::v<--SUM(A,G,n)
-::if (v)
+::if (v=S)
 ::: return 1
 ::else

@@ แถว 24: / แถว 24: @@
 ::if (v)
 ::: return 1
-:else
+::else
 ::: return 0
 :else

@@ แถว 10: / แถว 10: @@
 SUM(A,G,n)
 :sum <-- 0
 ::for i=0 to n-1
 :::if G[i] = 1
 ::::sum = sum + A[i]
+:if(sum=S)
-:return(sum)
+::return(1)
 GENERATE(k)
 :if k=0
 ::v<--SUM(A,G,n)
+::if (v)
 ::: return 1
 :else
 ::: return 0
 :else
 :: for G[k-1]= 1 to G[k-1]=2
 ::: GENERATE(k-1)
 เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง

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

	จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้		จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้
		+
		+	SUM(A,G,n)
		+
		+	:sum <- 0
		+
		+	:for i<-0 to n-1
		+
		+	:if g[i] = 1
		+
		+	:sum = sum + A[i]
		+
		+	:return(sum)

	เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง		เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:36, 18 สิงหาคม 2552
แถว 1:		แถว 1:
	อินพุต: เซตของจำนวนเต็ม <math>A=\{ a_1, a_2,... ,a_n \} \, </math> ที่มีสมาชิก <math> n \, </math> ตัว และจำนวนเต็ม <math> S \, </math>		อินพุต: เซตของจำนวนเต็ม <math>A=\{ a_1, a_2,... ,a_n \} \, </math> ที่มีสมาชิก <math> n \, </math> ตัว และจำนวนเต็ม <math> S \, </math>
		+
		+	เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่"
		+
		+	แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต <math>A \,</math> ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม <math>S \,</math> หรือไม่นั่นเอง
		+
		+	จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้
		+
		+	เนื่องจากจำนวนซับเซตที่พิจารณาทั้งหมดมี <math>2^n \,</math> ซับเซต และแต่ละซับเซตต้องทำการตรวจสอบว่าผลบวกของมันเท่ากับ <math>S \, </math> หรือไม่ ซึ่งใช้เวลาอย่างมาก <math>O(n) \, </math> ดังนั้น เวลาการทำงานทั้งหมดของอัลกอริทึมคือ <math>O(n2^n) \,</math> นั่นเอง