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

ข้อย่อย 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)\,$