418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5

อินพุต: $x\,$ และ $k\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ

เอาพุต: หาค่า $x^{k}\,$

แนวคิดคือ จะเห็นว่า $x^{k}\,$ คือ $x\,$ คูณกัน $k\,$ ครั้ง ซึ่งการคูณจำนวน $k\,$ ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีกได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา $O(\log k)\,$ ดังนั้น เวลาการทำงานควรจะเป็น $T(k)=T(k/2)+O(1)\,$ (เหมือน binary serach นั่นเอง)

พิจารณากรณีที่ $k\,$ เป็นจำนวนเต็มคู่ จะได้ว่า $x^{k}=(x^{k/2})(x^{k/2})\,$ ดังนั้น การหาค่า $x^{k}\,$ ก็สามารถทำได้ด้วยการหาค่า $x^{k/2}\,$ จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที

ส่วนกรณีที่ $k\,$ เป็นจำนวนเต็มคี่ จะได้ว่า $k-1\,$ จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า $x^{k-1}\,$ ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ $x\,$ อีกทีก็จะได้ค่า $x^{k}\,$ ที่โจทย์ต้องการ

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

<geshi lang="c"> POWER(x,k)

   if k = 0
       return 1
   else if k = 1
       return x
   else if k mod 2 = 0  // k เป็นจำนวนเต็มคู่
               ans=POWER(x,k/2)
       return ans^2 
   else                // k เป็นจำนวนเต็มคี่ ดังนั้น k-1 เป็นจำนวนเต็มคู่
               ans=POWER(x,(k-1)/2)
       return (ans^2)*x

</geshi>