Tóm Tắt
Dãy Fibonacci là gì?
Dãy Fibonacci tạo dãy các số bằng cách cộng hai số đằng trước. Dãy Fibonacci bắt đầu từ hai số: F0 & F1. Giá trị ban đầu của F0 & F1 có thể tương ứng là 0, 1 hoặc 1, 1.
Điều kiện của dãy Fibonacci là:
F
n
=
F
n
-
1
+
F
n
-
2
Ví dụ một dãy Fibonacci:
F8 = 0 1 1 2 3 5 8 13
Ví dụ một dãy Fibonacci khác:
F8 = 1 1 2 3 5 8 13 21
Dưới đây là phần minh họa cho dãy Fibonacci trên:
Giải thuật sử dụng vòng lặp cho dãy Fibonacci
Đầu tiên, giải thuật của chúng ta sẽ sử dụng vòng lặp để tạo dãy Fibonacci:
B
ắ
t
đầ
u gi
ả
i thu
ậ
t
Fibonacci
(
n
)
khai b
á
o f
0
,
f
1
,
fib
,
loop
Thi
ế
t l
ậ
p f
0
l
à
0
Thi
ế
t l
ậ
p f
1
l
à
1
hi
ể
n th
ị
f
0
,
f
1
for
loop
←
1
t
ớ
i n fib
←
f
0
+
f
1
f
0
←
f
1
f
1
←
fib
hi
ể
n th
ị
d
ã
y fib
k
ế
t th
ú
c
for
K
ế
t th
ú
c gi
ả
i thu
ậ
t
Giải thuật sử dụng đệ qui cho dãy Fibonacci
Tiếp theo, dựa vào đệ qui chúng ta sẽ thiết kế giải thuật cho dãy Fibonacci như sau:
B
ắ
t
đầ
u gi
ả
i thu
ậ
t
Fibonacci
(
n
)
khai b
á
o f
0
,
f
1
,
fib
,
loop
Thi
ế
t l
ậ
p f
0
l
à
0
Thi
ế
t l
ậ
p f
1
l
à
1
hi
ể
n th
ị
f
0
,
f
1
for
loop
←
1
t
ớ
i n fib
←
f
0
+
f
1
f
0
←
f
1
f
1
←
fib
hi
ể
n th
ị
d
ã
y fib
k
ế
t th
ú
c
for
K
ế
t th
ú
c gi
ả
i thu
ậ
t
