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

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

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.

байна.

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

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

Цахим холбоос[засварлах | кодоор засварлах]

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