Фибоначчийн тоо / Монгол
Математикын шинжлэх ухаанд, Фибоначчийн тоо нь дараах дарааллаас бүрдэнэ:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....
Тодорхойлолт ёсоор бол Фибоначчийн тооны эхний 2 тоо нь 0 болон 1 гэж өгөгдсөн ба түүнээс хойшхи Фибоначчийн тоонууд нь өмнөх 2 тооныхоо нийлбэртэй тэнцүү болно.
Математик томъёололоор Фибоначчийн "N" дэхь тоог олохдоо рекурсив аргыг ашиглана.
анхны утга нь,
байна.
Фибоначчийн тоог хүн төрөлхтөн өөрсдийн ахуй амьдрал болоод шинжлэх ухааны олон салбар, урлаг , уран зураг гэх мэт маш олон салбарт амжилттай ашиглаж хэрэглэсээр байгаа билээ.
Хэд хэдэн сонирхолтой жишээг дурдвал:
Фибоначчийн тоо нь дээрх зураган дээр үзүүлсэн шиг бие биенийхээ нэг тал болж нэгэн цогц дүрсийг бий болгосон байна.
Энэхүү зурагын хувьд Алтан эргүүлэг гэж нэрлэгдэх улаан , ногоон, шар зурвасуудаас бүрдсэн эргүүлэгийг та бүхэн харж байна. Улаан зурвас нь логорифмик муруйг төлөөлсөн бол шар муруй нь Фибоначчийн тооны алтан харьцаан дээр тулгуурлан зурсан болно. Харин ногоон муруй нь квадрат бүрийн дөрөвний нэг хэсгийн тангенц дээр тулгуурлан зурсан байна.
Наран цэцгийн дотор хэсэгт үзүүлсэн дүрс бол 34-с 55 ширхэг Фибоначчийн тооны цуваанаас бүрдсэн байдаг байна.
Фибоначчийн тоог олох ерөнхий 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)
|(fib 1)
|1
1
|(fib 2)
| (fib 1)
| 1
| (fib 0)
| 0
|1
1
|(fib 3)
| (fib 2)
| |(fib 1)
| |1
| |(fib 0)
| |0
| 1
| (fib 1)
| 1
|2
|(fib 4)
| (fib 3)
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| |(fib 1)
| |1
| 2
| (fib 2)
| |(fib 1)
| |1
| |(fib 0)
| |0
| 1
|3
3
|(fib 5)
| (fib 4)
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| 3
| (fib 3)
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| |(fib 1)
| |1
| 2
|5
5
|(fib 6)
| (fib 5)
| |(fib 4)
| | (fib 3)
| | |(fib 2)
| | | (fib 1)
| | | 1
| | | (fib 0)
| | | 0
| | |1
| | |(fib 1)
| | |1
| | 2
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| |3
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| 5
| (fib 4)
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| 3
|8
8
|(fib 7)
| (fib 6)
| |(fib 5)
| | (fib 4)
| | |(fib 3)
| | | (fib 2)
| | | |(fib 1)
| | | |1
| | | |(fib 0)
| | | |0
| | | 1
| | | (fib 1)
| | | 1
| | |2
| | |(fib 2)
| | | (fib 1)
| | | 1
| | | (fib 0)
| | | 0
| | |1
| | 3
| | (fib 3)
| | |(fib 2)
| | | (fib 1)
| | | 1
| | | (fib 0)
| | | 0
| | |1
| | |(fib 1)
| | |1
| | 2
| |5
| |(fib 4)
| | (fib 3)
| | |(fib 2)
| | | (fib 1)
| | | 1
| | | (fib 0)
| | | 0
| | |1
| | |(fib 1)
| | |1
| | 2
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| |3
| 8
| (fib 5)
| |(fib 4)
| | (fib 3)
| | |(fib 2)
| | | (fib 1)
| | | 1
| | | (fib 0)
| | | 0
| | |1
| | |(fib 1)
| | |1
| | 2
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| |3
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| 5
|13
13
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 жил хэрэгтэй болох нь гэдгийг анхаарна уу.
Илүү ихийг:
http://en.wikipedia.org/wiki/Fibonacci_number
http://mn.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B9%D0%BD_%D1%82%D0%BE%D0%BE
