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

Aoy เมื่อ 07:58, 4 กันยายน 2552

2009-09-04T07:58:30Z

Aoy เมื่อ 07:57, 4 กันยายน 2552

2009-09-04T07:57:20Z

Aoy เมื่อ 07:56, 4 กันยายน 2552

2009-09-04T07:56:24Z

Aoy เมื่อ 09:56, 2 กันยายน 2552

2009-09-02T09:56:46Z

Aoy เมื่อ 09:55, 2 กันยายน 2552

2009-09-02T09:55:44Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: $x \,$ และ $k \,$ เป็นจำนวนเต้ฒที่ไม่เป็…'

2009-09-02T09:55:23Z

หน้าที่ถูกสร้างด้วย 'อินพุต: <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> 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> k-1 \, </math> จะเป็นจำนวนเต็มคู่ ดังนั้นการหาค่า <math> x^{k-1} \, </math> ก็สามารถทำได้เหมือนกับกรณีข้างต้น หลังจากนั้นก็นำค่าที่ได้มาคูณกับ <math>x \, </math> อีกทีก็จะได้ค่า <math> x^k \, </math> ที่โจทย์ต้องการ

จากแนวคิดดังกล่าว นำมาเขียนเป็น pseudocode ได้ดังนี้

@@ แถว 18: / แถว 18: @@
          return x
      else if k mod 2 = 0  // k เป็นจำนวนเต็มคู่
-        ans=POWER(x,k/2)
+                ans=POWER(x,k/2)
          return ans^2
      else                // k เป็นจำนวนเต็มคี่ ดังนั้น k-1 เป็นจำนวนเต็มคู่
-        ans=POWER(x,(k-1)/2)
+                ans=POWER(x,(k-1)/2)
          return (ans^2)*x
 </geshi>

@@ แถว 20: / แถว 20: @@
          ans=POWER(x,k/2)
          return ans^2
-     else
+     else                // k เป็นจำนวนเต็มคี่ ดังนั้น k-1 เป็นจำนวนเต็มคู่
          ans=POWER(x,(k-1)/2)
          return (ans^2)*x
 </geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:56, 4 กันยายน 2552
แถว 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
		+	ans=POWER(x,(k-1)/2)
		+	return (ans^2)*x
		+	</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:55, 2 กันยายน 2552
แถว 1:		แถว 1:
−	อินพุต: <math> x \, </math> และ <math> k \, </math> ~~เป็นจำนวนเต้ฒที่ไม่เป็นลบ~~	+	อินพุต: <math> x \, </math> และ <math> k \, </math> เป็นจำนวนเต็มที่ไม่เป็นลบ

	เอาพุต: หาค่า <math> x^k \,</math>		เอาพุต: หาค่า <math> x^k \,</math>

@@ แถว 3: / แถว 3: @@
 เอาพุต: หาค่า <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> จากนั้นค่อยเอาค่าที่ได้มายกกำลังสองอีกที