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

รุ่นแก้ไขปัจจุบันเมื่อ 09:18, 4 กันยายน 2552

อินพุต: เซตของจำนวนเต็ม $A=\{a_{1},a_{2},...,a_{n}\}\,$ ที่มีสมาชิก $n\,$ ตัว และจำนวนเต็ม $S\,$

เอาพุต: คำตอบว่า "ใช่" หรือ "ไม่ใช่"

แนวคิด: เนื่องจากข้อนี้ต้องการตรวจสอบซับเซตทุก ๆ ซับเซตของ เซต $A\,$ ฉะนั้นวัตถุที่เราสนใจก็คือ ซับเซตนั่นเอง ซึ่งในห้องเรียนได้เรียนถึงวิธีการหยิบซับเซตขึ้นมาพิจารณาทีละซับเซตกันไปแล้ว เราก็จะใช้วิธีนั้นกัน นอกจากนี้โจทย์ข้อนี้ต้องการตรวจสอบว่าซับเซตที่เรากำลังพิจารณาอยู่นั้นมีค่าผลบวกเท่ากับจำนวนเต็ม $S\,$ หรือไม่ แสดงว่าเงื่อนไขก็คือ ผลบวกของซับเซตที่กำลังพิจารณาเท่ากับจำนวนเต็ม $S\,$ หรือไม่นั่นเอง

ให้อะเรย์ A เก็บค่าจำนวนเต็ม $n/,$ ตัว อะเรย์ G แต่ละช่องเก็บค่า 1 หรือ 2 ถ้า G[i] เก็บค่า 1 หมายถึง สมาชิกตัวที่ i ในอะเรย์ A เป็นสมาชิกของซับเซต แต่ถ้าเก็บค่า 2 คือไม่เป็นสมาชิกของซับเซต

จากแนวคิดข้างต้นสามารถเขียนเป็น pseudocode ได้ดังนี้ <geshi lang="c"> SUM(A,G,n) {

   sum <-- 0
   for i=0 to n-1
   {
        if G[i] = 1
        {
              sum = sum + A[i]
        }
   }    
   return(sum)

} </geshi>

<geshi lang="c"> GENERATE(k) {

    if k=0
    {     
        v<--SUM(A,G,n)
        if (v=S)
        {
             return 1
        }else{ 
             return 0
        }
     }else{
        for G[k-1]= 1 to G[k-1]=2
        {
             GENERATE(k-1)
        }
     }

} </geshi>

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

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

รุ่นแก้ไขปัจจุบันเมื่อ 09:18, 4 กันยายน 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

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