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

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

เอาพุต: หาค่า <math> x^k \,</math>

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

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

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

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