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

Cardcaptor: /* ข้อย่อย 2 */

2009-09-04T14:28:42Z

ข้อย่อย 2

Cardcaptor: /* ข้อย่อย 1 */

2009-09-04T14:28:33Z

ข้อย่อย 1

158.108.183.136: /* ข้อย่อย 1 */

2009-09-04T14:16:02Z

ข้อย่อย 1

158.108.183.136: หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == เราจะพิสูจน์ข้อความนี้ด้วย induction (Base Case) ใน…'

2009-09-04T14:15:30Z

หน้าที่ถูกสร้างด้วย '== ข้อย่อย 1 == เราจะพิสูจน์ข้อความนี้ด้วย induction (Base Case) ใน…'

หน้าใหม่

== ข้อย่อย 1 ==
เราจะพิสูจน์ข้อความนี้ด้วย induction

(Base Case) ในกรณีนี้ <math>n = 1 \,</math> ซึ่งเราจะได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^1 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} f_1 & f_2 \\ 0 & f_1 \end{bmatrix} \,</math>

(Induction Case) สมมติให้ <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix}</math> สำหรับ <math>n \geq 1 \,</math> บางตัว เราได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^{n+1} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix} = \begin{bmatrix} f_ & 1 \\ 0 & 1 \end{bmatrix} </math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:28, 4 กันยายน 2552
แถว 10:		แถว 10:

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
−	จากข้อย่อย 1 เราสามารถคำนวณ <math>f_n</math> ได้ด้วยการคำนวณ <math>\begin{~~matrix~~}1 & 1 \\ 1 & 0 \end{~~matrix~~}^n</math> ซึ่งเราสามารถใช้อัลกอริทึีมได้ เพียงแต่เปลี่ยนการคูณจำนวนเต็มเป็นการคูณเมตริกซ์เท่านั้น เนื่องจากการคูณเมตริกซ์ขนาด 2 x 2 สามารถทำได้ใน <math>O(1) \,</math> เราจึงได้ว่าเราสามารถคำนวณ <math>f_n \,</math> ได้ในเวลา <math>O(\log n) \,</math>	+	จากข้อย่อย 1 เราสามารถคำนวณ <math>f_n</math> ได้ด้วยการคำนวณ <math>\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix}^n</math> ซึ่งเราสามารถใช้อัลกอริทึีมได้ เพียงแต่เปลี่ยนการคูณจำนวนเต็มเป็นการคูณเมตริกซ์เท่านั้น เนื่องจากการคูณเมตริกซ์ขนาด 2 x 2 สามารถทำได้ใน <math>O(1) \,</math> เราจึงได้ว่าเราสามารถคำนวณ <math>f_n \,</math> ได้ในเวลา <math>O(\log n) \,</math>

@@ แถว 2: / แถว 2: @@
 เราจะพิสูจน์ข้อความนี้ด้วย induction
-(Base Case) ในกรณีนี้ <math>n = 1 \,</math> ซึ่งเราจะได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^1 =  \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} f_1 & f_2 \\ 0 & f_1 \end{bmatrix} \,</math>
+(Base Case) ในกรณีนี้ <math>n = 1 \,</math> ซึ่งเราจะได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^1 =  \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} f_2 & f_1 \\ f_1 & f_0 \end{bmatrix} \,</math>
-(Induction Case) สมมติให้ <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix}</math> สำหรับ <math>n \geq 1 \,</math> บางตัว เราได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^{n+1} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}</math>
+(Induction Case) สมมติให้ <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix}</math> สำหรับ <math>n \geq 1 \,</math> บางตัว เราได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n+1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} f_{n+1} + f_n & f_n + f_{n-1} \\ f_{n+1} + 0 & f_n + 0\end{bmatrix} = \begin{bmatrix} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{bmatrix}</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:16, 4 กันยายน 2552
แถว 5:		แถว 5:


−	(Induction Case) สมมติให้ <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix}</math> สำหรับ <math>n \geq 1 \,</math> บางตัว เราได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^{n+1} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 ~~& 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix} = \begin{bmatrix} f_~~ & 1 \\ 0 & 1 \end{bmatrix} </math>	+	(Induction Case) สมมติให้ <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix}f_n & f_{n+1} \\ 0 & f_n \end{bmatrix}</math> สำหรับ <math>n \geq 1 \,</math> บางตัว เราได้ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^{n+1} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}</math>