Nội dung chính
Đề bài
Viết chương trình c tìm n số Fibonacci đầu tiên.
Quy luật của dãy số Fibonacci: số tiếp theo bằng tổng của 2 số trước, 2 số đầu tiên của dãy số là 0, 1. Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Lời giải
Có 2 cách để viết chương trình dãy số Fibonacci trong C
- Tính dãy số Fibonacci trong C không dùng phương pháp đệ quy
- Tính dãy số Fibonacci trong C sử dụng phương pháp đệ quy
Tính dãy số Fibonacci không dùng phương pháp đệ quy
Ví dụ chương trình tính dãy số Fibonacci không sử dụng phương pháp đệ quy:
File: FibonacciExample1.c
/** * Tinh day so Fibonacci KHONG dung phuong phap de quy * * @author viettuts.vn */ #include<stdio.h> /** * Tinh so Fibonacci thu n * * @param n: chi so cua so Fibonacci tinh tu 0 * vd: F0 = 0, F1 = 1, F2 = 1, F3 = 2 * @return So Fibonacci thu n */ int fibonacci(int n) { int f0 = 0; int f1 = 1; int fn = 1; int i; if (n < 0) { return -1; } else if (n == 0 || n == 1) { return n; } else { for (i = 2; i < n; i++) { f0 = f1; f1 = fn; fn = f0 + f1; } } return fn; } /** * Ham main */ int main() { int i; printf("10 so dau tien cua day so Fibonacci: \n"); for (i = 0; i < 10; i++) { printf("%d ", fibonacci(i)); } }
Kết quả:
10 so dau tien cua day so Fibonacci: 0 1 1 2 3 5 8 13 21 34
Tính dãy số Fibonacci sử dụng phương pháp đệ quy
Ví dụ chương trình tính dãy số Fibonacci sử dụng phương pháp đệ quy:
File: FibonacciExample2.c
/** * Tinh day so Fibonacci bang phuong phap de quy * * @author viettuts.vn */ #include<stdio.h> /** * Tinh so Fibonacci thu n * * @param n: chi so cua so Fibonacci tinh tu 0 * vd: F0 = 0, F1 = 1, F2 = 1, F3 = 2 * @return So Fibonacci thu n */ int fibonacci(int n) { if (n < 0) { return -1; } else if (n == 0 || n == 1) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } /** * Ham main */ int main() { int i; printf("10 so dau tien cua day so Fibonacci: \n"); for (i = 0; i < 10; i++) { printf("%d ", fibonacci(i)); } }
Kết quả:
10 số đầu tiên của dãy số fibonacci: 0 1 1 2 3 5 8 13 21 34