Bài 40. Cách tính số Fibonacci trong C/C++

11
52713
Bài số 38 trong 69 bài của khóa học Học C Không Khó

Chắc các bạn cũng đã biết dãy Fibonacci là gì rồi. Đó là dãy số mà số tiếp theo là tổng của hai số liền trước, ví dụ: 1, 1, 2, 3, 5, 8, 13, …. Bài viết này sẽ hướng dẫn cho các bạn cách tính số fibonacci bằng phương pháp dùng đệ quy và không dùng đệ quy.

Dùng đệ quy để tính số fibonacci

Công thức truy hồi của dãy fibonacci có dạng: f(n) = f(n-1) + f(n-2) .

Với f(1) = 1;  f(2) =1;

Cách tính số Fibonacci trong C

Cách tính số Fibonacci trong C++

- Bài viết liên quan dành cho bạn -

Khi đã có hệ thức truy hồi thì việc viết hàm đệ quy rất đơn giản phải không nào ? Nhưng liệu bạn có thử nhập n lớn ( cỡ 30 – 40 ) không ạ. Nếu thử rồi thì chắc các bạn cũng thấy nó chậm hơn rất nhiều. Nguyên nhân là khi tính số fibonacci thứ 5 chương trình sẽ yêu cầu tính hai số fibonacci thứ 4 và thứ 3. Nó lại tiếp tục như vậy đến khi tính được số fibonacci thứ 2 hoặc thứ 1 mới dừng lại.

Cách tính số fibonacci
Cách tính số fibonacci

Vậy nếu muốn chương trình của chúng ta chạy nhanh hơn thì chúng ta phải khử đệ quy. Cùng làm nhé !

Cách tính số Fibonacci không dùng đệ quy

Ý tưởng cách này là chúng ta sẽ dùng một vòng lặp để tính số Fibonacci .

  • Nếu n = 1 hoặc n = 2 thì chúng ta return 1
  • Sau đó tạo một biến i có giá trị bằng 3
  • Trong vòng while chúng ta tính a = a1 + a2
  • Sau đó gán a1 = a2 và a2 = a cứ chạy đến khi nào i = n thì dừng

Cách tính số Fibonacci trong C++

Tìm 1000 số Fibonacci đầu tiên

Với code trên bạn tìm đến số Fibo thứ 50 là bị tràn số rồi. Code với số nguyên lớn dưới đây sẽ giúp bạn tính được số Fibo thứ 1000 hoặc hơn thế nữa. Có thể bạn sẽ cần đọc bài viết dưới đây trước khi tham khảo code này.

Cộng trừ nhân chia 2 số nguyên lớn trong C/C++

Lời giải cho chương trình in ra 1000 số Fibo đầu tiên.

Dưới đây là giá trị của số Fibo thứ 1000:

Theo dõi lập trình không khó tại:

Các bài viết trong khóa họcBài trước: Bài 39. Cách tính giai thừa trong C/C++Bài sau: Bài 41. Mảng 1 chiều trong C
Subscribe
Notify of
guest
11 Bình luận
Inline Feedbacks
View all comments