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)

GENERATE(m,l)

if l=0

if c[0] + c[1] > c[2] // c[0],c[1],c[2] คือ a,b,c ตามลำดับ

then return 1

else

return 0

else

for c[l-1] = l to m

GENERATE(c[l-1]-1,l-1)

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