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

รุ่นแก้ไขปัจจุบันเมื่อ 07:58, 4 กันยายน 2552

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

เอาพุต: หาค่า $x^{k}\,$

แนวคิดคือ จะเห็นว่า $x^{k}\,$ คือ $x\,$ คูณกัน $k\,$ ครั้ง ซึ่งการคูณจำนวน $k\,$ ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีกได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา $O(\log k)\,$ ดังนั้น เวลาการทำงานควรจะเป็น $T(k)=T(k/2)+O(1)\,$ (เหมือน binary serach นั่นเอง)

พิจารณากรณีที่ $k\,$ เป็นจำนวนเต็มคู่ จะได้ว่า $x^{k}=(x^{k/2})(x^{k/2})\,$ ดังนั้น การหาค่า $x^{k}\,$ ก็สามารถทำได้ด้วยการหาค่า $x^{k/2}\,$ จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที

ส่วนกรณีที่ $k\,$ เป็นจำนวนเต็มคี่ จะได้ว่า $k-1\,$ จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า $x^{k-1}\,$ ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ $x\,$ อีกทีก็จะได้ค่า $x^{k}\,$ ที่โจทย์ต้องการ

จากแนวคิดดังกล่าว นำมาเขียนเป็น 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>

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

รุ่นแก้ไขปัจจุบันเมื่อ 07:58, 4 กันยายน 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 1: / แถว 1: @@
-อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต้ฒที่ไม่เป็นลบ
+อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต็มที่ไม่เป็นลบ
 เอาพุต: หาค่า <math> x^k \,</math>
-แนวคิดคือ จะเห็นว่า <math> x^k \, </math> คือ <math> x \, </math> คูณกัน <math> k \, </math> ครั้ง ซึ่งการคูณจำนวน <math> k \, </math> ครั้งทั้งหมด สามารถทำการแยกการคูณแล้วค่อยเอาผลคูณย่อยมาคูณกันอีก ก็สามารถทำได้ และเนื่องจากโจทย์ต้องการให้อัลกอริทึมทำงานในเวลา <math>O(\log n) \,</math> ดังนั้น เวลาการทำงานควรจะเป็น <math>T(k)=T(k/2)+O(1) \,</math> (เหมือน binary serach นั่นเอง)
+แนวคิดคือ จะเห็นว่า <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> จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที
@@ แถว 10: / แถว 10: @@
 จากแนวคิดดังกล่าว นำมาเขียนเป็น 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>