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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต้ฒที่ไม่เป็…')
 
แถว 1: แถว 1:
อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต้ฒที่ไม่เป็นลบ
+
อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต็มที่ไม่เป็นลบ
  
 
เอาพุต: หาค่า <math> x^k \,</math>
 
เอาพุต: หาค่า <math> x^k \,</math>

รุ่นแก้ไขเมื่อ 09:55, 2 กันยายน 2552

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

เอาพุต: หาค่า

แนวคิดคือ จะเห็นว่า คือ คูณกัน ครั้ง ซึ่งการคูณจำนวน ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีก ก็สามารถทำได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา ดังนั้น เวลาการทำงานควรจะเป็น (เหมือน binary serach นั่นเอง)

พิจารณากรณีที่ เป็นจำนวนเต็มคู่ จะได้ว่า ดังนั้น การหาค่า ก็สามารถทำได้ด้วยการหาค่า จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที

ส่วนกรณีที่ เป็นจำนวนเต็มคี่ จะได้ว่า จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ อีกทีก็จะได้ค่า ที่โจทย์ต้องการ

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