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

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

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

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1067559660
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 09 Mar 2026 08:47:32 GMT


Sensitive client information

IP address: 158.108.32.49

$T(k)=T(k/2)+O(1)\,$ (เหมือน binary serach นั่นเอง)

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

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

จากแนวคิดดังกล่าว นำมาเขียนเป็น 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>