ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 3: | แถว 3: | ||
เอาพุต: หาค่า <math> x^k \,</math> | เอาพุต: หาค่า <math> x^k \,</math> | ||
| − | แนวคิดคือ จะเห็นว่า <math> x^k \, </math> คือ <math> x \, </math> คูณกัน <math> k \, </math> ครั้ง ซึ่งการคูณจำนวน <math> 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>x^k=(x^{k/2})(x^{k/2})\,</math> ดังนั้น การหาค่า <math> x^k \, </math> ก็สามารถทำได้ด้วยการหาค่า <math> x^{k/2} \, </math> จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที | ||
รุ่นแก้ไขเมื่อ 09:56, 2 กันยายน 2552
อินพุต: และ เป็นจำนวนเต็มที่ไม่เป็นลบ
เอาพุต: หาค่า
แนวคิดคือ จะเห็นว่า คือ คูณกัน ครั้ง ซึ่งการคูณจำนวน ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีกได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา ดังนั้น เวลาการทำงานควรจะเป็น (เหมือน binary serach นั่นเอง)
พิจารณากรณีที่ เป็นจำนวนเต็มคู่ จะได้ว่า ดังนั้น การหาค่า ก็สามารถทำได้ด้วยการหาค่า จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที
ส่วนกรณีที่ เป็นจำนวนเต็มคี่ จะได้ว่า จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ อีกทีก็จะได้ค่า ที่โจทย์ต้องการ
จากแนวคิดดังกล่าว นำมาเขียนเป็น pseudocode ได้ดังนี้
