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

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

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

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