Cho n số, tạo dãy Fibonacci từ 0 đến n. Dãy Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
0 và 1 cố định, sau đó cộng hai số trước: 0+1=1, 1+1=2, 2+1=3...
Quy luật truy hồi: Fn = Fn-1 + Fn-2, với F(0)=0, F(1)=1.
Có nhiều cách tạo dãy:
Đệ quy - Gọi lại hàm, đơn giản nhưng độ phức tạp exponent, không hiệu quả.
Dùng vòng lặp For - Giảm độ phức tạp xuống O(n), hiệu quả.
Ví dụ
Đầu vào: n=10 Đầu ra: 0 1 1 2 3 5 8 13 21 34
Thuật toán
BAT DAU
B1: Hàm fibonacci(int n)
a=0, b=1, c, i
In a, b
Vòng lặp i=2; i
Ví dụ
#include <stdio.h>
void fibonacci(int n) {
int a = 0, b = 1, c, i;
printf("Day Fibonacci den %d la ", n);
printf("\n%d %d", a, b); // in 0 và 1
for (i = 2; i < n; ++i) {
c = a + b;
printf(" %d", c);
a = b;
b = c;
}
}
int main() {
int n = 10;
fibonacci(n);
return 0;
}
Kết quả
Day Fibonacci den 10 la
0 1 1 2 3 5 8 13 21 34