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