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

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

 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 утгыг функцээр илэрхийлдэг:



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

Фибоначчийн тоог олох ерөнхий 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 жил хэрэгтэй болох нь гэдгийг анхаарна уу.

 Бас үзнэ үү 
Трибоначчийн тоо

 Цахим холбоос 
Фибоначчийн тоо

Ангилал:Цуваа ба дараалал
Ангилал:Тооны онол
Ангилал:Онолын биологи
Ангилал:Бүхэл тоон олонлог
Ангилал:Арифметик