หาจำนวน Fibonacci ด้วย Matrix

ตัวเลขฟิโบนักซี ซึ่งเป็นความสัมพันธ์เวียนบังเกิดที่มีสูตร

f(n)=f(n-1)+f(n-2); f(1)=f(2)=1

สมมติอยากรู้ f(3) ถ้าเขียนในรูป matrix (ขอเขียนแบบ Python list นะครับ) จะได้ว่า

[[f(3)]] = [[1, 1]] * [[f(2)], [f(1)]] = [[f(2) + f(1)]]

ซึง matrix ตัวหนึ่ง เก็บค่าตัวคูณ (สัมประสิทธิ์) ซึ่งก็เป็นค่าคงที่ไม่ขึ้นกับค่า n ส่วนอีก matrix เก็บเลข fibonacci ตัวก่อนๆ เพื่อใช้คำนวณตามสูตร

แต่ถ้าต้องการจะรู้ตัวถัดไป คือ f(4) จะมีปัญหาว่า matrix ที่เราได้ มีแค่ f(3) โดยไม่่มี f(2) งานนี้เราจึงต้องคูณ matrix แล้วเก็บค่าเก่าที่จำเป็นในการหาเลข fibonacci ตัวต่อไปด้วย คือเก็บ f(2) วิธีง่ายๆ ก็แค่คูณ 1 เก็บไว้ ที่เหลือ คูณ 0

[[f(3)], [f(2)]] = [[1, 1], [1, 0]] * [[f(2)], [f(1)]] = [[f(2) + f(1)], [f(2) + 0]]

[[f(4)], [f(3)]] = [[1, 1], [1, 0]] * [[f(3)], [f(2)]]

ถ้าแทน F(n) = [[f(n)], [f(n-1)]] และ [[1, 1], [1, 0]] = M จะได้ว่า

F(3) = M*F(2)
F(4) = M*F(3) = M*M*F(2) = M2F(2)
F(5) = M*F(4) = M*M*M*F(2) = M3F(2)

น้้นคือ

F(n) = M(n-2)F(2) ; F(2) = [[f(2)], [f(1)]] = [[1], [1]]

จะเห็นว่า เราเปลี่ยนรูปความสัมพันธ์จากการบวกไปเรื่อย มาเป็นการยกกำลังหรือการคูณเลข (หรือ matrix) ตัวเดียวกันหลายๆ ครั้ง
ซึ่งเป็นการคูณที่มักจะใช้ขั้นตอนการคำนวณมากกว่าการบวก การเปลี่ยนจากการบวกมาเป็นการยกกำลังนั้นน่าจะคำนวณยุ่งยากกว่า แต่การยกกำลังนั้น เราไม่จำเป็นต้องใช้อัลกอริทึมที่มีขั้นตอนอยู่ใน O(n) แต่ทำแบบ O(log(n)) ได้ โดยอาศัยหลักการที่ว่า Mn = (Mn/2)2 คือถ้าเราจะหา Mn ก็หใ้หา Mn/2 แล้วเอามายกกำลังสอง งานนี้เขียนโปรแกรมแบบ recursive จนกว่าจะถึง M หรือ M2 ก็หยุดเรียกตัวเอง ถ้าเกิด n เป็นเลขคี่ นั้นคือ n-1 เป็นเลขคู่ ก็ใช้สูตร Mn = M*Mn-1 = M*(M(n-1)/2)2

แนวทางจาก http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

One response to “หาจำนวน Fibonacci ด้วย Matrix

  1. Pingback: ถ่ายภาพจาก Huawei P9 กล้องซึ่ง Leica มีส่วนร่วม | Ultimateohm's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s