Фибоначчийн тоо
Математикийн шинжлэх ухаанд, Фибоначчийн тоо нь дараах дарааллаас бүрдэнэ:
- 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 жил хэрэгтэй болох нь гэдгийг анхаарна уу.