Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Gải thuật tính F(n) - Dãy Fibonaci bội 3

  1. #1
    Ngày gia nhập
    02 2008
    Nơi ở
    AYS 107
    Bài viết
    41

    Thumbs down Gải thuật tính F(n) - Dãy Fibonaci bội 3

    Dãy Fibonaci bội 3 được định nghĩ đệ qui như sau:
    F(n+3)=F(n+2) + F(n+1) + F(n) với n>0
    F(1) = F(2) = F(3) =1
    Có hay không giải thuật tính F(n) với n=2^k với thời gian tính là O(logn) ??
    Nếu có hãy chỉ ra giải thuật như vậy!!

    Bài thi cấu trúc dữ liệu của mình hôm nay đó. Không giải được
    Có bạn nào có ý tưởng gì không??
    I don't wanna waste another day

  2. #2
    Ngày gia nhập
    09 2008
    Bài viết
    10

    mình xin chỉ thuật giải
    ko bít có áp dụng được bài của bạn ko?
    bạn thử xem nha
    ta có ptdq:
    F(n) = n, n<2 (1)
    F(n) = F (n-1) + F (n-2) , n >=2 (2)
    giải ptdq trên
    BG
    Ta có:
    F(n) - F (n-1) - F(n-2) = 0
    phương trình đặc trưng sẽ là:
    X^2 - X - 1 = 0
    ptdt có 2 nghiệm pb là
    X = (1-sqrt5)/2
    X = (1+sqrt5)/2
    =>
    F (n) = C1.[(1-sqrt5)/2]^n + C2 [(1+sqrt5)/2]^n
    với n = 0 <=> F0 = C1 + C2 = 0 (3)
    với n = 1 <=> F1 = C1.[(1-sqrt5)/2]^1 + C2 [(1+sqrt5)/2]^1 = 1 (4)
    => từ (3) và (4) ta được
    C1 = -1/sqrt5
    C2 = 1/sqrt5
    => Fn = (1/sqrt5).([(1+sqrt5)/2]^n - [(1-sqrt5)/2]^n)
    => Fn = O(max((1+sqrt5)/2]^n),(1-sqrt5)/2]^n)))
    = O (1+sqrt5)/2]^n)
    ĐS:
    Fn = O (1+sqrt5)/2]^n)

    nhìn hơi phức tạp nhưng bạn viết ra giấy thì thấy rất đơn giản thui

  3. #3
    Ngày gia nhập
    09 2008
    Bài viết
    10

    hoặc có cách khác để đặt n = 2^k là
    dùng pp đệ quy từ phương trình
    F(n+3)=F(n+2) + F(n+1) + F(n) với n>0
    rùi đến một số bước ta tách được pttq của nó
    giả sử là
    Fn = 2^i.F(n/(2^i)) + i.C2.n (1)
    khi đó n = 2^k quá trình suy rộng kết thúc khi i = k
    ta có
    vì 2^k = n => k = log2(n) và F(1) = F(2) = F(3) =1
    nên thay vào (1) ta được
    Fn = n.F(1) + log2(n).C2.n
    = n + C2.log2(n).n
    => Fn = O (max (n ,log2(n).n)
    => Fn có độ phức tạp là
    O(n.log2(n))

    tuơng tự vậy nha bạn
    mình cũng chỉ biết có thế thui
    chúc bạn thành công

  4. #4
    Ngày gia nhập
    05 2008
    Bài viết
    14

    cái này có nhầm không pro xem lại phương trình dặc trưng xem.hình như phải là X^3-X^2-X-1=0 chứ.phương trình này chỉ có duy nhất 1 nghiệm thôi
    giờ say mê bên ai em đổ lỗi anh vô tình

Các đề tài tương tự

  1. Tìm giá trị số fibonaci thứ n bằng đệ quy????
    Gửi bởi blue_23 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 09-08-2010, 02:22 AM
  2. Dãy Fibonaci
    Gửi bởi pannaruto trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 02-01-2010, 11:30 AM
  3. Bài tập C | Tìm số Fibonaci thứ n!
    Gửi bởi nqpbvh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 14
    Bài viết cuối: 25-06-2009, 05:18 PM
  4. In dãy Fibonaci vào tệp
    Gửi bởi kegiaumat055 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 20-12-2008, 08:14 PM
  5. Bàn về giải thuật kiểm tra một số có phải là số Fibonaci hay không
    Gửi bởi luckyluke trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 02-03-2008, 10:12 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn