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

ข้อย่อย 1

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

เอาพุต: มีคู่ของจำนวนเต็ม $a,b\in A\,$ ที่ $a<b,a+b=x\,$ อยู่กี่คู่

แนวคิด จากโจทย์ เราต้องการหาคู่ของจำนวนเต็ม $a,b\in A\,$ ที่ $a<b,a+b=x\,$ ซึ่งในห้องเรียนเราได้รู้วิธีการหา combination มาแล้ว ซึ่งข้อนี้ก็คือการหาซับเซตของ $A\,$ ที่มีขนาด 2 ที่ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x ว่ามีทั้งหมดกี่คู่นั่นเอง จากแนวคิดข้างต้น เราจะได้ว่าวัตถุที่เราสนใจคือ combination ของ $A\,$ ที่มีขนาด 2 และเงื่อนไขคือ สมาชิกของซับเซตทั้งสองตัวนี้บวกกันแล้วได้เท่ากับ x นั่นเอง

จากแนวคิดข้างต้น เมื่อเขียนเป็น pseudocode จะได้ดังนี้

ตัวแปรทุกอย่างขออ้างอิงจากในห้องเรียน โดยที่ข้อนี้ให้ l = 2

COUNT(c,x)

count <-- 0

if(c[0]+c[1]= x)

count <-- count + 1

return(count)

GENERARTE(m,l)

if l = 0

return(COUNT(c,x))

else

for c[l-1]=0 to c[l-1] = 2

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

ข้อย่อย 2

อินพุต เอาพุตยังเหมือนข้อย่อย 1

แนวคิด วัตถุที่เราสนใจและเงื่อนไขยังเหมือนข้อย่อย 1 และเนื่องจากเงื่อนไขคือ $a+b=x\,$ นั่นคือ ถ้าเราพิจารณาจำนวนเต็ม $a\in A\,$ ใด ๆ เราสามารถถามได้ว่าจำนวนเต็ม $b\,$ ซึ่งเท่ากับ $x-a\,$ นั้นมีอยู่ในเซต $A\,$ หรือไม่ ได้ในเวลา$O(f(n))\,$ เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมของเราทำงานได้ในเวลา $O(n.f(n))\,$ ข้อนี้กำหนดให้ อัลกอริทึม EXIST มีการทำงานคือถามว่าจำนวนเต็ม $b\,$ มีอยู่ในเซต $A\,$ หรือไม่ และใช้เวลาทำงานเป็น $O(f(n))\,$

GENERATE(A,x,n)

count <-- 0

for i=0 to n-1

if (EXIST(x-A[i]))

count <-- count + 1

return (count)