ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต้ฒที่ไม่เป็…') |
Aoy (คุย | มีส่วนร่วม) |
||
แถว 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 ได้ดังนี้