ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| แถว 18: | แถว 18: | ||
return x | return x | ||
else if k mod 2 = 0 // k เป็นจำนวนเต็มคู่ | else if k mod 2 = 0 // k เป็นจำนวนเต็มคู่ | ||
| − | + | ans=POWER(x,k/2) | |
return ans^2 | return ans^2 | ||
else // k เป็นจำนวนเต็มคี่ ดังนั้น k-1 เป็นจำนวนเต็มคู่ | else // k เป็นจำนวนเต็มคี่ ดังนั้น k-1 เป็นจำนวนเต็มคู่ | ||
| − | + | ans=POWER(x,(k-1)/2) | |
return (ans^2)*x | return (ans^2)*x | ||
</geshi> | </geshi> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 07:58, 4 กันยายน 2552
อินพุต: และ เป็นจำนวนเต็มที่ไม่เป็นลบ
เอาพุต: หาค่า
แนวคิดคือ จะเห็นว่า คือ คูณกัน ครั้ง ซึ่งการคูณจำนวน ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีกได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา ดังนั้น เวลาการทำงานควรจะเป็น (เหมือน binary serach นั่นเอง)
พิจารณากรณีที่ เป็นจำนวนเต็มคู่ จะได้ว่า ดังนั้น การหาค่า ก็สามารถทำได้ด้วยการหาค่า จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที
ส่วนกรณีที่ เป็นจำนวนเต็มคี่ จะได้ว่า จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ อีกทีก็จะได้ค่า ที่โจทย์ต้องการ
จากแนวคิดดังกล่าว นำมาเขียนเป็น 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>
