The Fibonacci numbers

จากงานของ OS อ.ให้ทำโปรแกรม fibonacci ให้เป็น child process เราก็เลยอยากจะยก fibonacci มาให้ดูว่า มีวิธีทำแบบไหนบ้าง

A recursive algorithm

Algorithm 1:
int fib(int n)
 {
    if (n <= 2) return 1;
    else return fib(n-1) + fib(n-2);
}

Dynamic programming

Algorithm 2:
int fib(int n)
{
    int f[n+1];
    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    return f[n];
 }

Space complexity

Algorithm 3:
int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
        }
    return b;
}

Recursive powering

Algorithm 4:
int fib(int n)
{
    int M[2][2] = {{1,0},{0,1}}
    for (int i = 1; i < n; i++)
        M = M * {{1,1},{1,0}}
    return M[0][0];
}

Algorithm 5:
int M[2][2] = {{1,0}{0,1}}
int fib(int n)
{
    matpow(n-1);
    return M[0][0];
}
void matpow(int n)
{
     if (n > 1) {
         matpow(n/2);
         M = M*M;
     }
     if (n is odd)
          M = M*{ {1,1} {1,0} }
}

ข้อมูลจากเว็บ http://www.ics.uci.edu/~eppstein/161/960109.html

1 Response to “The Fibonacci numbers”


  1. 1 aejunknaja ่่8 กุมภาพันธ์, 2008 ที่ 4:41 am

    อยากจะถามเรื่อง Fibonacci หน่ะคะ


ใส่ความเห็น

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 / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s




RSS เพลงเรา@odeo

  • มีความผิดพลาดเกิดขึ้น feed อาจใช้งานไม่ได้ชั่วคราว ลองใหม่อีกครั้งภายหลัง

RSS rss@thaimacdev

  • มีความผิดพลาดเกิดขึ้น feed อาจใช้งานไม่ได้ชั่วคราว ลองใหม่อีกครั้งภายหลัง

RSS rss@พี่ไท้

  • มีความผิดพลาดเกิดขึ้น feed อาจใช้งานไม่ได้ชั่วคราว ลองใหม่อีกครั้งภายหลัง

blog stats

  • 425,840 ครั้ง

%d bloggers like this: