Фибоначчийн тоо

Математикийн шинжлэх ухаанд, Фибоначчийн тоо нь дараах дарааллаас бүрдэнэ:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

Тодорхойлолт ёсоор бол Фибоначчийн тооны эхний 2 тоо нь 0 болон 1 гэж өгөгдсөн ба түүнээс хойших Фибоначчийн тоонууд нь өмнөх 2 тооныхоо нийлбэртэй тэнцүү болно.

Математик томьёололоор Фибоначчийн "N" дэх тоог олохдоо рекурсив аргыг ашиглана.

F(n)= F(n - 1) + F(n - 2)

анхны утга нь,

F(0) = 0 , F(1) = 1.

байна.

Бине-ийн томъёо нь Fn утгыг функцээр илэрхийлдэг:

$F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}$

Фибоначчийн тоог хүн төрөлхтөн өөрсдийн ахуй амьдрал болоод шинжлэх ухааны олон салбар, урлаг , уран зураг гэх мэт маш олон салбарт амжилттай ашиглаж хэрэглэсээр байгаа билээ.

Фибоначчийн тоог олох ерөнхий 2 арга байдаг бөгөөд эдгээр нь Top Down болон Bottom Up арга болно.

Аль ч аргаар нь Фибоначчийн тоог ямар нэг програмчлалын хэл ашиглан олж болох боловч Фибоначчийн тооны N дэх тоог олоход зарцуулах хугацаагаар нь дээрх 2 аргын ялгаа гарч ирнэ.

Жишээ болгож Top Down аргаар программчлалын хэлний PLT-SCHEME (функционал хэл) хэлийг ашиглан хэрхэн олохыг сонирхоцгооё.

;fibonacci sequence
(define (fib n) 
  ;n параметрийн утга авах fib функц зарлаж байна
  (cond ((= n 0) 0)
        ((= n 1) 1)
        ;нөхцөл: хэрвээ n-ийн утга 1 болон 0 тэй тэнцүү үед 1 болон 0-г буцаах
        (else (+ (fib(- n 1)) (fib(- n 2))))))
        ;нөхцөл: дээрх нөхцөл үл биелэх үед fib(n - 1) + (fib(n - 2) утгыг буцаана.

PLT-SCHEME нь LISP программчлалын хэлний нэг төрөл бөгөөд ' ; ' цэг таслал тэмдэглэгээ нь тодорхойлолт болон тайлбар бичихэд хэрэглэдэг болно.

Дээрх бичсэн код-оор Фибоначчийн тооны 1~7 дахь тоог олоход шаардагдах үйлдлийн тоог олцгооё.

(fib 1) (fib 2)  (fib 3)  (fib 4)  (fib 5)   (fib 6) (fib 7)  
3        7        11       19       31        51      83 

гэх мэт үйлдэл зарцуулах ба Фибоначчийн тооны 8 дахь тоог олоход нийт 135 үйлдэл хийх нь байна.

Эндээс Top Down аргаар Фибоначчийн тооны N дэх тоог олоход O(2n) үйлдэл хамгийн иxдээ зарцуулах нь байна.

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Эндэээс(Time Complexity)нь

T(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1)

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

Гэхдээ энэ дээр O(2n) гэдэг маань жишээлбэл (fib 200)-г олоход 4 x 1013 жил хэрэгтэй болох нь гэдгийг анхаарна уу.

Бас үзнэ үү

Трибоначчийн тоо

Цахим холбоос

Фибоначчийн тоо

Энэ биологийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.

Энэ математикийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.

Энэ тооны онолын тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.

Энэ тооны тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.