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

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

ข้อย่อย 1

อินพุต: เซตของจำนวนเต็ม $A\,$ ที่มีสมาชิกอยู่ $n\,$ ตัว

เอาพุต: มีจำนวนเต็ม $a,b,c\in A\,$ โดยที่ $a<b<c\,$ และ $a+b>c\,$ หรือไม่

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

จากแนวคิดดังกล่าวสามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ (ให้ค่า l=3)

<geshi lang="c"> GENERATE(n,l) {

   if l=0
   {
         if c[0] + c[1] > c[2] then // c[0],c[1],c[2] คือ a,b,c ตามลำดับ
                            return 1
         else
             return 0
   }else{
         for c[l-1] = l to n
             GENERATE(c[l-1]-1,l-1)
   }

} </geshi>

เวลาการทำงานของอัลกอริทึมข้างต้น คือเวลาที่ใช้ในการคำนวณหา combination ที่มีสมาชิก 3 ตัว คือ ${n \choose 3}=\Theta (n^{3})\,$ นั่นเอง

ข้อย่อย 2

สังเกตว่าถ้าเราเรียงจำนวนที่อยู่ใน A ได้แล้ว พิจารณาจำนวน $a\in A\,$ เราจะทำการตรวจสอบจำนวนที่ติดกับ $a\,$ ไปทางขวาอีกแค่สองตัวเท่านั้น (นั่นคือจำนวน $b,c\,$ จะอยู่ทางขวาของ a ไปอีกสองตำแหน่ง) ตามเงื่อนไข $a<b<c\,$ เพราะจำนวนถัดไปจำนวนที่สาม ตรวจสอบไปก็ไม่เกิดประโยชน์ ดังนั้นการเรียงจำนวนที่อยู่ใน A ก่อนจะทำให้เราลดจำนวนวัตถุที่เราต้องพิจารณาลงไปได้

ซึ่งจากแนวคิดดังกล่าวนำมาเขียนเป็น pseudocode ได้ดังนี้

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

    for i=0 to i < n
    {
        if A[i] + A[i+1] > A[i+2]
             return 1
        else
             return 0
    }

} </geshi>

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

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

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

ข้อย่อย 1

ข้อย่อย 2

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

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